第66题图
注意：可能Ａ有左孩子或无左孩子，插入后考虑穿索的状态应作何修改。【上海大学1998六(17分)】 64．编写一算法，利用叶子结点中的空指针域将所有叶子结点链接为一个带有头结点的双链表，算法返回头结点的地址。【东北大学 1999 四(13分)】
65．编写程序段，利用中序全线索树求其中任意结点p^的前序后继结点，结果仍用p指出。要求先描述结构和算法思路。设线索树不带头结点，其中序序列第一结点的左标志和最后结点的右标志皆为０（非线索），对应指针皆为空。【北京工业大学 2000 七(10分)】
66.已知一个二叉树如下图，修改结点（node）的连接方式，以致可以不借助辅助堆栈实现中序遍历的非递归方法。画出修改后的结点连接图并写出其实现中序遍历的非递归算法。【浙江大学2002五（10分）】
67．已知指针p指向带表头的中根次序穿线二叉树中的某结点，试写一算法FFA（p，q），该算法寻找结点p的父亲结点q。设穿线二叉树的结点结构、表头结点结构和空树结构分别为（LTAG,LLINK,INFO,RLINK,RTAG）,且规定穿线树的最左下结点的LLINK域和最右下结点的RLINK域指向表头。【吉林大学 1999 二 、1 （16分）】
68. 给出中序线索树的结点结构并画出一个具有头结点的中序线索树，使其树结点至少应有6个。写一算法在不使用栈和递归的情况下前序遍历一中序线索树，并分析其时间复杂性。
【东南大学 1993 三(20分) 1997 三(18分) 1998 六(14分)】
69．设有二叉树BT，每个结点包括ltag、lchild、data、rchild、rtag五个字段，依次为左标志、左儿子、数据、右儿子、右标志。给出将二叉树BT建成前序（即先序）线索二叉树的递归算法。
【四川联合大学2000 三】【东南大学1999六(15分)】 70．写出中序线索二叉树的线索化过程（已知二叉树T）。
【山东大学 2000 五、2 (10分)】【长沙铁道学院 1997 五、6 (10分)】 71．已知一中序线索二叉树,写一算法完成对它的中序扫描。【山东大学2001软件与理论三
(8分)】
72．已知中序线索二叉树T右子树不空。设计算法，将S所指的结点作为T的右子树中的一个叶子结点插入进去，并使之成为T的右子树的（中序序列）第一个结点（同时要修改相应的线索关系）。
【合肥工业大学 2001 五、2（8分)】
73．写出算法，求出中序线索二叉树中给定值为x的结点之后继结点，返回该后继结点的指针。线索树中结点结构为：（ltag,lc,data,rc,rtag）。其中，data存放结点的值；lc，rc为指向左、右孩子或该结点前驱或后继的指针；ltag，rtag为标志域，各值为：0，则lc，rc为指向左、右孩子的指针；值为1，则lc，rc为指向某前驱后继结点的指针。【北京邮电大学 1996 八(20分)】
74．设后序线索树中结点构造为(Ltag,Lchild,Data,Rchild,Rtag)。其中:Ltag,Rtag 值为0时,Lchild、Rchild 分别为儿子指针；否则分别为直接前驱,直接后继的线索。请写出在后序线索树上找给定结点p^ 的直接前驱q 的算法。【武汉交通科技大学 1996 四、1（13
分）】
75．用算法说明在对称序穿线树中，如何对任意给定的结点直接找出该结点的对称序后继。
【山东大学 1999 六、３(10分）】
76．写出在中序线索二叉树里；找指定结点在后序下的前驱结点的算法。【河海大学1998七(10分）】
77．设中序穿线二叉树的结点由五个域构成：info:给出结点的数据场之值。LL：当LT 为1 时，则给出该结点的左儿子之地址，当LT为0时，则给出按中序遍历的前驱结点的地址。LT:标志域，为1或为0。RL：当RT为1时，则给出该结点的右儿子的地址；当RT为0时，则给出按中序遍历的后继结点地址。RT: 标志域为0或为1。
请编写程序，在具有上述结点结构的中序穿线二叉树上，求某一结点p的按后序遍历次序的后继结点的地址q，设该中序穿线二叉树的根结点地址为r。另外，请注意必须满足：（1）额外空间的使用只能为O(1)，(2)程序为非递归。【上海交通大学 2000 十(20分)】 78．写出按后序序列遍历中序线索树的算法。【东南大学 2000 六(15分)】
79．给定一组项及其权值，假定项都存放于二叉树的树叶结点，则具有最小带权外部路径长度的树称为huffman 树。（1）给出构造huffman 树 的算法。（2）给定项及相应的权如下表：画出执行上述算法后得到的huffman树。（3）用c语言编写构造huffman 树的程序. 【浙江大学 2000 七 (18分)】 序号 1 2 向 A B 15 6 3 C 7 4 D 12 5 E 25 6 F 4 7 G 6 8 H 1 9 I 15 80、二叉树T的中序遍历序列和层次遍历序列分别是BAFDGCE和ABCDEFG，试画出该二叉树（3分），并写出由二叉树的中序遍历序列和层次遍历序列确定二叉树的算法（5分）。 【烟台大学 2004 四、1(8分)】
答案:
第6章 树和二叉树
一、选择题 1.D 9.C 2.B 3.C 4.D 5.D 6.A 7.1C 7.2A 7.3C 7.4A 7.5C 8.B 20.D 32.B 43.B 55.C 65.D 10.D 11.B 12.E 13.D 14.D 15.C 16.B 17.C 18.C 19.B 21.A 22.A 23.C 24.C 25.C 26.C 27.C 28.C 29.B 30.C 31.D 33.A 34.D 35.B 36.B 37.C 38.B 39.B 40.B 41.1F 41.2B 42.C 44.C 45.C 46.B 47.D 48.B 49.C 50.A 51.C 52.C 53.C 54.D 56.B 57.A 58.D 59.D 60.B 61.1B 66.1C 66.2D 66.3F 66.4H 66.5I 61.2A 61.3G 62.B 63.B 64.D 部分答案解释如下。
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. √ 13.× 25.√ 37.√ 49.√ 14.√ 26.× 38.× 50.√ 15.× 27.× 39.× 16.× 28.× 40.× 5. √ 17.√ 29.√ 6. √ 18.√ 30.× 7.√ 8.× 9. √ 19.× 31.× 43.√ 20.√ 32.√ 44.× 21.× 33.× 45.√ 10.× 22.√ 34.× 46.× 11.× 23.× 35.× 47.× 12.× 24.× 36.√ 48.× 41.(3) 42.√ 部分答案解释如下。
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.平衡因子
k-1kH-1H
6. 9 7. 12 8.(1)2 (2)2-1 9.(1)2 (2)2-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
K+1k-2
14. N2+1 15.(1) 2-1 (2) k+1 16. ?N/2? 17. 2 18. 64 19. 99 20. 11 21.(1) n1-1 (2)n2+n3
k-2H-1H-1k-2
22.(1)2+1（第k层1个结点，总结点个数是2，其双亲是2/2=2）(2) ?log2i?+1 23.69
h-1
24. 4 25.3 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 58.(1) IF t=NIL THEN num:=0 ELSE num:=num(t^.l)+num(t^.r)+1 (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所述三点。二叉树不是树的特例。