设前序序列为：
a1，a2，…，am，中序序列为：
b1，b2，…，bm。
因为前序序列由前序遍历得到，则a1为根结点元素；又中序序列由中序遍历得到，则在中序序列中必能找到和a1相同的元素并设为bj（1≤j≤m）,由此可得{b1，…，bj-1}为左子树的中序序列，{bj+1，…，bm}为右子树的中序序列。
（1）若j=1即b1为根，此时二叉树的左子树为空，{a2，…，am}即为右子树的前序序列，{b2，…，bm}即为右子树的中序序列，右子树的结点数为m-1，由此，这两个序列唯一确定了右子树，也唯一确定了二叉树。
（2）若j=m即bm为根，此时二叉树的右子树为空，{a2，…，am}即为左子树的前序序列，{b2，…，bm}即为左子树的中序序列，同
（1），这两个序列唯一确定了左子树，也唯一确定了二叉树。
（3）2≤j≤m-1，则子序列{a2，…，aj}和{b1，…，bj-1}分别为左子树的前序序列和中序序列，这两个序列唯一确定了左子树；子序列{aj+1，…，am}和{bj+1，…，bm}分别为右子树的前序序列和中序序列，这两个序列唯一确定了右子树；
由此，证明了知道一棵二叉树的前序序列和中序序列，就能唯一地确定一棵二叉树。
5．
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
A
B
C
D
E
F
G
H
I
J
K
L
M
N
O
6．
A
A
B
C
（a）
（b）
A
B
C
（c）
A
B
（d）
A
B
E
C
F
I
J
D
H
G1
J
K
（e）
7．
3
5
9
16
4
9
20
34
54
F
E
B
C
A
D
1
18
WPL=1*5+3*5+5*4+9*3+16*2+20*1
=119
A:
01
B:
0001
C:
001
D:
1
E:
00001
F:
00000
8．
F
c
d
-
b
*
a
+
f
e
/
-
波兰式：
-+a*b-cd/ef
逆波兰式：
abcd-*+ef/-
五．算法设计题
//-------二叉树的二叉链表存储表示-----
typedefstructBiTNode{
TElemTypedata;
structBiTNode*lchild,*rchild;
}BiTree;
1．
intNodes（BiTreebt）/*求以bt为根的二叉树中度为1的结点数目*/
{if（bt==NULL）return0;/*bt为空时，结点数为0*/
elseif（（bt->lchild==NULL）&&（bt->rchild==NULL））
return0;/*只有根节点时，结点数为0*/
elseif（（bt->lchild==NULL）||（bt->rchild==NULL））
return（1+Nodes（bt->lchild）+Nodes（bt->rchild））;
/*返回当前根节点和左或右子树中满足条件的节点数目*/
elsereturn（Nodes（bt->lchild）+Nodes（bt->rchild））;
/*返回左右子树中满足条件的节点数目*/
}//Nodes
2．
voidLeafPath（BiTreeT,intnum）
{/*求二叉树根结点T到所有叶子结点的路径*/
/*用数组path存储路径（不包括T在内），其中已有的元素个数为num，其初值为0*/
BiTreep;
inttop,i;
if（T==NULL）/*如果二叉树为空，则给出相应信息，算法结束*/
{printf（"二叉树为空!
"）;return;}
if（T->lchild==NULL&&T->rchild==NULL）
printpath（path,T,num）;/*输出路径*/
else
{
path[num+1]=T;/*将T放到路径中*/
LeafPath（T->lchild,num+1）;
LeafPath（T->rchild,num+1）;
}
}
其中printpath函数代码如下：
voidprintpath（BiTNode*path[],BiTreeT,intnum）
{
printf（"%c：
",T->data）;
for（inti=1;i<=num;i++）printf（"%c",path[i]->data）;
printf（"%c\n",T->data）;
}
3．
voidPreOrderTraverse（BiTreeT,inthigh）
{/*设二叉树的根指针为T，T所指结点的层次为high*/
if（T）
{printf（"（%c,%d）",T->data,high）;
PreOrderTraverse（T->lchild,high+1）;
PreOrderTraverse（T->rchild,high+1）;
}
4．BiTreechange（BiTreeT）/*二叉树左右子树交换递归算法*/
{BiTreep;
if（T!
=NULL）
if（T->lchild!
=NULL||T->rchild!
=NULL）
{
p=（BiTree）malloc（sizeof（BiTNode））;
p->data=T->data;
p->rchild=NULL;
p->lchild=T->lchild;
T->lchild=T->rchild;
T->rchild=p->lchild;
T->lchild=change（T->lchild）;
T->rchild=change（T->rchild）;
}
returnT;
}
5．
BiTNode*Node（BiTreebt）
{/*求二叉树T的后序序列的第一个结点的指针，采用非递归算法*/
StackElemTypestack[BiTree_Max_Size];/*定义顺序栈*/
BiTreep;
inttop;
top=-1;/*栈初始化*/
p=bt;
while（p）/*二叉树非空，根结点及其tag标记0一同入栈，然后遍历其左子树*/
{top++;
stack[top].T=p;
p=p->lchild;
}
if（top!
=-1）returnstack[top].T;
elsereturnNULL;
}
6．
BiThrNode*PreOrder_Next（BiThrNode*p）{
//在先序后继线索二叉树中查找结点p的先序后继，并返回指针
if（p->Ltag==0）returnp->lchild;
elsereturnp->rchild;
}//PreOrder_Next
voidPreOrderTraverse_Thr（BiThrTreeT）
{
BiThrNode*p;
p=T;
while（p!
=NULL）
{Visit（p->data）;p=PreOrder_Next（T）;}
}
7．
typedefcharTElemType;
//-------二叉树的二叉链表存储表示-----
typedefstructBiTNode{
TElemTyped
升级会员 