东北大学：《数据结构》课程教学资源（学习资料）第6章树和二叉树答案.doc_大学文库

第 6 章树和二叉树一、选择题 1.D 2.B 3.C 4.D 5.D 6.A 7.1C 7.2A 7.3C 7.4A 7.5C 8.B 9.C 10.D 11.B 12.E 13.D 14.D 15.C 16.B 17.C 18.C 19.B 20.D 21.A 22.A 23.C 24.C 25.C 26.C 27.C 28.C 29.B 30.C 31.D 32.B 33.A 34.D 35.B 36.B 37.C 38.B 39.B 40.B 41.1F 41.2B 42.C 43.B 44.C 45.C 46.B 47.D 48.B 49.C 50.A 51.C 52.C 53.C 54.D 55.C 56.B 57.A 58.D 59.D 60.B 61.1B 61.2A 61.3G 62.B 63.B 64.D 65.D 66.1C 66.2D 66.3F 66.4H 66.5I 部分答案解释如下。 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.平衡因子 8.(1)21(2)2-1 9.(1)2H(2)2-1 (3)H-LIog2NF1 10.用顺序存储二叉树时,要按完全二叉树的形式存储,非完全二叉树存储时,要加“虚结点”。设编号为i和j的结点在顺序存储中的下标为s和t,则结点i和j在同一层上的条件是L10g2 s hlog2tl 11. Llogai hlog2jj (1)0(2)(n-1)/2(3)(m+1)/2(4) Logan」+1 13 14.N2+1 15.(1)221-1(2)k+1 21.(1)n1-1(2)n2+n3 22.(1)2+1(第k层1个结点,总结点个数是2,其双亲是21/2=22)(2)Llog2i+1 23.69 24.4 25.3 27.「1og2kh1 28.(1)完全二叉树(2)单枝树,树中任一结点(除最后一个结点是叶子外),只有左子女或只有右子女。 29.N+130.(1)128(第七层满,加第八层1个)(2)7 1.0至多个。任意二叉树,度为1的结点个数没限制。只有完全二叉树,度为1的结点个数才至多为1 33.(1)2(2)n-1(3)1(4)n 5)1(6)n-1 34(1)FEGHDCB ②2)BEF(该二叉树转换成森林,含三棵树,其第一棵树的先根次序是 BEF 35.(1)先序(2)中序 (1)EACBDGF (2)2 37.任何结点至多只有右子女的二叉树 38.(1)a(2)dbe(3)hfog39.(1).D.G.B.A.E.H.C.F.(2)..GD.B..HE.FCA 40. DGEBFCA 41.(1)5(2)略 42.二叉排序树 43.二叉树前序 45.(1)先根次序(2)中根次序46.双亲的右子树中最左下的叶子结点47.2 48.(n+1)/2 49.31(x的后继是经x的双亲y的右子树中最左下的叶结点) 0.(1)前驱(2)后 51.(1)1(2)y. Child(3)0(4)x(5)1(6)y(7)x(编者注:本题按中序线索化) 52.带权路径长度最小的二叉树,又称最优二叉树 54.(1)6(2)261 55.(1)80(2)001(不唯一)56.2no-1 57.本题①是表达式求值,②是在二叉排序树中删除值为x的结点。首先查找x,若没有x, 则结束。否则分成四种情况讨论:x结点有左右子树:只有左子树:只有右子树和本身是叶 (1)Postoder eval(t' Lchild)(2) Postorder eval(t. Rchild) (3) ERROR ELie 算符)(4)A (5)tempA Lchild(6)tempA=NULL (7)q Rchild( 8) (9)tempA. Rchild

三.填空题 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 个结点，总结点个数是 2 H-1，其双亲是 2 H-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^.ItemNIL) 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)(iB[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->flag==0 (2)*x=bt (3) *x=node->right 四.应用题 1.树的孩子兄弟链表表示法和二叉树二叉链表表示法,本质是一样的,只是解释不同也就是说树(树是森林的特例,即森林中只有一棵树的特殊情况)可用二叉树唯一表示,并可使用二叉树的一些算法去解决树和森林中的问题。树和二叉树的区别有三:一是二叉树的度至多为2,树无此限制:二是二叉树有左右子树之分,即使在只有一个分枝的情况下,也必须指出是左子树还是右子树,树无此限制三是二叉树允许为空,树一般不允许为空(个别书上允许为空)。 2.树和二叉树逻辑上都是树形结构,区别有以上题1所述三点。二叉树不是树的特例。 3.线性表属于约束最强的线性结构,在非空线性表中,只有一个“第一个”元素,也只有一个“最后一个”元素:除第一个元素外,每个元素有唯一前驱;除最后一个元素外, 每个元素有唯一后继。树是一种层次结构,有且只有一个根结点,每个结点可以有多个子女但只有一个双亲(根无双亲),从这个意义上说存在一(双亲)对多(子女)的关系。广义表中的元素既可以是原子,也可以是子表,子表可以为它表共享。从表中套表意义上说,广义表也是层次结构。从逻辑上讲,树和广义表均属非线性结构。但在以下意义上,又蜕变为线性结构。如度为1的树,以及广义表中的元素都是原子时。另外,广义表从元素之间的关系可看成前驱和后继,也符合线性表,但这时元素有原子,也有子表,即元素并不属于同数据对象。 4.方法有二。一是对该算术表达式(二叉树)进行后序遍历, 得到表达式的后序遍历序列,再按后缀表达式求值;二是递归求出左子树表达式的值,再递归求出右子树表达式的值,最后按根结点运算符(+、-、*、/等)进行最后求值 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)式可写为由(1)、(3)得n2=n0-1,代入(1),并由(1)和(2)得B=2*(n0-1)。证毕。 8.(1)k(h为层数) (2)因为该树每层上均有K个结点,从根开始编号为1,则结点i的从右向左数第2个孩子的结点编号为ki。设n为结点i的子女,则关系式(i-1)k+21)的前一结点编号为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应满足2<n<=2-1关系式。解

