数据结构1800题和答案第6章 树和二叉树答案
第 6 章 树和二叉树
一、选择题
1.D 2.B 3.C 4.D 5.D 6.A 7.1C 7.2A 7.3C 7.4A 7.5 8.B
C
9.C 10.D 11.B 12.E 13.D 14.D 15.C 16.B 17.C 18.C 19. 20.
BD
21.A 22.A 23.C 24.C 25.C 26.C 27.C 28.C 29.B 30.C 31. 32.
DB
33.A 34.D 35.B 36.B 37.C 38.B 39.B 40.B 41.1 41.2 42. 43.
F
B
CB
44.C 45.C 46.B 47.D 48.B 49.C 50.A 51.C 52.C 53.C 54. 55.
DC
56.B 57.A 58.D 59.D 60.B 61.1 61.2 61.3 62.B 63.B 64. 65.
B
A
G
DD
66.1 66.2 66.3 66.4 66.5
C
D
F
H
I
部分答案解释如下。
12. 由二 叉树 结点的 公式 ： n=n0+n1+n2=n0+n1+(n0-1)=2n0+n1-1 ， 因 为 n=1001, 所以
1002=2n0+n1,在完全二叉树树中，n1 只能取 0 或 1,在本题中只能取 0，故 n=501，因此选
E。
42.前序序列是“根左右”，后序序列是“左右根”，若要这两个序列相反，只有单支树，所
以本题的 A 和 B 均对，单支树的特点是只有一个叶子结点，故 C 是最合适的，选 C。A 或 B
都不全。由本题可解答 44 题。
47. 左子树为空的二叉树的根结点的左线索为空（无前驱），先序序列的最后结点的右线索
为空（无后继），共 2 个空链域。
52．线索二叉树是利用二叉树的空链域加上线索，n 个结点的二叉树有 n+1 个空链域。
二、判断题
1.× 2.× 3.× 4. 5. √ 6. 7.√ 8.× 9. 10. 11. 12.
√
√
√×××
13. 14. 15. 16. 17.√ 18. 19. 20. 21. 22. 23. 24.
×√××
√×√×√××
25. 26. 27. 28. 29.√ 30. 31. 32. 33. 34. 35. 36.
√×××
××√×××√
37. 38. 39. 40. 41.(3) 42. 43. 44. 45. 46. 47. 48.
√×××
√√×√×××
49. 50.
√√
部分答案解释如下。
6．只有在确定何序（前序、中序、后序或层次）遍历后，遍历结果才唯一。
19．任何结点至多只有左子树的二叉树的遍历就不需要栈。
24. 只对完全二叉树适用，编号为 i 的结点的左儿子的编号为 2i(2i<=n)，右儿子是 2i+1
（2i+1<=n）
37. 其中序前驱是其左子树上按中序遍历的最右边的结点（叶子或无右子女），该结点无右
孩子。 38 . 新插入的结点都是叶子结点。 42. 在二叉树上，对有左右子女的结点，其中序前驱是其左子树上按中序遍历的最右边的结 点（该结点的后继指针指向祖先），中序后继是其右子树上按中序遍历的最左边的结点（该 结点的前驱指针指向祖先）。 44．非空二叉树中序遍历第一个结点无前驱，最后一个结点无后继，这两个结点的前驱线索 和后继线索为空指针。
三.填空题
1.(1)根结点(2)左子树(3)右子树
2.(1)双亲链表表示法(2)孩子链表表示法(3)孩
子兄弟表示法
3．p->lchild==null && p->rchlid==null
4.(1) ++a*b3*4-cd (2)18
5.平
衡因子
6. 9
7. 12
8.(1)2k-1 (2)2k-1
9.(1)2H-1 (2)2H-1
(3)H=log2N+1
10. 用顺序存储二叉树时，要按完全二叉树的形式存储，非完全二叉树存储时，要加“虚结
点”。设编号为 i 和 j 的结点在顺序存储中的下标为 s 和 t ,则结点 i 和 j 在同一层上的条
件是 log2s=log2t。
11. log2i=log2j
12.(1)0 (2)(n-1)/2 (3)(n+1)/2 (4) log2n +1
13.n
14. N2+1
15.(1) 2K+1-1 (2) k+1
16. N/2
17. 2k-2
18.
64
19. 99
20. 11
21.(1) n1-1 (2)n2+n3
22.(1)2k-2+1（第 k 层 1 个结点，总结点个数是 2H-1，其双亲是 2H-1/2=2k-2）(2) log2i+1
23.69
24. 4
25.3h-1
26. n/2
27. log2k+1
28.(1)完全二叉树 (2)单枝树，树中任一结点（除最后一个结点是叶子外）,只有左子女或
只有右子女。
29.N+1 30.(1) 128(第七层满，加第八层１个) (2) 7
31. 0 至多个。任意二叉树，度为１的结点个数没限制。只有完全二叉树，度为１的结点个
数才至多为 1。
32．21
33.(1)2 (2) n-1 (3) 1 (4) n
(5) 1 (6) n-1
34.(1) FEGHDCB (2)BEF（该二叉树转换成森林，含三棵树，其第一棵树的先根次序是
BEF）
35.(1)先序（2）中序
36. (1)EACBDGF （2）2
37.任何结点至多只有右子女
的二叉树。
38.(1)a (2) dbe (3) hfcg 39.(1) .D.G.B.A.E.H.C.F. (2) ...GD.B...HE..FCA
40.DGEBFCA
41．(1)5 （2）略
42.二叉排序树
43.二叉树
44.前序
45.(1) 先 根 次 序 （ 2 ） 中 根 次 序 46. 双 亲 的 右 子 树 中 最 左 下 的 叶 子 结 点 47.2
48.(n+1)/2
49.31（x 的后继是经 x 的双亲 y 的右子树中最左下的叶结点）
50.(1)前驱 (2)后
继
51.(1)1 (2)y^.lchild (3)0 (4)x (5)1 (6) y (7)x(编者注：本题按
中序线索化)
52.带权路径长度最小的二叉树，又称最优二叉树
53.69
54.(1)6 (2)261
55.(1)80 (2)001（不唯一）56.2n0-1
57.本题①是表达式求值，②是在二叉排序树中删除值为 x 的结点。首先查找 x，若没有 x，
则结束。否则分成四种情况讨论：x 结点有左右子树；只有左子树；只有右子树和本身是叶
子。
(1)Postoder_eval(t^.Lchild) (2) Postorder_eval(t^.Rchild) (3)ERROR(无此运
算符)(4)A
(5)tempA^.Lchild (6)tempA=NULL (7)q^.Rchild (8)q (9)tempA^.Rchild
(10)tempA^.Item
(2) IF (t=NIL) AND (m≤n) OR (t<>NIL) AND (m>n) THEN all:=false
ELSE BEGIN chk(t^.l,2*m);chk (t^.r,2*m+1);END
59. (1)p->rchild
(2)p->lchild
(3)p->lchild
(4)ADDQ(Q,p->lchild)
(5)ADDQ(Q,p->rchild)
60.(1)t->rchild!=null (2)t->rchild!=null (3)N0++
(4)count(t->lchild)
(5)count(t->rchild)
61.(1)p (2)0 (3)height(p->lchild) (4)0 (5)height(p->rchild) (6)lh+1
(7)rh+1 (8)0
62.(1)p<>NIL (2)addx(p)
(3)addx(tree)
(4)r^.rchild
63.(1)stack[tp]=t
(2) p=stack[tp--]
(3)p
(4)++tp
64.① 本算法将二叉树的左右子树交换
② (1)new (s) //初始化，申请结点 (2) s^.next=NIL
//s 是带头结点的
链栈
(3)s^.next^.data //取栈顶元素 (4)s^.next:= p^.next //栈顶指针下移
(5)dispose(p)
//回收空间
(6)p^.next:=s^.next //将新结点入链
栈
(7)push(s,p^.rchild) //先沿树的左分支向下，将 p 的右子女入栈保存
(8)NOT empty(s) (9) finishe:=true //已完成
(10)finish=true （或
s^.next=NIL）
65.(1)new(t) (2)2*i≤n (3)t^.lchild,2*i (4)2*i+1≤n (5)t^.rchild,2*i+1
(6)1
66.(1)Push(s,p) (2)K=2 (3)p->data=ch
(4)BT=p
(5) ins>>ch
67.(1)result; (2)p:=p^.link; (3) q:=q^.pre （（２）（３）顺序可变）
68.(1)top++
(2) stack[top]=p->rchild
(3)top++
(4)stack[top]=p->lchild
69．(1)(i<=j) AND (x<=y)
(2)A[i]<>B[k]
(3)k-x
(4)creatBT(i+1,i+L,x,k-1,s^.lchild) (5) creatBT(i+L+1,j,k+1,y,s^.rchild)
70. (1)push(s,bt) （2）pop(s) （3）push(s,p^.rchild) // p 的右子树进栈
71．(1) p=p->lchild // 沿左子树向下 （2）p=p->rchild
72．(1)0
（2）hl>hr
(3)hr=hl
73. (1)top>0 (2)t*2 // 沿左分枝向下 （3）top-1 // 退栈
74．(1)p:=p^.lchild
（2）（3）p:=S.data[s.top]^.rchild (4)s.top=0
75. (1)*ppos // 根结点 （2）rpos=ipos (3)rpos–ipos (4)ipos (5)ppos+1
76. (1)top>0 (2)stack[top]:=nd^.right (3)nd^.left<>NIL (4)top:=top+1 (左子
树非空)
77. (1) p<>thr // 未循环结束
（2）p->ltag=0
(3)p->lchild
(4)p->rtag=1 && p->rchild!=thr (5) p=p->rchild
(6)p=p->rchild
78. 若 p^.rtag=1,则 p^.rchild 为后继，否则 p 的后继是 p 的右子树中最左下的结点
(1)q=p^.rchild
(2)q^.ltag=0
(3) q^.lchild
79．（1）tree->lchild (2)null
(3)pre->rchild
(4)pre->rtag=1
(5) pre->right=tree; (6) tree->right (注（4）和（5）顺
序可换)
80．（1）node->rflag==0
(2)*x=bt
(3) *x=node->right
四．应用题
1．树的孩子兄弟链表表示法和二叉树二叉链表表示法，本质是一样的，只是解释不同，
也就是说树（树是森林的特例，即森林中只有一棵树的特殊情况）可用二叉树唯一表示，并
可使用二叉树的一些算法去解决树和森林中的问题。
树和二叉树的区别有三：一是二叉树的度至多为 2，树无此限制；二是二叉树有左右子
树之分，即使在只有一个分枝的情况下， 也必须指出是左子树还是右子树，树无此限制；
三是二叉树允许为空，树一般不允许为空（个别书上允许为空）。
2.树和二叉树逻辑上都是树形结构，区别有以上题 1 所述三点。二叉树不是树的特例。
3．线性表属于约束最强的线性结构，在非空线性表中，只有一个“第一个”元素，也
只有一个“最后一个”元素；除第一个元素外，每个元素有唯一前驱；除最后一个元素外，
每个元素有唯一后继。树是一种层次结构，有且只有一个根结点，每个结点可以有多个子女，
但只有一个双亲（根无双亲），从这个意义上说存在一（双亲）对多（子女）的关系。广义
表中的元素既可以是原子，也可以是子表，子表可以为它表共享。从表中套表意义上说，广
义表也是层次结构。从逻辑上讲，树和广义表均属非线性结构。但在以下意义上，又蜕变为
*
线性结构。如度为 1 的树，以及广义表中的元素都是原 子时。另外，广义表从元素之间的关系可看成前驱和后继，也符
+
+
合线性表，但这时元素有原子，也有子表，即元素并不属于同一
+
f
g
h
数据对象。 4．方法有二。一是对该算术表达式（二叉树）进行后序遍历，
+
*
得到表达式的后序遍历序列，再按后缀表达式求值；二是递归
a
bc
+
求出左子树表达式的值，再递归求出右子树表达式的值，最后 按根结点运算符（+、-、*、/ 等）进行最后求值。
d
e
5．该算术表达式转化的二叉树如右图所示。
第 5 题图
6．n（n>0）个结点的 d 度树共有 nd 个链域，除根结点外，每个结点均有一个指针所指，
故该树的空链域有 nd-(n-1)=n(d-1)+1 个。
7．证明：设二叉树度为 0 和 2 的结点数及总的结点数分别为 n0，n2 和 n，则 n=n0+n2 …
(1)
再 设 二 叉 树 的 分 支 数 为 B, 除 根 结 点 外 ， 每 个 结 点 都 有 一 个 分 支 所 指 ， 则
n=B+1… … …(2)
度为零的结点是叶子，没有分支，而度为 2 的结点有两个分支，因此（2）式可写为
n=2*n2+1
……………(3)
由（1）、（3）得 n2=n0-1,代入（1），并由（1）和（2）得 B=2*(n0-1)。 证毕。
8．(1)kh-1(h 为层数)
（2）因为该树每层上均有 Kh-1 个结点，从根开始编号为 1，则结点 i 的从右向左数第２个
孩子的结点编号为 ki。设 n 为结点 i 的子女，则关系式(i-1)k+2<=n<=ik+1 成立，因 i 是
整数，故结点 n 的双亲 i 的编号为 n-2)/k+1。
(3) 结点 n(n>1)的前一结点编号为 n-1（其最右边子女编号是(n-1)*k+1），故结点 n 的
第 i 个孩子的编号是(n-1)*k+1+i。
(4) 根据以上分析，结点 n 有右兄弟的条件是，它不是双亲的从右数的第一子女，即 (n-
1)%k!=0，其右兄弟编号是 n+1。
9．最低高度二叉树的特点是，除最下层结点个数不满外，其余各层的结点数都应达到
各层的最大值。设 n 个结点的二叉树的最低高度是 h，则 n 应满足 2h-1
为 O(logn)。
10．2n-1(本题等价于高度为 n 的满二叉树有多少叶子结点，从根结点到各叶子结点的单枝
树是不同的二叉树。)
11．235。由于本题求二叉树的结点数最多是多少，第 7 层共有 27-1=64 个结点，已知有 10 个
叶子，其余 54 个结点均为分支结点。它在第八层上有 108 个叶子结点。所以该二叉树的结
点数最多可达(27-1+108)=235。(注意；本题并未明说完全二叉树的高度，但根据题意，只能
8 层。)
12．1023（=210-1）
13．证明：设度为 1 和 2 的结点数是 n1 和 n2，则二叉树结点数 n 为 n=m+n1+n2…………
(1)
由于二叉树根结点没有分枝所指，度为 1 和 2 的结点各有 1 个和 2 个分枝，度为 0 的
结点没有分枝，故二叉树的结点数 n 与分枝数 B 有如下关系
n=B+1=n1+2*n2+1……………………….(2)
由（1）和（2），得 n2=m-1。即 n 个结点的二叉树，若叶子结点数是 m，则非叶子结点
中有（m-1）个度为 2，其余度为 1。
14．根据顺序存储的完全二叉树的性质，编号为 i 的结点的双亲的编号是 i/2，故 A[i]和
A[j]的最近公共祖先可如下求出：
while(i/2!=j/2)
if(i>j) i=i/2; else j=j/2;
退出 while 后，若 i/2=0,则最近公共祖先为根结点，否则最近公共祖先是 i/2。
15．N 个结点的 K 叉树，最大高度 N（只有一个叶结点的任意 k 叉树）。设最小高度为 H，第
i(1<=i<=H)层的结点数 Ki-1，则 N=1+k+k2+…+ kH-1，由此得 H=logK(N(K-1)+1)
16. 结点个数在 20 到 40 的满二叉树且结点数是素数的数是 31，其叶子数是 16。
17．设分枝结点和叶子结点数分别是为 nk 和 n0，因此有 n=n0+nk
(1)
另 外 从 树 的 分 枝 数 B 与 结 点 的 关 系 有 n=B+1=K*nk +1
(2)
由（1）和（2）有 n0=n-nk=(n(K-1)+1)/K
18.用顺序存储结构存储 n 个结点的完全二叉树。编号为 i 的结点，其双亲编号是 i/2(i=1
时无双亲)，其左子女是 2i(若 2i<=n,否则 i 无左子女)，右子女是 2i+1(若 2i+1<=n,否则无
右子女)。
19. 根据完全二叉树的性质，最后一个结点（编号为 n）的双亲结点的编号是 n/2，这是
最后一个分枝结点，在它之后是第一个终端（叶子）结点，故序号最小的叶子结点的下标是
n/2+1。
20. 按前序遍历对顶点编号，即根结点从１开始，对前序遍历序列的结点从小到大编号。
21. 设树的结点数为 n，分枝数为 B，则下面二式成立
n=n0+n1+n2+…+nm
(1)
n=B+1= n1+2n2+…+mnm
(2)
m
(i 1)n i
由(1)和(2)得叶子结点数 n0=1+ i1
22. log2n +1
23.15
24. 该结论不成立。对于任一 a€A,可在 B 中找到最近祖先 f。a 在 f 的左子树上。对于从
f 到根结点路径上所有 b€B，有可能 f 在 b 的右子树上，因而 a 也就在 b 的右子树上，这时
a＞b，因此 a＜b 不成立。同理可以证明 b
空指针数为 n*m-(n-1)=n*(m-1)+1。证毕。
26. 证明 设度为 1 和 2 及叶子结点数分别为 n0，n1 和 n2，则二叉树结点数 n 为 n=n0+n1+n2
(1)
再看二叉树的分支数，除根结点外，其余结点都有一个分支进入，设 B 为分支总数，则
n=B+1。度为 1 和 2 的结点各有 1 个和 2 个分支，度为 0 的结点没有分支，故 n=n1+2n2+1
(2)
由（1）和（2），得 n0= n2+1。
27. 参见题 26．
28. 设完全二叉树中叶子结点数为 n，则根据完全二叉树的性质，度为 2 的结点数是 n-1，
而完全二叉树中，度为 1 的结点数至多为 1，所以具有 n 个叶子结点的完全二叉树结点数是
n+(n-1)+1=2n 或 2n-1（有或无度为 1 的结点）。由于具有 2n(或 2n-1)个结点的完全二叉树
的深度是 log2(2n)+1( log2(2n-1)+1，即 log2n+1,故 n 个叶结点的非满的完全二叉树
的高度是 log2n+1。（最下层结点数>=2）。
29. (1)根据二叉树度为 2 结点个数等于叶子结点个数减 1 的性质，故具有 n 个叶子结点且
非叶子结点均有左左子树的二叉树的结点数是 2n-1。
(2)证明：当 i=1 时，2-（1-1）=20=1，公式成立。设当 i=n-1 时公式成立，证明当 i=n 时公式
仍成立。
设某叶子结点的层号为 t，当将该结点变为内部结点，从而再增加两个叶子结点时，这
两个叶子结点的层号都是 t+1，对于公式的变化，是减少了一个原来的叶子结点，增加了两
个新叶子结点，反映到公式中，因为 2-(t-1)=2-(t+1-1)+2-(t+1-1)，所以结果不变，这就证明当 i=n
时公式仍成立。证毕．
30．结点数的最大值 2h-1（满二叉树），最小值 2h-1（第一层根结点，其余每层均两个结点）。
31．（1）k(u-1)+1+i (2) (v-2)/k+1 (参见第 8 题推导)
32．该二叉树是按前序遍历顺序编号，以根结点为编号 1，前序遍历的顺序是“根左右”。
33．（1）设 n=1，则 e=0+2*1=2（只有一个根结点时，有两个外部结点），公式成立。
设有 n 个结点时，公式成立，即
En=In+2n
(1)
现在要证明，当有 n+1 个结点时公式成立。
增加一个内部结点，设路径长度为 l，则
In+1=In+l
(2)
该内部结点，其实是从一个外部结点变来的，即这时相当于也增加了一个外部结点（原
外部结点变成内部结点时，增加两个外部结点），则
En+1=En+l+2
(3)
由（1）和（2），则（3）推导为
En+1=In+2n+l+2=In+1-l+2n+l+2
=In+1+2(n+1）
故命题成立
（2）成功查找的平均比较次数 s=I/n
不成功查找的平均比较次数 u=（E-n）/（n+1）=（I+n）/n+1
由以上二式，有 s=（1+1/n）*u-1 。 34．
2
1
14
13
16
7
3
8
4
15
12
0
9 该有向图只有一个顶点入度为 0，其余顶点入度均为 1，
5
6
10 11
它不是有向树。
35．题图
36．参见 26 题
37．由于二叉树前序遍历序列和中序遍历序列可唯一确定一棵二叉树，因此，若入栈序列为
1，2，3，…，n，相当于前序遍历序列是 1，2，3，…，n，出栈序列就是该前序遍历对应的
二叉树的中序序列的数目。因为中序遍历的实质就是一个结点进栈和出栈的过程，二叉树的
形态确定了结点进栈和出栈的顺序，也就确定了结点的中序序列。
下图以入栈序列 1，2，3，（解释为二叉树的前序序列）为例，说明不同形态的二叉树在
中序遍历时栈的状态和访问结点次序的关系：
1 2 3
1
2 3
1
2
3
1 2
3
1 2 3
栈状态 访 栈状态 访 栈状态 访 栈状态 访 栈状态 访
问
问
问
问
问
空
空
空
空
空
1
1
1
1
1
12
12
12
空
空
1
123
1
21
21
2
12 3 13
空
12
空
2
1
21
33
23
3
空
1空
1空
32
空
3
3
空
2
38．给定二叉树结点的前序序列和对称序（中序）序列，可以唯一确定该二叉树。因为前序
序列的第一个元素是根结点，该元素将二叉树中序序列分成两部分，左边（设 l 个元素）表
示左子树，若左边无元素，则说明左子树为空；右边（设 r 个元素）是右子树，若为空，则
右子树为空。根据前序遍历中“根—左子树—右子树”的顺序，则由从第二元素开始的 l 个
结点序列和中序序列根左边的 l 个结点序列构造左子树，由前序序列最后 r 个元素序列与
中序序列根右边的 r 个元素序列构造右子树。
由二叉树的前序序列和后序序列不能唯一确定一棵二叉树，因无法确定左右子树两部分。
例如，任何结点只有左子树的二叉树和任何结点只有右子树的二叉树，其前序序列相同，后
序序列相同，但却是两棵不同的二叉树。
39．前序遍历是“根左右”，中序遍历是“左根右”，后序遍历是“左右根”。三种遍历中只
是访问“根”结点的时机不同，对左右子树均是按左右顺序来遍历的，因此所有叶子都按相
同的相对位置出现。
40．在第 38 题，已经说明由二叉树的前序序列和中序序列可以确定一棵二叉树，现在来证
明由二叉树的中序序列和后序序列，也可以唯一确定一棵二叉树。
当 n=1 时，只有一个根结点，由中序序列和后序序列可以确定这棵二叉树。
设当 n=m-1 时结论成立，现证明当 n=m 时结论成立。
设中序序列为 S1，S2，…，Sm,后序序列是 P1,P2,…，Pm。因后序序列最后一个元素 Pm
是根，则在中序序列中可找到与 Pm 相等的结点（设二叉树中各结点互不相同）Si(1≤i≤m)，
因中序序列是由中序遍历而得，所以 Si 是根结点，S1，S2，…，Si-1 是左子树的中序序列，
而 Si+1,Si+2,…,Sm 是右子树的中序序列。
若 i=1，则 S1 是根，这时二叉树的左子树为空，右子树的结点数是 m-1,则{S2，S3，…，
Sm}和{P1，P2，…，Pm-1}可以唯一确定右子树，从而也确定了二叉树。
若 i=m,则 Sm 是根，这时二叉树的右子树为空，左子树的结点数是 m-1，则{S1，S2，…，
Sm-1}和{P1，P2，…，Pm-1}唯一确定左子树，从而也确定了二叉树。
最后，当 1
叉树的左子树和右子树的后序遍历序列。因而由{S1，S2，…，Si-1}和{AP1，P2，…，Pi-1} A
可唯一确定二叉树的左子树，由{Si+1,Si+2,…，Sm}和
B
C
B
C
{Pi,Pi+1,…，Pm-1}可唯一确定二叉树的右子树 。
由中序序列 DBEAFGC 和后序序列 DEBGFCA 构
D
EF
D
EF
造的二叉树如右图：
G
G
H
41．证明请参见第 40 题和第 38 题
第 40 题图
第 41 题图
由前序序列 ABDGECFH 和中序序列 DGBEAFHC 构造的二叉树如图：
42．参见第 38 题
43．先序遍历二叉树的顺序是“根—左子树—右子树”，中序遍历“左子树—根—右子树”，
后序遍历顺序是：“左子树—右子树―根＂，根据以上原则，本题解答如下：
（１） 若先序序列与后序序列相同，则或为空树，或为只有根结点的二叉树
（２） 若中序序列与后序序列相同，则或为空树，或为任一结点至多只有左子树的二叉树．
（３） 若先序序列与中序序列相同，则或为空树，或为任一结点至多只有右子树的二叉树．
（４） 若中序序列与层次遍历序列相同，则或为空树， 或为任一结点至多只有右子树的二叉树
由中序序列 DBEAFIHCG 和后序序列 DEBHIFGCA 确定的二叉树略。
A
B
D
44. 森林转为二叉树的三步： （１）连线（将兄弟结点相连，各树的根看作兄弟）； （２）切线（保留最左边子女为独生子女，将其它子女分枝切掉）； （３）旋转（以最左边树的根为轴，顺时针向下旋转 45 度）。 其实经过（１）和（２），已转为二叉树， 执行（３）只是为了与平时的二叉树的画法一致。
45．（1）①tree[p]·l→p ② tree[p]·r→p ③ p=0
CEG
H
F
I
KO
J
LM
P
N
O
（2）框（A）移至Ⅲ处，成为前序遍历。
44 题图
46.
A
A
B
C
B
C
D
E
null
F
G
H
(1)
D
E
F
G
H
(2)
A BM D
F
C EM H G
(3)
47.
A
B
C
D
E
F
G
H
J I
K
L (1)
A
C
F
K
BE I
J
D
H
G
L
(2)
48． （1）
A
B
D
CE
F
G
I
H
（2）设二叉树的前序遍历序列为 P1，P2，…，Pm，中序遍历序列为 S1,S2,…，Sm。因为前 序遍历是“根左右”，中序遍历是“左根右”，则前序遍历序列中第一个结点是根结点（P1）。 到中序序列中查询到 Si=P1,根据中序遍历时根结点将中序序列分成两部分的原则，有：
若 i=1，即 S1=P1，则这时的二叉树没有左子树; 否则，S1,S2,…,Si-1 是左子树的中 序遍历序列,用该序列和前序序列 P2,P3，…，Pi 去构造该二叉树的左子树。
若 i=m,即 Sm=P1,则这时的二叉树没有右子树; 否则,Si+1,Si+2,…，Sm 是右子树的中 序遍历序列，用该序列和前序序列中 Pi+1,Pi+2,…,Pm,去构造该二叉树的右子树。算法描 述请参见下面算法设计第 56 题。 （3）若前序序列是 abcd，并非由这四个字母的任意组合（4!=24）都能构造出二叉树。因为 以 abcd 为输入序列，通过栈只能得到 1/(n+1)*2n!/(n!*n!)=14 种，即以 abcd 为前序序列 的二叉树的数目是 14。任取以 abcd 作为中序遍历序列，并不全能与前序的 abcd 序列构成 二叉树。例如：若取中序列 dcab 就不能。
该 14 棵二叉树的形态及中序序列略。
49．不能。因 DABC 并不是 ABCD 的合法出栈序列，参照第 37、48（3）的解释。
50．先序序列是“根左右” 后序序列是“左右根”，可见对任意结点，若至多只有左子女或
至多只有右子女，均可使前序序列与后序序列相反，图示如下：
F
C
D
IA
H
50 题
E
G
51．
B
52．按层次遍历，第一个结点（若树不空）为根，该结点在中序序列中把序列分成左右两部
分—左子树和右子树。若左子树不空，层次序列中第二个结点左子树的根；若左子5树1 为题空，
则层次序列中第二个结点右子树的根。对右子树也作类似的分析。层次序列的特点是图：从左
到右每个结点或是当前情况下子树的根或是叶子。
A
B
C
DE
F I
G
H
J (52)题图
A
B
E
CF
G
D
H
I (52)题(1)
A
E
B CD
F
G
H
I
(52 题(1)对应森林)
53．森林的先序序列和后序序列对应其转换的二叉树的先序序列和中序序列，应先据此构造 二叉树，再构造出森林。
A
K
BF
G
C DE HI J
L
N
MG O
54．
A B
C D
53 题森林
A B
C
D
E
(54)题图
E
55．HIDJKEBLFGCA
56.
A
G B
H
C
D
I
E
F
J
A
B
C
D
FE
G
K IH
J
A
H B
IK
C
D
J
L
E F
1 2 34
5 6
7
57．M 叉树的前序和后序遍历分别与它转换成的二叉树的先序和中序遍历对应。 58．前序遍历是“根左右”，中序遍历是“左根右”，后序遍历是“左右根”。若将“根”去 掉，三种遍历就剩“左右”。三种遍历中的差别就是访问根结点的时机不同。二叉树是递归 定义的，对左右子树均是按左右顺序来遍历的，因此所有叶子结点间的先后关系都是相同的。 59．本题的核心是三种遍历的顺序：“根左右”-“左根右”-“左右根”，但对本题的解答必 须先定义结点间相互关系的“左右”。本解答中将 N 是 M 的左子女，当作 N 在 M 的左边，而 N 是 M 的右子女，当作 N 在 M 的右边。若定义 P 是 M 和 N 的最近公共祖先，N 在 P 的左子树 中，M 在 P 的右子树中，称 N 在 M 的左边，那时的答案是不一样的。
先根遍历时 n 先被访
问
N 在 M 的左边
N 在 M 的右边
N 是 M 的祖先
N 是 M 的子孙
60．HIDJKEBLFGCA
61．
A
B
CG
中根遍历时 n 先被访 问
H
DEF I
L
J
K
后根遍历时 n 先被访 问
62．后序遍历的顺序是“左子树—右子树—根结点”。因此，二叉树最左下的叶子结点是遍
历的第一个结点。下面的语句段说明了这一过程（设 p 是二叉树根结点的指针）。
if(p!=null)
{while (p->lchild!=null || p->rchild!=null)
{while(p->lchild!=null) p=p->lchild;
if(p->rchild!=null) p=p->rchild; } }
return(p); //返回后序序列第一个结点的指针；
63. 采用前序和后序两个序列来判断二叉树上结点 n1 必定是结点 n2 的祖先。
在前序序列中某结点的祖先都排在其前。若结点 n1 是 n2 的祖先,则 n1 必定在 n2 之前。
而在后序序列中，某结点的祖先排在其后，即若结点 n1 是 n2 的祖先，则 n1 必在 n2 之后。
根据这条规则来判断若结点 n1 在前序序列中在 n2 之前，在后序序列中又在 n2 之后，则它
必是结点 n2 的祖先。
64.(1)
（2） 前序序列：ABCEDFHGIJ
A
中序序列：ECBHFDJIGA
（3）后序线索树
null A
B
B
C
D
E
F
G
C
null E
D
F
G
后序序列：ECHFJIGDBA
65. 最后一个递归调用语句所保留的参数没有意义。这类递归因其在算法最后，通常被称为
“尾递归”， 可不用栈且将其（递归）消除。 如中序遍历递归算法中，最后的递归语句
inorder (bt->rchild)可改为下列语句段：
bt=bt->rchild;
while (bt->rchild!=null)
{inorder (bt ->lchild); printf(“%c”,bt ->data);//访问根结点，假定结点数据域为
字符
bt=bt ->rchild; }
66.在二叉链表表示的二叉树中， 引入线索的目的主要是便于查找结点的前驱和后继。因为
若知道各结点的后继，二叉树的遍历就变成非常简单。二叉链表结构查结点的左右子女非常
方便，但其前驱和后继是在遍历中形成的。为了将非线性结构二叉树的结点排成线性序列，
利用结点的空链域，左链为空时用作前驱指针，右链为空时作为后继指针。再引入左右标记
ltag 和 rtag ，规定 ltag=0，lchild 指向左子女,ltag=1 时,lchild 指向前驱；当 rtag=0
时 ,rchild 指向右子女，rtag=1 时，rchild 指向后继。这样，在线索二叉树（特别是中序
线索二叉树）上遍历就消除了递归，也不使用栈（后序线索二叉树查后继仍需
要栈。）
67.
A
B
E
CF
K
D
I
GL
A
B
C
D
E F GH
IJ 67 题(2)
K
L MN
O
P
J
HM
67 题(1)
O
N
P
(3)后根遍历森林，结点序列为: BDCAIFJGHELOPMNK
68. （1）前序序列：ABDEHCFG （2）中序序列：DHEBAFCG （3）后序序列：HEDBFGCA
A
B
F
C
A
null
B
C
null
D
F
G
E H
null
A
B
F
C
69.（1）
（2）BiTree INORDER-PRIOR(N,X) //在中序线索二叉树上查找结点 N 的前驱结点 X {if(n->ltag==1){X=N->lchild; return (X);} else {p=N->lchild; while (p->rtag==0) p=p->rchild; X=p;return(p);} }
70.
A
B
C
D
E
F
A
A
C
B
C
null
null B
E
D
E
F
D
G
F
H
I
G
H
70题 （ 1）
I
71.
G
H
70题 （ 2）
I
A
前序序列：ＡＢＣＥＤＦＨＧＩJ 中序序列： E C B H F D J I G A 后序序列： ＥＣＨＦＪＩＧＤＢＡ
71 题（2）
B
C E
D null
F
G
H
I
70 题（3）
A null
B
C
D
E
F
G
H
I
J J
71 题（3） 72. 后序线索树中结点的后继，要么是其右线索（当结点的 rtag=1 时），要么是其双亲结点 右子树中最左下的叶子结点。所以，只有当二叉树只有根或树中任一结点均无右子树时，进 行遍历才不用栈，其遍历程序段如下：
while（p->ltag==0）p==p->lchild; //找最左下叶子结点
while（p->rchild!=null）{visit(p->data); //访问结点；
p=p->rchild;} //沿线索向上
对前序线索二叉树，当二叉树非空时，若其结点有左子女（ltag=0），左子女是后继；
否则，若结点有右子女（rtag=0），则右子女是后继；若无右子女（rtag=1），右子女是线索，
也指向后继。所以，对任何前序线索二叉树进行前序遍历均不需使用栈。
73．左右子树均不空的二叉树先序线索化后，空指针域为 1 个（最后访问结点的右链为空）。
74．if(p->ltag==0) return(p->lchild);//左子女不空，左子女为直接后继结点
else return(p->rchild);
//左子女空，右子女（或右线索）为后继
75. 后序线索树中结点的后继（根结点无后继），要么是其右线索（当结点的 rtag=1 时），
要么是其双亲结点右子树中最左下的叶子结点。对中序线索二叉树某结点，若其左标记等于
1,则左子女为线索，指向直接前驱；否则，其前驱是其左子树上按中序遍历的最后一个结点。
76. 树的后根遍历（对应二叉树的中序遍历）全线索链表
Data A
B
C
D
E
F
G
H
I
J
K
Ltag 0
1
0
0
0
1
0
1
1
1
1
Fch 2
null 5 7 8 5 11 2 8 9 3
Rtag 1
0
0
1
0
1
1
0
0
1
1
Nsib null 3
4
1
6
3
4
9
10 5
7
77.
0
1
0
10
1
0
10
25 1 c2
c5 10
11
0 1 c6 0 1
c3 3
4
5
6
c8 c1
1 36 c7 null
c4
A
F B
E
C
null G
DH
J
77题 中 序 线 索 树
I
77题 哈 夫 曼 编 码 树
虽然哈夫曼树的带权路径长度是唯一的，但形态不唯一。本题中各字母编码如下：
c1:0110 c2:10 c3:0010 c4:0111 c5:000 c6:010 c7:11 c8:0011
78. 字符 A，B，C，D 出现的次数为 9,1,5,3。其哈夫曼编码如下 A:1，B:000，C:01，
D:001
79．（2）wpl=(2+3)*5+6*4+(9+14+15)*3+(16+17)*2=229
0
1
0
16
1
0
1
17
1
0
1
0
14
15
90
1
0
1
0
9 1
5
0
1
6
0
1
2
3
13 78 题哈夫曼编码树
79题 （ 1）
(3) 编码为：15:111, 3:10101, 14:110, 2:10100, 6:1011, 9:100, 16:00, 17:01
(4) 常用哈夫曼树为通讯用的字符编码，本题中集合的数值解释为字符发生的频率（次数）。
由哈夫曼树构造出哈夫曼编码。译码时，进行编码的“匹配”，即从左往右扫描对方发来的
“编码串”，用字符编码去匹配，得到原来的元素（本题中的数）。
80．首先确定是否需加“虚权值”（即权值为 0）,对 m 个权值，建 k 叉树，若（m-1）%(k-
1)=0,则不需要加“虚权值”，否则，第一次归并时需（m-1）%(k-1)+1 个权值归并。建立 k
叉树的过程如下：
（1）将 m 个权值看作 m 棵只有根结点的 k 叉树的集合 F={T1，T2，…，Tm}。
（2）从 F 中选 k（若需加虚权值，则第一次选（m-1）%(k-1)+1）个权值最小的树作子树，
构成一棵 k 叉树，k 叉树根结点的权值为所选的 k 个树根结点权值之和，在 F 中
删除这 k 棵子树，并将新 k 叉树加入到 F 中。
385
（3）从 F 中选 k 个权值最小的树作子树，构成一棵 k 叉树，其根 结点权值等于所选的 k 棵树根结点权值之和，在 F 中删除这 k 棵树，
91
100
194
并将新得到的树加到 F 中。 (4) 重复（3），直到 F 中只有一棵树为止，这就是最优的 k 叉树。
25 30 36 49 64 81
对本题 10 个权值，构造最优三叉树。 因（10-1）%(3-1)=1，
5 9 16
所以第一次用 2 个权值合并。 最小加权路径长度：
1
4
（1+4）*4+(9+16)*3+(25+36+49+64+81)*2+100*1=705
字符 weight Papraernetnt lchlchrchrch
1A
3
08
00 00
81
．
初
态
图
2B
12
0 12
00 00
终态图
3C
7
0 10
00 00
82．前缀码是一编码不是任何其它编码
4D
4
09
00 00
前缀的编码。例如，0 和 01 就不是前缀
5E
2
08
00 00
码，因为编码 0 是编码 01 的前缀。仅
6F
8
0 10
00 00
从编码来看，0 和 01 是前缀码，但因历
7G
11
0 11
00 00
史的原因，它不被称为前缀码，而是把
8
5
09
05 01
一编码不是另一编码前缀的编码称为
9
9
0 11
04 08
前缀码。
10
15
0 12
03 06
利用二叉树可以构造前缀码，例如，
11
20
0 13
09 07
以 A，B，C，D 为叶子可构成二叉树，将
1122 1133
27 47
0 13 00
0 2 0 10 0 11 0 12
左分枝解释为 0，右分枝解释成 1，从根 结点到叶子结点的 0、1 串就是叶子的 前缀码。用哈夫曼树可构造出最优二叉
树，使编码长度最短。
83．哈夫曼树只有度为 0 的叶子结点和度为 2 的分枝结点，设数量分别为 n0 和 n2，则树的
结点数 n 为 n=n0+n2。 另根据二叉树性质：任意二叉树中度为 0 的结点数 n0 和度为 2 的结
点数 n2 间的关系是 n2=n0-1,代入上式，则 n=n0+n2=2n0-1。
84．（1）T 树的最大深度 Kmax=6（除根外，每层均是两个结点） T 树的最小深度 Kmin=4（具有 6 个叶子的完全二叉树是其中的一种形态）
（2）非叶子结点数是 5。（n2=n0-1） （3）哈夫曼树见下图，其带权路径长度 wpl=51
64 5
3
1
2 84题 图
85．（1）错误，循环结束条件 top=0 不能满足，因为在 top>1 情况下，执行 top:=top-1
(2)错误 （3）错误 （4）正确 （5）结点的深度与其右孩子深度相同，比左孩子
深度少 1。
五．算法设计题 1．[题目分析]以二叉树表示算术表达式，根结点用于存储运算符。若能先分别求出左子树 和右子树表示的子表达式的值，最后就可以根据根结点的运算符的要求，计算出表达式的最 后结果。 typedef struct node
{ElemType data; float val; char optr; //只取‘+’， ‘-’， ‘*’，‘/’ struct node *lchild，*rchild }BiNode,*BiTree; float PostEval(BiTree bt) // 以后序遍历算法求以二叉树表示的算术表达式的值 {float lv,rv; if(bt!=null) {lv=PostEval(bt->lchild); // 求左子树表示的子表达式的值 rv=PostEval(bt->rchild); // 求右子树表示的子表达式的值 switch(bt->optr) {case ‘+’: value=lv+rv; break; case ‘-’: value=lv-rv;break; case ‘*’: value=lv*rv;break; case ‘/’: value=lv/rv; } } return(value); } 2.[题目分析] 本题是将符号算术表达式用二叉树表示的逆问题，即将二叉树表示的表 达式还原成原表达式。二叉树的中序遍历序列与原算术表达式基本相同，差别仅在于二叉树 表示中消除了括号。将中序序列加上括号就恢复原貌。当根结点运算符优先级高于左子树 （或右子树）根结点运算符时，就需要加括号。 int Precede(char optr1,optr2) // 比较运算符级别高低，optr1 级别高于 optr2 时返回 1，相等时返回 0，低于时返 回-1
{switch(optr1) {case‘+’:case‘-’:if(optr2==‘+’||optr2==‘-’)return(0);else return(-
1);
case‘*’:case‘/’:if(optr1==‘*’||optr2==‘/’)return(0);else return(1);
}}
void InorderExp (BiTree bt)
//输出二叉树表示的算术表达式，设二叉树的数据域是运算符或变量名
{int bracket;
if(bt)
{if(bt->lchild!=null)
{bracket=Precede(bt->data,bt->lchild->data)//比较双亲与左子女运算符优
先级
if(bracket==1) printf(‘(’)；
InorderExp(bt->lchild);
//输出左子女表示的算术表达式
if(bracket==1)printf(‘)’)； //加上右括号
}
printf(bt->data);
//输出根结点
if(bt->rchild!=null)
//输出右子树表示的算术表达式
{bracket=Precede(bt->data,bt->rchild->data)
if (bracket==1)printf(“(”)； //右子女级别低，加括号
InorderExp (bt->rchild);
if(bracket==1)printf(“)”)；
}}
}//结束 Inorder Exp
3．[题目分析]首先通过对二叉树后序遍历形成后缀表达式，这可通过全局变量的字符
数组存放后缀表达式；接着对后缀表达式求值，借助于一栈存放运算结果。从左到右扫描后
缀表达式，遇操作数就压入栈中，遇运算符就从栈中弹出两个操作数，作运算符要求的运算，
并把运算结果压入栈中，如此下去，直到后缀表达式结束，这时栈中只有一个数，这就是表
达式的值。
char ar[maxsize];//maxsize 是后缀表达式所能达到的最大长度
int i=1;
void PostOrder(BiTree t )//后序遍历二叉树 t,以得到后缀表达式
{if(t)
{PostOrder(t->lchild); PostOrder(b->rchild)；ar[i++]=b->data; }
}//结束 PostOrder
void EXPVALUE()
//对二叉树表示的算术表达式，进行后缀表达式的求值
{ar[i]=‘\0’;
//给后缀表达式加上结束标记
char value[];
//存放操作数及部分运算结果
i=1; ch=ar[i++];
while(ch!=‘\0’)
{switch(ch)
{case ch in op: opnd1=pop(value);opnd2=pop(value); //处理运算符
push(operate(opnd2,ch,opnd1));break;
default:
push(value,ch);
//处理操作数，压入
栈中
}
ch=ar[i++];
//读入后缀表达式
} printf(value[1]);
//栈中只剩下一个操作数，即运算结束。
} //结束 EXPVALUE
[算法讨论] 根据题意，操作数是单字母变量，存放运算结果的栈也用了字符数组。实
际上，操作数既可能是变量，也可以是常量。运算中，两个操作数（opnd1 和 opnd2）也不
会直接运算，即两个操作数要从字符转换成数（如‘3’是字符，而数值 3=‘3’-‘0’）。数
在压入字符栈也必须转换，算法中的 operate 也是一个需要编写的函数，可参见上面算法设
计题 1，其细节不再深入讨论。
4．[题目分析]当森林（树）以孩子兄弟表示法存储时，若结点没有孩子（fch=null）,
则它必是叶子，总的叶子结点个数是孩子子树（fch）上的叶子数和兄弟（nsib）子树上叶
结点个数之和。
typedef struct node
{ElemType data;//数据域
struct node *fch, *nsib;//孩子与兄弟域 }*Tree;
int Leaves (Tree t)
//计算以孩子-兄弟表示法存储的森林的叶子数
{if(t)
if(t->fch==null)
//若结点无孩子，则该结点必是叶子
return(1+Leaves(t->nsib)); //返回叶子结点和其兄弟子树中的叶子结点数
else return (Leaves(t->fch)+Leaves(t->nsib)); //孩子子树和兄弟子树中叶子
数之和
}//结束 Leaves
5．[题目分析]由指示结点 i 左儿子和右儿子的两个一维数组 L[i]和 R[i]，很容易建立指
示结点 i 的双亲的一维数组 T[i]，根据 T 数组，判断结点 U 是否是结点 V 后代的算法，转
为判断结点 V 是否是结点 U 的祖先的问题。
int Generation (int U,V,N,L[],R[],T[])
//L[]和 R[]是含有 N 个元素且指示二叉树结点 i 左儿子和右儿子的一维数组，
//本算法据此建立结点 i 的双亲数组 T，并判断结点 U 是否是结点 V 的后代。
{for(i=1;i<=N;i++) T[i]=0; //T 数组初始化
for (i=1;i<=N;i++)
//根据 L 和 R 填写 T
if(L[i]!=0) T[L[i]]=i; //若结点 i 的左子女是 L，则结点 L 的双亲是结点 i
for(i=1;i<=N;i++)
if (R[i]!=0) T[R[i]]=i; //i 的右子女是 r，则 r 的双亲是 i
int parent=U;
//判断 U 是否是 V 的后代
while (parent!=V && parent!=0) parent=T[parent];
if (parent==V){printf(“结点 U 是结点 V 的后代”);return(1);}
else{ printf(“结点 U 不是结点 V 的后代”);return(0);}
}结束 Generation
6．[题目分析]二叉树是递归定义的，以递归方式建立最简单。判定是否是完全二叉树，可
以使用队列，在遍历中利用完全二叉树“若某结点无左子女就不应有右子女”的原则进行判
断。
BiTree Creat()
//建立二叉树的二叉链表形式的存储结构
{ElemType x；BiTree bt;
scanf(“%d”,&x); //本题假定结点数据域为整型
if(x==0) bt=null;
else if(x>0)
{bt=(BiNode *)malloc(sizeof(BiNode));
bt->data=x; bt->lchild=creat(); bt->rchild=creat();
}
else error(“输入错误”)；
return(bt);
}//结束 BiTree
int JudgeComplete(BiTree bt) //判断二叉树是否是完全二叉树,如是，返回 1，否
则，返回 0
{int tag=0; BiTree p=bt, Q[]; // Q 是队列，元素是二叉树结点指针，容量
足够大
if(p==null) return (1);
QueueInit(Q); QueueIn(Q,p); //初始化队列，根结点指针入队
while (!QueueEmpty(Q))
{p=QueueOut(Q);
//出队
if (p->lchild && !tag) QueueIn(Q,p->lchild); //左子女入队
else {if (p->lchild) return 0;
//前边已有结点为空，
本结点不空
else tag=1;
//首次出现结点为空
if (p->rchild && !tag) QueueIn(Q,p->rchild); //右子女入队
else if (p->rchild) return 0; else tag=1;
} //while
return 1; } //JudgeComplete
[算法讨论]完全二叉树证明还有其它方法。判断时易犯的错误是证明其左子树和右子数
都是完全二叉树，由此推出整棵二叉树必是完全二叉树的错误结论。
7．BiTree Creat(ElemType A[],int i)
//n 个结点的完全二叉树存于一维数组 A 中，本算法据此建立以二叉链表表示的完全二
叉树
{BiTree tree;
if (i<=n){tree=(BiTree)malloc(sizeof(BiNode)); tree->data=A[i];
if(2*i>n) tree->lchild=null；else tree->lchild=Creat(A,2*i)；
if(2*i+1>n) tree->rchild=null；else tree->rchild=Creat(A,2*i+1)； }
return (tree)； }//Creat
[算法讨论]初始调用时,i=1。
8. [题目分析]二叉树高度可递归计算如下：若二叉树为空，则高度为零，否则，二叉
树的高度等于左右子树高度的大者加 1。这里二叉树为空的标记不是 null 而是 0。设根结点
层号为 1，则每个结点的层号等于其双亲层号加 1。
现将二叉树的存储结构定义如下:
typedef struct node
{int L[];//编号为 i 的结点的左儿子
int R[];//编号为 i 的结点的右儿子
int D[];//编号为 i 的结点的层号
int i; //存储结点的顺序号（下标）
}tnode;
（1）int Height(tnode t,int i)//求二叉树高度，调用时 i=1
{int lh,rh;
if (i==0) return (0);
else{lh=Height(t,t.L[i]); rh=Height(t,t.R[i]);
if(lh>rh) return(lh+1); else return(rh+1);
}
}//结束 Height
（2）int Level（tnode t）//求二叉树各结点的层号，已知编号为 1 的结点是根，且层
号为 1
{t.D[1]=1;
for(i=1;i<=n;i++) {depth=t.D[i]；
//取出根结点层号
if(t.L[i]!=0) t.D[t.L[i]]=depth+1; //i 结点左儿子层号
if(t.R[i]!=0) t.D[t.R[i]]=depth+1; }//i 结点右儿子层号
}结束 level
9.[题目分析]二叉树采用顺序存储结构（一维数组）是按完全二叉树的形状存储的，不是完
全二叉树的二叉树顺序存储时，要加“虚结点”。数组中的第一个元素是根结点。本题中采
用队列结构。
typedef struct
{BiTree bt;
//二叉树结点指针
int num; }tnode // num 是结点在一维数组中的编号
tnode Q[maxsize]; //循环队列,容量足够大
void creat(BiTree T,ElemType BT[ ])
//深度 h 的二叉树存于一维数组 BT[1:2h-1]中，本算法生成该二叉树的二叉链表存
储结构
{tnode tq;
//tq 是队列元素
int len=2h-1; //数组长度
T=(BiTree)malloc(sizeof(BiNode)); //申请结点
T->data=BT[1];
//根结点数据
tq.bt=T; tq.num=1;
Q[1]=tq;
//根入队列
front=0;rear=1;
//循环队列头、尾指针
while(front!=rear)
//当队列不空时循环
{front=(front+1) % maxsize ;
tq=Q[front] ; p=tq.bt; i=tq.num ;
//出队，取出结点及编号
if (BT[2*i]==‘#’||2*i>len) p->lchild=null; //左子树为空，‘#’表示虚
结点
else //建立左子女结点并入队列
{p->lchild=(BiTree) malloc(sizeof(BiNode)); //申请结点空间
p->lchilddata=BT[2*i];
// 左子女数据
tq.bt=p->lchild; tq.num=2*i; rear=(rear+1) % maxsize ;//计算队尾位置
Q[rear]=tq;
//左子女结点及其编号入队
}