文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.
空指针数为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。
-（1-1）0
(2)证明：当i=1时，2=2=1，公式成立。设当i=n-1时公式成立，证明当i=n时公式仍成立。
设某叶子结点的层号为t，当将该结点变为内部结点，从而再增加两个叶子结点时，这两个叶子结点的层号都是t+1，对于公式的变化，是减少了一个原来的叶子结点，增加了两
-(t-1)-(t+1-1)-(t+1-1)
个新叶子结点，反映到公式中，因为2=2+2，所以结果不变，这就证明当i=n时公式仍成立。证毕．
h
30．结点数的最大值2-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 。 14 1 2 34． 13 16 该有向图只有一个顶点入度为0，其余顶点入度均为7 1， 3 15 8 0 它不是有向树。 35．题图 12 4 36．参见26题 9 5 6 11 10 6文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.
文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.
37．由于二叉树前序遍历序列和中序遍历序列可唯一确定一棵二叉树，因此，若入栈序列为1，2，3，…，n，相当于前序遍历序列是1，2，3，…，n，出栈序列就是该前序遍历对应的二叉树的中序序列的数目。因为中序遍历的实质就是一个结点进栈和出栈的过程，二叉树的形态确定了结点进栈和出栈的顺序，也就确定了结点的中序序列。
下图以入栈序列1，2，3，（解释为二叉树的前序序列）为例，说明不同形态的二叉树在中序遍历时栈的状态和访问结点次序的关系：
2 3 栈状态 访问 空 1 1 2 1 2 3 1 2 3 1 2 空 1 1 2 3 栈状态 访问 空 1 1 2 1 2 1 3 1 3 空 1 栈状态 访问 空 1 1 2 1 2 空 1 3 空 3 1 2 1 3 3 栈状态 访问 空 1 空 1 2 2 3 2 3 空 2 1 2 1 2 3 栈状态 访问 空 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，…，Sm}和{P1，P2，…，Pm-1}可以唯一确定右子树，从而也确定了二叉树。
若i=m,则Sm是根，这时二叉树的右子树为空，左子树的结点数是m-1，则{S1，S2，…，Sm-1}和{P1，P2，…，Pm-1}唯一确定左子树，从而也确定了二叉树。
最后，当1 A . 7文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持B C D E F G D A B E F H C 文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持. 由于后序遍历是“左子树—右子树—根结点”，所以{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．先序遍历二叉树的顺序是“根—左子树—右子树”，中序遍历“左子树—根—右子树”，后序遍历顺序是：“左子树—右子树―根＂，根据以上原则，本题解答如下： （１） 若先序序列与后序序列相同，则或为空树，或为只有根结点的二叉树 （２） 若中序序列与后序序列相同，则或为空树，或为任一结点至多只有左子树的二叉树． （３） 若先序序列与中序序列相同，则或为空树，或为任一结点至多只有右子树的二叉树． （４） 若中序序列与层次遍历序列相同，则或为空树， A 或为任一结点至多只有右子树的二叉树 B D 由中序序列DBEAFIHCG和后序序列DEBHIFGCA确定的二叉树略。 44. 森林转为二叉树的三步： E G C （１）连线（将兄弟结点相连，各树的根看作兄弟）； H F （２）切线（保留最左边子女为独生子女，将其它子女分枝切掉）； I KO （３）旋转（以最左边树的根为轴，顺时针向下旋转45度）。 J L 其实经过（１）和（２），已转为二叉树， M 执行（３）只是为了与平时的二叉树的画法一致。 P N 45．（1）①tree[p]·l→p ② tree[p]·r→p ③ p=0 O （2）框（A）移至Ⅲ处，成为前序遍历。 44题图 46. AA C (1) (2) 47. D EM H A A C BM F K BC B C B E I 48． （1） F G A J DEF （2）设二叉树的前序遍历序列为P1，P2，…，Pm，中序遍历序列为S1,S2,…，Sm。因为前D D E B H D 序遍历是“根左右”，中序遍历是“左根右”，则前序遍历序列中第一个结点是根结点（。nullJ (3) P1）K G G H I Si=P1,根据中序遍历时根结点将中序序列分成两部分的原则，有：L F 到中序序列中查询到 C E FGH 若L i=1，即S1=P1，则这时的二叉树没有左子树; 否则，S1,S2,…,Si-1是左子树的中G I (1) (2) 序遍历序列,用该序列和前序序列P2,P3，…，Pi去构造该二叉树的左子树。 H 若i=m,即Sm=P1,则这时的二叉树没有右子树; 否则,Si+1,Si+2,…，Sm是右子树的中 序遍历序列，用该序列和前序序列中Pi+1,Pi+2,…,Pm,去构造该二叉树的右子树。算法描述请参见下面算法设计第56题。 （3）若前序序列是abcd，并非由这四个字母的任意组合（4!=24）都能构造出二叉树。因 8文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持. 文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持. 为以abcd为输入序列，通过栈只能得到1/(n+1)*2n!/(n!*n!)=14 种，即以abcd为前序序列的二叉树的数目是14。任取以abcd作为中序遍历序列，并不全能与前序的abcd序列构成二叉树。例如：若取中序列dcab就不能。 该14棵二叉树的形态及中序序列略。 49．不能。因DABC并不是ABCD的合法出栈序列，参照第37、48（3）的解释。 50．先序序列是“根左右” 后序序列是“左右根”，可见对任意结点，若至多只有左子女或至多只有右子女，均可使前序序列与后序序列相反，图示如下： F C D 51． 52．按层次遍历，第一个结点（若树不空）为根，该结点在中序序列中把序列分成左右两部H A I 分—左子树和右子树。若左子树不空，层次序列中第二个结点左子树的根；若左子树为空，E G 则层次序列中第二个结点右子树的根。对右子树也作类似的分析。层次序列的特点是：从左50题 到右每个结点或是当前情况下子树的根或是叶子。 B A A 51题53．森林的先序序列和后序序列对应其转换的二叉树的先序序列和中序序列，应先据此构造C B E B 二叉树，再构造出森林。 A E G F D G F A K C E B C D H I 54． F I 53题森林 L A F G D N G H B H A 55．HIDJKEBLFGCA I A C B D J E H I 题(1)对应森林) J B MG (52O (52)题(1) 56. (52)H A 题图 A 1 B C 57．M叉树的前序和后序遍历分别与它转换成的二叉树的先序和中序遍历对应。 G C C B 2 5 K I B 58．前序遍历是“根左右”，中序遍历是“左根右”，后序遍历是“左右根”。若将“根”去C D D H D D F E G 6 掉，三种遍历就剩“左右”。三种遍历中的差别就是访问根结点的时机不同。二叉树是递归C J L 3 4 D I E E 定义的，对左右子树均是按左右顺序来遍历的，因此所有叶子结点间的先后关系都是相同的。 J E H K (54)I F 7 题图 E F 59．本题的核心是三种遍历的顺序：“根左右”-“左根右”-“左右根”，但对本题的解答必J G N在M 的左边，而8 须先定义结点间相互关系的“左右”。本解答中将N是M的左子女，当作K 56 (1) 56题图 N是M的右子女，当作N在M 的右边。若定义P是M和N的最近公共祖先，N在P的左子树56 (2) 56 (3) P的右子树中，称N在M 的左边，那时的答案是不一样的。中，M在 先根遍历时n先被访问 中根遍历时n先被访问 后根遍历时n先被访问 ? ? ? ? ? N在M的左边 N在M的右边 N是M的祖先 N是M的子孙 60．HIDJKEBLFGCA 61． A 62．后序遍历的顺序是“左子树—右子树—根结点”。因此，二叉树最左下的叶子结点是遍H B G C 历的第一个结点。下面的语句段说明了这一过程（设p是二叉树根结点的指针）。 if(p!=null) I L D E F {while (p->lchild!=null || p->rchild!=null) J K {while(p->lchild!=null) p=p->lchild; if(p->rchild!=null) p=p->rchild; } } return(p); //返回后序序列第一个结点的指针； 9文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持. 文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持. 63. 采用前序和后序两个序列来判断二叉树上结点n1必定是结点n2的祖先。 在前序序列中某结点的祖先都排在其前。若结点n1是n2的祖先,则n1必定在n2之前。而在后序序列中，某结点的祖先排在其后，即若结点n1是n2的祖先，则n1必在n2之后。根据这条规则来判断若结点n1在前序序列中在n2之前，在后序序列中又在n2之后，则它必是结点n2的祖先。 64.(1) （2） 前序序列：ABCEDFHGIJ （3）后序线索树 null中序序列：ECBHFDJIGA AA后序序列：ECHFJIGDBA BB65. 最后一个递归调用语句所保留的参数没有意义。这类递归因其在算法最后，通常被称为C“尾递归”， 可不用栈且将其（递归）消除。 如中序遍历递归算法中，最后的递归语句DDCinorder (bt->rchild)可改为下列语句段： nullFEGEGbt=bt->rchild; Fwhile (bt->rchild!=null) HIHI {inorder (bt ->lchild); printf(“%c”,bt ->data);//访问根结点，假定结点数据域为字符 JJbt=bt ->rchild; } 66.在二叉链表表示的二叉树中， 引入线索的目的主要是便于查找结点的前驱和后继。因为若知道各结点的后继，二叉树的遍历就变成非常简单。二叉链表结构查结点的左右子女非常方便，但其前驱和后继是在遍历中形成的。为了将非线性结构二叉树的结点排成线性序列， 利用结点的空链域，左链为空时用作前驱指针，右链为空时作为后继指针。再引入左右标记ltag 和rtag ，规定ltag=0，lchild 指向左子女,ltag=1时,lchild指向前驱；当rtag=0时 ,rchild指向右子女，rtag=1时，rchild 指向后继。这样，在线索二叉树（特别是中序线索二叉树）上遍历就消除了递归，也不使用栈（后序线索二叉树查后继仍需 要栈。） 67. K AE 67题(1) A BEL M N 68. （1）前序序列：ABDEHCFG AF G H B C （2）中序序列：DHEBAFCG O P KnullCFBCnullI J （3）后序序列：HEDBFGCA D 67题(2) 69.（1） DGIDGLF（2）BiTree INORDER-PRIOR(N,X) //在中序线索二叉树上查找结点N的前驱结点X {if(n->ltag==1){X=N->lchild; return (X);} ME后根遍历森林，结点序列为: J(3)Helse {p=N->lchild; BDCAIFJGHELOPMNK Hwhile (p->rtag==0) p=p->rchild; NO X=p;return(p);} } P70. AAA 71. AF nullC BCAB C 前序序列：ＡＢＣＥＤＦＨＧＩnullJ B nullBH I E 中序序列： E C B H F D J I G A BDEFD 71题（E3） FD 后序序列： ＥＣＨＦＪＩＧＤＢＡG DCDC72. 后序线索树中结点的后继，要么是其右线71题（2） nullEGHrtag=1时），要么是其双亲结点GFG索（当结点的H 70题（3） EGF右子树中最左下的叶子结点。所以，只有当二70题 （1）I70题 （2）HIIJHJI10文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持.