+ + * + f g h + * a b c + d e 可换) 80．（1）node->rflag==0 (2)*x=bt (3) *x=node->right 四．应用题 1．树的孩子兄弟链表表示法和二叉树二叉链表表示法，本质是一样的，只是解释不同，也就是说树（树是森林的特例，即森林中只有一棵树的特殊情况）可用二叉树唯一表示，并可使用二叉树的一些算法去解决树和森林中的问题。树和二叉树的区别有三：一是二叉树的度至多为 2，树无此限制；二是二叉树有左右子树之分，即使在只有一个分枝的情况下，也必须指出是左子树还是右子树，树无此限制；三是二叉树允许为空，树一般不允许为空（个别书上允许为空）。 2.树和二叉树逻辑上都是树形结构，区别有以上题 1 所述三点。二叉树不是树的特例。 3．线性表属于约束最强的线性结构，在非空线性表中，只有一个“第一个”元素，也只有一个“最后一个”元素；除第一个元素外，每个元素有唯一前驱；除最后一个元素外，每个元素有唯一后继。树是一种层次结构，有且只有一个根结点，每个结点可以有多个子女，但只有一个双亲（根无双亲），从这个意义上说存在一（双亲）对多（子女）的关系。广义表中的元素既可以是原子，也可以是子表，子表可以为它表共享。从表中套表意义上说，广义表也是层次结构。从逻辑上讲，树和广义表均属非线性结构。但在以下意义上，又蜕变为线性结构。如度为 1 的树，以及广义表中的元素都是原子时。另外，广义表从元素之间的关系可看成前驱和后继，也符合线性表，但这时元素有原子，也有子表，即元素并不属于同一数据对象。 4．方法有二。一是对该算术表达式（二叉树）进行后序遍历，得到表达式的后序遍历序列，再按后缀表达式求值；二是递归求出左子树表达式的值，再递归求出右子树表达式的值，最后按根结点运算符（+、-、*、/ 等）进行最后求值。 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）因为该树每层上均有 K h-1 个结点，从根开始编号为 1，则结点 i 的从右向左数第２个孩子的结点编号为 ki。设 n 为结点 i 的子女，则关系式(i-1)k+21)的前一结点编号为 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 应满足 2 h-1 <n<=2h -1 关系式。解

