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
(2) (n) (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.先序序列是“根左右”后序序列是“左右根”,可见对任意结点,若至多只有左子女或 至多只有右子女,均可使前序序列与后序序列相反,图示如下: 50题 52.按层次遍历,第一个结点(若树不空)为根,该结点在中序序列中把序列分成左石两部 分一左子树和右子树。若左子树不空,层次序列中第二个结点左子树的根;若左子精煙空, 则层次序列中第二个结点右子树的根。对右子树也作类似的分析。层次序列的特点是:从左
(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 题
到右每个结点或是当前情况下子树的根或是叶子 G山 (52)题图 (52)题(1) (52题(1)对应森林) 53.森林的先序序列和后序序列对应其转换的二叉树的先序序列和中序序列,应先据此构造 二叉树,再构造出森林。 54 53题森林 (54)题图 55. HIDJKEBLFGCA 56题图 56(1) 56(3) 57.M叉树的前序和后序遍历分别与它转换成的二叉树的先序和中序遍历对应。 58.前序遍历是“根左右”,中序遍历是“左根右”,后序遍历是“左右根”。若将“根”去 掉,三种遍历就剩“左右”。三种遍历中的差别就是访问根结点的时机不同。二叉树是递归 定义的,对左右子树均是按左右顺序来遍历的,因此所有叶子结点间的先后关系都是相同的 59.本题的核心是三种遍历的顺序:“根左右”-“左根右”-“左右根”,但对本题的解答必
到右每个结点或是当前情况下子树的根或是叶子。 53．森林的先序序列和后序序列对应其转换的二叉树的先序序列和中序序列，应先据此构造 二叉树，再构造出森林。 54． 55．HIDJKEBLFGCA 56. 57．M 叉树的前序和后序遍历分别与它转换成的二叉树的先序和中序遍历对应。 58．前序遍历是“根左右”，中序遍历是“左根右”，后序遍历是“左右根”。若将“根”去 掉，三种遍历就剩“左右”。三种遍历中的差别就是访问根结点的时机不同。二叉树是递归 定义的，对左右子树均是按左右顺序来遍历的，因此所有叶子结点间的先后关系都是相同的。 59．本题的核心是三种遍历的顺序：“根左右”-“左根右”-“左右根”，但对本题的解答必 I (52)题(1) A D B E C F G H (52)题图 A B D G E C F I H J (52 题(1)对应森林) E C A B D I G H F 53 题森林 F A E B C D H J G I K O L N MG (54)题图 A B D C E A B C D E 56 题图 A B C E D G I H F J K G 56 (2) A B C E D H I K F J L 56 (3) 1 3 2 4 8 5 6 7 56 (1) A B D K F C J E I H G