1、对一般二叉树，仅根据一个先序、中序、后序遍历，不能确定另一个遍历序列。但对于满二叉树，任一结点的左右子树均含有数量相等的结点，根据此性质，可将任一遍历序列转为另一遍历序列（即任一遍历序列均可确定一棵二叉树）。r
voidPreToPostElemTypepreposti
tl1h1l2h2r
将满二叉树的先序序列转为后序序列，l1h1l2h2是序列初始和最后结点的下标。r
ifh1l1r
posth2prel1根结点r
halfh1l12左或右子树的结点数r
PreToPostprepostl11l1halfl2l2half1将左子树先序序列转为后序序列r
PreToPostprepostl1half1h1l2halfh21将右子树先序序列转为后序序列r
PreToPostr
32叶子结点只有在遍历中才能知道，这里使用中序递归遍历。设置前驱结点指针pre，初始为空。第一个叶子结点由指针head指向，遍历到叶子结点时，就将它前驱的rchild指针指向它，最后叶子结点的rchild为空。r
Li
kedListheadpre
ull全局变量r
Li
kedListI
OrderBiTreebtr
中序遍历二叉树bt，将叶子结点从左到右链成一个单链表，表头指针为headr
ifbtI
Orderbtlchild中序遍历左子树r
ifbtlchild
ullbtrchild
ull叶子结点r
ifpre
ullheadbtprebt处理第一个叶子结点r
elseprerchildbtprebt将叶子结点链入链表r
I
Orderbtrchild中序遍历左子树r
prerchild
ull设置链表尾r
r
retur
headI
Orderr
时间复杂度为O
辅助变量使用head和pre栈空间复杂度O
r
r
2、设有两个集合A和集合B，要求设计生成集合CA∩B的算法，其中集合A、B和C用链式存储结构表示。r
typedefstruct
odei
tdatastruct
ode
extlklistr
voidi
tersectio
lklisthalklisthblklisthcr
r
lklistpqtr
forphahc0p0pp
extr
forqhbq0qq
extifqdatapdatabreakr
ifq0tlklistmallocsizeoflklisttdatapdatat
exthchctr
r
r
r
3、若第
件物品能放入背包，则问题变为能否再从
1件物品中选出若干件放入背包（这时背包可放入物品的重量变为sw
）。若第
件物品不能放入背包，则考虑从
1件物品选若干件放入背包（这时背包可放入物品仍为s）。若最终s0则有一解；否则，若s0或虽然s0但物品数
1则无解。r
（1）sw
1K
apsw
1truer
（2）s
1K
ap←K
aps
1r
r
4、将顶点放在两个集合V1和V2。对每个顶点，检查其和邻接点是否在同一个集合中，如是，则为非二部图。为此，用整数1和2表示两个集合。再用一队列结构存放图中访问的顶点。r
i
tBPGraphAdjMatrixgr
判断以邻接矩阵表示的图g是r