此不等式,并考虑h是整数,则有 h=logn}1,即任一结点个数为n的二叉树的高度至少为0(logn)。 10.2-1(本题等价于高度为n的满二叉树有多少叶子结点,从根结点到各叶子结点的单枝树是不同的二叉树。) 11.235。由于本题求二叉树的结点数最多是多少,第7层共有2=64个结点,已知有10 个叶子,其余54个结点均为分支结点。它在第八层上有108个叶子结点。所以该二叉树的结点数最多可达(2-1+108)=235。(注意;本题并未明说完全二叉树的高度,但根据题意, 只能8层。 12.1023(=2-1) 13.证明:设度为1和2的结点数是n和n2,则二叉树结点数n为n=m+n1+n2 由于二叉树根结点没有分枝所指,度为1和2的结点各有1个和2个分枝,度为0的结点没有分枝,故二叉树的结点数n与分枝数B有如下关系 n=B+1=n1+2*n2+1…………… 由(1)和(2),得n2=m-1。即n个结点的二叉树,若叶子结点数是m,则非叶子结点中有(m-1)个度为2,其余度为1。 14.根据顺序存储的完全二叉树的性质,编号为i的结点的双亲的编号是Li/2J,故A[i]和 A[j的最近公共祖先可如下求出: while(i/21=j/2) if(i>j)i=1/2: e1 退出 while后,若i/2=0,则最近公共祖先为根结点,否则最近公共祖先是i/2。 15.N个结点的K叉树,最大高度N(只有一个叶结点的任意k叉树)。设最小高度为H,第 i(1<=i<=H)层的结点数K,则N=1+k+k2+…+k,由此得 H=Llogs(N(K-1)+1) 16.结点个数在20到40的满二叉树且结点数是素数的数是31,其叶子数是16。 17.设分枝结点和叶子结点数分别是为n4和n0,因此有n=n+n4 另外从树的分枝数B与结点的关系有n=B+1=K*n+1 由(1)和(2)有n=n-nk=(n(K-1)+1)/K 18.用顺序存储结构存储n个结点的完全二叉树。编号为i的结点,其双亲编号是Li/2」(i=1 时无双亲),其左子女是2i(若2i<=n,否则i无左子女),右子女是2i+1(若2i+1<=n,否则无右子女)。 19.根据完全二叉树的性质,最后一个结点(编号为n)的双亲结点的编号是Ln/2,这是最后一个分枝结点,在它之后是第一个终端(叶子)结点,故序号最小的叶子结点的下标是 20.按前序遍历对顶点编号,即根结点从1开始,对前序遍历序列的结点从小到大编号 21.设树的结点数为n,分枝数为B,则下面二式成立 n=no+n+n2+…+na n=B+1=n1+2n2+…+mn (2) 由(1)和(2)得叶子结点数n=1+=1 22.「1ogn1+1 24.该结论不成立。对于任一aeA,可在B中找到最近祖先f。a在f的左子树上。对于从f 到根结点路径上所有beB,有可能f在b的右子树上,因而a也就在b的右子树上,这时 b,因此a<b不成立。同理可以证明b<c不成立。而对于任何a∈A,c∈C均有a<c

此不等式，并考虑 h 是整数，则有 h=logn+1，即任一结点个数为 n 的二叉树的高度至少为 O(logn)。 10．2 n -1(本题等价于高度为 n 的满二叉树有多少叶子结点，从根结点到各叶子结点的单枝树是不同的二叉树。) 11．235。由于本题求二叉树的结点数最多是多少，第 7 层共有 2 7-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)层的结点数 K i-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) 由(1)和(2)得叶子结点数 n0=1+ = − m i i 1 ni ( 1) 22. log2n +1 23.15 24. 该结论不成立。对于任一 a€A,可在 B 中找到最近祖先 f。a 在 f 的左子树上。对于从 f 到根结点路径上所有 b€B，有可能 f 在 b 的右子树上，因而 a 也就在 b 的右子树上，这时 a ＞b，因此 a＜b 不成立。同理可以证明 b<c 不成立。而对于任何 a∈A,c∈C 均有 a<c

25.n个结点的m次树,共有n*m个指针。除根结点外,其余n-1个结点均有指针所指,故空指针数为n*m(m-1)=n*(m-1)+1。证毕。 26.证明设度为1和2及叶子结点数分别为no,n1和n2,则二叉树结点数n为n=no+n1+n2 (1) 再看二叉树的分支数,除根结点外,其余结点都有一个分支进入,设B为分支总数,则 n=B+1。度为1和2的结点各有1个和2个分支,度为0的结点没有分支,故n=n1+2n2+1 由(1)和(2),得no=n2+1 27.参见题26 28.设完全二叉树中叶子结点数为n,则根据完全二叉树的性质,度为2的结点数是n-1, 而完全二叉树中,度为1的结点数至多为1,所以具有n个叶子结点的完全二叉树结点数是 n+(n-1)+1=2n或2n-1(有或无度为1的结点)。由于具有2n(或2n-1)个结点的完全二叉树的深度是Llog2(2n)1(Llog2(2n-1)+1,即「ogn+1,故n个叶结点的非满的完全二叉树的高度是「og2n+1。(最下层结点数>=2)。 29.(1)根据二叉树度为2结点个数等于叶子结点个数减1的性质,故具有n个叶子结点且非叶子结点均有左左子树的二叉树的结点数是2n-1。 (2)证明:当i=1时,2(1)=2°=1,公式成立。设当i=n-1时公式成立,证明当i时公式仍成立设某叶子结点的层号为t,当将该结点变为内部结点,从而再增加两个叶子结点时,这两个叶子结点的层号都是t+1,对于公式的变化,是减少了一个原来的叶子结点,增加了两个新叶子结点,反映到公式中,因为2)=2+22,所以结果不变,这就证明当i=n 时公式仍成立。证毕 30.结点数的最大值2-1(满二叉树),最小值2h-1(第一层根结点,其余每层均两个结点)。 31.(1)ku-1)+1+i(2)L(v-2)/k1(参见第8题推导) 32.该二叉树是按前序遍历顺序编号,以根结点为编号1,前序遍历的顺序是“根左右”。 33.(1)设n=1,则e=0+2*1=2(只有一个根结点时,有两个外部结点),公式成立设有n个结点时,公式成立,即 E=I (1) 现在要证明,当有n+1个结点时公式成立。增加一个内部结点,设路径长度为1,则 In+=In+I 该内部结点,其实是从一个外部结点变来的,即这时相当于也增加了一个外部结点(原外部结点变成内部结点时,增加两个外部结点),则 =En+1+2 由(1)和(2),则(3)推导为 =In+2n+1+2=In-1+2n+1+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

25. n 个结点的 m 次树，共有 n*m 个指针。除根结点外，其余 n-1 个结点均有指针所指，故空指针数为 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．结点数的最大值 2 h -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． 1 3 15 2 11 14 12 13 10 5 6 4 9 8 7 16 0

该有向图只有一个顶点入度为0,其余顶点入度均为1, 它不是有向树 35.题图 36.参见26题 37.由于二叉树前序遍历序列和中序遍历序列可唯一确定一棵二叉树,因此,若入栈序列为 1,2,3,…,n,相当于前序遍历序列是1,2,3,…,n,出栈序列就是该前序遍历对应的二叉树的中序序列的数目。因为中序遍历的实质就是一个结点进栈和出栈的过程,二叉树的形态确定了结点进栈和出栈的顺序,也就确定了结点的中序序列。下图以入栈序列1,2,3,(解释为二叉树的前序序列)为例,说明不同形态的二叉树在中序遍历时栈的状态和访问结点次序的关系: 栈状态访问栈状态访问栈状态访问栈状态访问栈状态访问空 l111 123 12 38.给定二叉树结点的前序序列和对称序(中序)序列,可以唯一确定该二叉树。因为前序序列的第一个元素是根结点,该元素将二叉树中序序列分成两部分,左边(设1个元素)表示左子树,若左边无元素,则说明左子树为空;右边(设r个元素)是右子树,若为空,则右子树为空。根据前序遍历中“根一左子树一右子树”的顺序,则由从第二元素开始的个结点序列和中序序列根左边的1个结点序列构造左子树,由前序序列最后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,…

该有向图只有一个顶点入度为 0，其余顶点入度均为 1，它不是有向树。 35．题图 36．参见 26 题 37．由于二叉树前序遍历序列和中序遍历序列可唯一确定一棵二叉树，因此，若入栈序列为 1，2，3，…，n，相当于前序遍历序列是 1，2，3，…，n，出栈序列就是该前序遍历对应的二叉树的中序序列的数目。因为中序遍历的实质就是一个结点进栈和出栈的过程，二叉树的形态确定了结点进栈和出栈的顺序，也就确定了结点的中序序列。下图以入栈序列 1，2，3，（解释为二叉树的前序序列）为例，说明不同形态的二叉树在中序遍历时栈的状态和访问结点次序的关系：栈状态访问空 1 1 2 1 2 3 1 2 3 1 2 空 1 栈状态访问空 1 1 2 1 2 1 3 1 3 空 1 栈状态访问空 1 1 2 1 2 空 1 3 空 3 栈状态访问空 1 空 1 2 2 3 2 3 空 2 栈状态访问空 1 空 1 2 空 2 3 空 3 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，…， 1 3 2 1 3 2 1 2 3 2 1 3 2 1 3

Sm}和{1,P2,…,Pm-1}可以唯一确定右子树,从而也确定了二叉树若i=m,则Sm是根,这时二叉树的右子树为空,左子树的结点数是m1,则{S1,S2, Sm-l1}和{P1,P2,…,Pm-l}唯一确定左子树,从而也确定了二叉树。最后,当1<i<m时,Si把中序序列分成{S1,S2,…,Si-1}和{Si+1,Si+2, 由于后序遍历是“左子树一右子树一根结点”,所以{P1,P2,…,Pi-1}和{Pi,Pi+1,…Pm-1 是二叉树的左子树和右子树的后序遍历序列。因而由{S1,S2,…,Si-l和{Pl,P2,…, Pi-1} 可唯一确定二叉树的左子树,由{Si+1,Si+2,…,Sm}和 {Pi,Pi+1,…,Pm1}可唯一确定二叉树的右子树由中序序列 DBEAFGC和后序序列 DEBGFCA构造的二叉树如右图: 41.证明请参见第40题和第38题第40题图第41题图由前序序列 ABDGECFH和中序序列 DGBEAFHC构造的二叉树如图 42.参见第38题 43.先序遍历二叉树的顺序是“根一左子树一右子树”,中序遍历“左子树一根一右子树”, 后序遍历顺序是:“左子树一右子树一根”,根据以上原则,本题解答如下: (1)若先序序列与后序序列相同,则或为空树,或为只有根结点的二叉树 (2)若中序序列与后序序列相同,则或为空树,或为任一结点至多只有左子树的二叉树 (3)若先序序列与中序序列相同,则或为空树,或为任一结点至多只有右子树的二叉树 (4)若中序序列与层次遍历序列相同,则或为空树, 或为任一结点至多只有右子树的二叉树由中序序列 DBEAFIHCG和后序序列 DEBHIFGCA确定的二叉树略 44.森林转为二叉树的三步 (1)连线(将兄弟结点相连,各树的根看作兄弟) (2)切线(保留最左边子女为独生子女,将其它子女分枝切掉) (3)旋转(以最左边树的根为轴,顺时针向下旋转45度)。其实经过(1)和(2),已转为二叉树, 执行(3)只是为了与平时的二叉树的画法一致。 45.(1)① tree Lp]·l→p② treeS]·r→p③p=0 (2)框(A)移至Ⅲ处,成为前序遍历。 44题图 B

Sm}和{P1，P2，…，Pm-1}可以唯一确定右子树，从而也确定了二叉树。若 i=m,则 Sm 是根，这时二叉树的右子树为空，左子树的结点数是 m-1，则{S1，S2，…， Sm-1}和{P1，P2，…，Pm-1}唯一确定左子树，从而也确定了二叉树。最后，当 1<i<m 时，Si 把中序序列分成{S1，S2，…，Si-1}和{Si+1,Si+2,…，Sm}。由于后序遍历是“左子树—右子树—根结点”，所以{P1,P2,…,Pi-1}和{Pi,Pi+1,…Pm-1} 是二叉树的左子树和右子树的后序遍历序列。因而由{S1，S2，…，Si-1}和{P1，P2，…， Pi-1} 可唯一确定二叉树的左子树，由{Si+1,Si+2,…，Sm}和 {Pi,Pi+1,…，Pm-1}可唯一确定二叉树的右子树。由中序序列 DBEAFGC 和后序序列 DEBGFCA 构造的二叉树如右图： 41．证明请参见第 40 题和第 38 题第 40 题图第 41 题图由前序序列 ABDGECFH 和中序序列 DGBEAFHC 构造的二叉树如图： 42．参见第 38 题 43．先序遍历二叉树的顺序是“根—左子树—右子树”，中序遍历“左子树—根—右子树”，后序遍历顺序是：“左子树—右子树―根＂，根据以上原则，本题解答如下：（１）若先序序列与后序序列相同，则或为空树，或为只有根结点的二叉树（２）若中序序列与后序序列相同，则或为空树，或为任一结点至多只有左子树的二叉树．（３）若先序序列与中序序列相同，则或为空树，或为任一结点至多只有右子树的二叉树．（４）若中序序列与层次遍历序列相同，则或为空树，或为任一结点至多只有右子树的二叉树由中序序列 DBEAFIHCG 和后序序列 DEBHIFGCA 确定的二叉树略。 44. 森林转为二叉树的三步：（１）连线（将兄弟结点相连，各树的根看作兄弟）；（２）切线（保留最左边子女为独生子女，将其它子女分枝切掉）；（３）旋转（以最左边树的根为轴，顺时针向下旋转 45 度）。其实经过（１）和（２），已转为二叉树，执行（３）只是为了与平时的二叉树的画法一致。 45．（1）①tree[p]·l→p ② tree[p]·r→p ③ p=0 （2）框（A）移至Ⅲ处，成为前序遍历。 44 题图 46. A B D C E F G B D C E F H A G A BM F D (3) C EM H G H G D A C J I B F E M P O N KO L A D E B C F G H A D E B C F G H null

(1) (2) 47. 48．（1）（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．先序序列是“根左右” 后序序列是“左右根”，可见对任意结点，若至多只有左子女或至多只有右子女，均可使前序序列与后序序列相反，图示如下： 51． 52．按层次遍历，第一个结点（若树不空）为根，该结点在中序序列中把序列分成左右两部分—左子树和右子树。若左子树不空，层次序列中第二个结点左子树的根；若左子树为空，则层次序列中第二个结点右子树的根。对右子树也作类似的分析。层次序列的特点是：从左 (1) A K B C H D G E L F J I (2) E A B L D G H I C K J F A I B D C E H F G 51 题图 F E C I A B G D H 50 题

东北大学：《数据结构》课程教学资源（学习资料）第6章 树和二叉树答案

东北大学：《数据结构》课程教学资源（学习资料）第6章树和二叉树答案