第七章和第八章补充练习题(答案).docx

73补充练习题及参考答案7 .3.1单项选择题1.对于一棵具有n个结点、度为4的树来说,.A.树的高度最多是n-38 .树的高度最多是是n-4C.第i层上最多有4(iT)个结点D.至少在某一层上正好有4个结点答:这样的树中至少有一个结点而旋为4,也就是说,至少有一层中有4个或以上的结点，因此树的高度最多是展3。本题的答案为A。2.度为4、高度为h的树.A.至少有h+3个结点B.最多有4厂1个结点C.最多有4h个结点D.至少有h+4个结点答：与上小题分析相同,本题的答案为Ao3 .对于一棵具有n个结点、度为4的树来说,树的高度至少是.A. log4(2zz)B. Dog4On-I)C. log4(3n÷l)D. 11og4(2n+l)答：由树的性质4可知,具有n个结点的m次树的最小高度为log",5(m-l)+l)。这里m=4,因此最小高度为log,。"+DIo本题的答案为Co4 .在一棵3次树中度为3的结点数为两个,度为2的结点数为一个,度为1的结点数为两个,则度为0的结点数为个。.4B.5C.6D.7答：H3=2,zl2=i,n=2,n=n3+n2+nx+n0=5+%,n二度之和+1=3%+2%+%+1=11,所以0=11-5=6。本题的答案为配5 .若一棵有n个结点的树,其中所有分支结点的度均为k,该树中的叶子结点个数是oA.n(k-1)/kB.n-kC.(n+l)kD.(nk-n+l)k答:m=k,有人。+3度之和=nT=S,%=ST"攵所以11o=n-nk=n-(n-l)k=(nk-n+l)/k.本题的答案为D06 .若3次树中有a个度为1的结点、b个度为2的结点、C个度为3的结点,则该树有个叶子结点。A.l+2b÷3cB.l+2b+3cC.2b-3cD.l+b+2c:n=w°+w1÷w2+=11°+a+b+c,n=度之和+1=%+2%+2%+l=a+2b+3c+l,所以，%=8+2c+l,总结点数n=a+2b+3c+l0本题的答案为D7 .假设每个结点值为单个字符,而一棵树的层次遍历序列为Abcdefghij,则其根结点的值是.A.AB.BC.JD.以上都不对答:树的层次遍历过程中访问的第一个结点是根结点,本题的答案为A8 .用双亲存储结构表示树,其优点之一是比较方便.A.找指定结点的双亲结点9 .找指定结点的孩子结点C.找指定结点的兄弟结点D.判断某结点是不是叶子结点答:A。10 用孩子链存储结构表示树,其优点之一是比较方便。A.判断两个指定结点是不是兄弟B.找指定结点的双亲C.判断指定结点在第几层D.计算指定结点的度数答:在树的孩子链存储结构中,每个结点有指向所有孩子结点的指针,所以很容易计算其孩子结点个数(度数)。本题的答案为D10. 一棵度为10、结点个数为m(n>100)的树采用孩子链存储结构时,其中非空指针域数占总指针域数的比例约为.A.5%B.10%C.20%D.50%答:在度为10树的孩子链存储结构中,每个结点的指针域个数为10,共有IOn个指针域,其中非空的指针域个数等于分支数,即n-l,其余为空指针域,所以非空指针域数占总指针域数的比例二(n-l)(10n)10%o本题的答案为B011 .如果在树的孩子兄弟链存储结构中有6个空的左指针域,7个空的右指针域,5个结点数、右指针域都为空,则该树中叶子结点的个数.A.有7个B.有6个C.有5个I).不能确定答:在树的孩子兄弟链存储结构中,左指针域指向第一个孩子结点,右指针域指向右兄弟结点。该树有6个空的左指针域,说明有6个结点没有任何孩子,则为叶子结点。本题的答案为B12 .有一棵3次树,其中%=2,=2,n1=1,当该数采用孩子兄弟链存储结构时，其中非空指针域数占总指针域数的比例约为.A.10%B.45%C,70%D.90%答:m=3,11=w0+w1+n2+n3=n0+5,三n-l=1+22+3¾=ll,所以非空指针域数占总指针域个数为24.指向孩子或者兄弟的非空指针域个数二n-11,所以非空指针域数占总指针域个数的比例=I1/24=45%.本题的答案为B013 .设森林F中有3棵树,第一、第二和第三课数的结点个数分别为犯、也和巧。与森林F对应的二叉树根结点的右子树上的结点个数是A“tn+m2©叫D加2+m3答:对应的二叉树根结点的右子树上的结点均由第二和第三棵树上的结点转换得到本题的答案为D.14 .设F是一个森林,B是由F变换的二叉树。若F中有In个分支结点,则B中右指针域为空的结点有个。A.m-lB.mC.m+1D.m+2答:F中的每个分支结点都有一个最右孩子结点,这个最右孩子结点在B中右指针域为空，同时根结点的右指针域也为空,所以B中共有m÷l个右指针域为空的结点。本题的答案为C.15.设森林F对应的二叉树为B,它有m个结点,B的根为p,p的右子树结点个数为n,森林F中第一棵树的结点个数是.A.m-nB.m-n-1C.n+1D.条件不足,无法确定答:森林林F中的第一棵树转换成二叉树p及p的左子树。本题的答案为A016 .如果将一棵有序树T转换为二叉树B,那么T中结点的先根遍历序列就是B中结点的序列。A.先序B.中序C.后序D.层次序答:若树T的根为N,它的子树为几百，?其先根序列为NTGF。树T转换成二叉树B的过程如图7.7所示口转换为以），为N的左子树中结点，纥的所有结点都在用根结点的右子树中,T的邛分工序列在B中遍历过程是先根结点、再左子树,对应B的先序序列。本题的答案为A.17 .如果将一棵有序树T转换为二叉树B,那么T中结点的后根遍历序列就是B中结点的序列。A.先序B.中序C.后序D.层次序答:若树T的根为N,它的子树为TKTz、Tln,其后根序列为Trr2TmNo树T转换成二叉树B的过程如图7.7所示（I,转换为Bi）,Bl为N的左子树中结点,B2、Bn的所有结点都在Bl根结点的右子树中,T的T1T2TmN序列在B中遍历过程是先左子树,再根结点。又显然不会是B的后序序列，因为在B的后序遍历中,B2中结点会在Bl根结点之前访问,所以只能是B的中序序列。本题的答案为B18 .如果将一棵有序树T转转换为二叉树B,那么T中结点的层次序列对应B的一序列.A.先序遍历B.中序遍历C.层次遍历D.以上都不对答：由于T中的兄弟变为B中的右孩子,改变为父子关系,所以以T中结点的层次序列与B的先序、中序、后序和层次序列都没有对应关系。本题的答案为D19 .二叉树若用顺序方法存储,则下列4种运算中最容易实现.先序遍历历二叉树B.判判断两个结点值分别为x、y的结点是不是在同一层上C.层次遍历二叉树D.求结点值为X的结点的所有孩子答:直接顺序扫描存储二叉树的数组即得到层次遍历二叉树序列。本题的答案为C20.二叉树和度为2的树的相同之处包括.A.每个结点都有一个或两个孩子结点B.至少有一个根结点C.至少有一个度为2的结点D.每个结点最多只有一个双亲结点答:D。二叉树树和度为2的树都属于树形结构,其中每个结点最多只有一个双亲结点.21 .一棵完全二叉树上有1001个结点,其中叶子结点的个数是.A.250B.501C.254D.505答：由二叉树的性质知%-1,且完全二叉树的尸0或1；己知二叉树的总结点数=%+%+%,即有=2%+%-1；将总结点数m=OOi代入得I(X)I=2%+%-1,因101为奇数,故ni=o,得到no=501o本题的答案为Bo22 .一棵有124个叶子结点的完全二叉树最多有个结点。A.247B.248C.249D.250答：由。二%+1可知n2=123;=2+%+0=247+,在完全二叉树中，口1二0或1,所以n的最大值为247+1=248,故选B23 .在一棵具有n个结点的完全二叉树中，分支结点的最大编号为.A.15+1)/2b.1ST)/?c./21I).1./2答：D.24 .在高度为h的完全二叉树中，A.度为0的结点都在第h层上B.第i(IWiWh)层上结点都是度为2的结点C.第(IWiWhT)层上有N"个结点D.不存在度为1的结点答:在高度为h的元全二叉树中，第1层第h-1层构成一个满二叉树,在满二叉树中第i层上有2'“个结点。本题的答案为C25.每个结点的度或者为O或者为2的二叉树称为正则二叉树,对于n个结点的正则二叉树来说,它的最大高度是A.睡21B.(n-l)2c.地2(一1)1D.(n÷l)2答：最大高度的正则二叉树是这样的二叉树,第1层有一个结点,第2层第h层均有两个结点,因此2(hT)+l=n,即h=(n+l)2o本题的答案为Do26 .若一棵二叉树具有10个度为2的结点、5个度为1的结点,则度为0的结点个数是.A.9B.11C.15D.不确定答:n2=10,no=n2+l=ll,本题的答案为B27 .若二叉树的中序序列是abcdef,且c为根结点,则A.结点C有两个孩子B.二叉树有两个度为。的的结点C.二叉树的高度为5D.以上都不对答：中序序列是abcdef,则ab为结点C的左子树的中序序歹I1.def为结点C的右子树的中序序列,说明结点c既有左子树又有右子树。本题的答案为A028 .在任何一棵二叉树中，如果结点a有左孩子b、右孩子c,则在结点的先序序列、中序序列、后序序列中,.A.结点b一定在结点a的前面B.结点b一定在结点C的前面C.结点a一定在结点C的前面D.结点a一定在结点b的前面答:在先序遍历、中序遍历和后序遍历中都是先遍历左子树,再遍历右子树,所以结点b一定在结点C的前面访问。本题的答案为B29 .如果一棵二叉树的先序序列是ab，中序序列是ba，则.A.结点a和结点b分别在某结点的左子树和右子树中B.结点b在结点a的右子树中C.结点b在结点a的左子树中D.结点a和结点b分别在某结点的两棵非空子树中答:先序序列是ab,贝IIb在a的左子树中或者b在a的某个祖先X的右子树中，中序序列是ba，则b不可在a的某个祖先X的右子树中，即b只能在a的左子树中。本题的答案为C30.设a、b为一棵二叉树上的两个结点,在中序序列时,a在b之前的条件是A.a在b的右方B.a是b的祖先C.a在b的左方D.a是b的子孙答:中序遍历时,先遍历左子树,再访问根结点,最后遍历右子树。a在b前,则a在b的左子树中或b在a的右子树中，或者a在某棵子树的左子树中而b在其右子树中,这都表示a在b的左方。本题的答案为C。31.如果在一棵二叉树的先序序列、中序序列和后序序列中，结点a、b的位置都是a在前、b在后（即形如ab），则.A.a、b可能是兄弟B.a可能是b的双亲C.a可能是b的的孩子D.不存在这样的二叉树答：图7.8所示的二叉树中a和b结点就满足本题的条件。本题的答案为A。32 .若二叉树树采用二叉链存储结构,如果要交换其所有分支结点的左、右子树位置,利用遍历方法最合适。A.先序B.中序C.后序D.按层次答:先对根结点的左、右子树进行交换,再交换根结点的左、右指针值,这是后序遍历的思路。本题的答案为C.33 .关于非空二叉树的后序序列以下说法正确的是.后序序列的最后一个结点是根结点B.后序序列的最后一个结点一定是叶子结点C.后序序列的第一个结点一定是叶子结点D.以上都不对答:A34 .某二叉树的先序序列和后序序列正好相反,则该二叉树一定是.A.空或只有一个结点B.完全二叉树C.二叉排序树D.高度等于其结点数答:二叉树的先序序列是N1.R（N为根结点,1.为左子树,R为右子树），后序序列1.RN,要使N1.R=NR1.,则1.为空或R为空,这样的二叉树每层只有一个结点，即高度等于其结点数。本题题的答案为D。35 .若一棵二叉树的先序序列和后序遍历分别是1、2、3、4和4、3、2、1,则该二叉树的中序序列不会是.A.1、2、3、4B.2、3、4、1C.3、2、4、1D.4、3、2、1答:将先序序列1、2、3、4与某个中序序列构造出一棵二叉树,再看其后序序列是否为4、3、2、1。当选项为C时,构造出的二叉树的后序序列为3、4、2、1。本题的答案为C36 .某二叉树是由一个森林转换而来,其层次序列为Abcdefghi,中序序列为DGIBAEHCF,将其还原为森林,该森林是由棵树构成的.A.1B.2C.3D.无法确定答：由二叉树的层次序列和中序序列构造出唯一的二叉树,其中根结点有两个右下孩子,所以还原为森林后对应3棵树。本题的答案为C。37 .一棵二叉树的先序序列为ABCDEFG,它的中序序列可能是A.BDCFEGB.CBDEFGC.BCDEFGD.DACEFBG答:先序序列和中序序列可以确定一棵二叉树,这里由选项A、C和D的中序序列无法确定一棵二叉树。本题的答案为B.38 .在中序线索二叉树（带头结点）中,p结点的左子树为空的充要条件是A.p->lchiId=NU1.1.B.p->Itag=IC.p->Itag=I且p->lchiId=NU1.1.D.以上都不对答:B。在带头结点的中序线索二叉树中所有指针域非空,p->ltag=l表示左指针为线索，即原来右子数为空。39.在n个结点的线索二叉树中（不计头结点），线索的数目为.A.n-lB.nC.n+1D.2n答:n个结点的二叉树中有n÷l个空指针,它们都转化为存放线索,所以线索的数目为n+1。本题的答案为C40 .若度为m的哈夫曼树（其中只有度为m的结点和叶子结点）中,其叶子结点个数为n,则非叶子结点的个数为.A.n-1B."一C.1）/（帆-1）D/（加-1）|-1答:在度为m的哈夫曼树中，设度为m的结点个数为“%结点总数=n+"%所有结点度之和二结点总数一l=n+乙7（这样的哈夫曼树也是一棵树,满足“所有结点度之和二分支数二结点总数一,的特性），而所有结点度之和和二mX即11+11w-l=m×n,H,求出n,n=（n-l）/（m-l）。本题答案为C41 .设有13个值,用它们组成一棵哈夫曼树,则该哈夫曼树共有个结点A.13B.12C.26D.25答:具有n个叶子结点的哈夫曼树共有2mn-l个结点。本题的答案为D42 .根据使用频率为5个字符设计的哈夫曼编码不可能是A.111,110,10,01,00B.000,001,010,011,1C.100,11,10,1,0D.001,000,01,11,10答:在C中，100和10冲突,即一个结点既是叶子结点又是内部结点,哈夫曼树中不可能出现这种情况。本题的答案为C43.若查找表用树表示,其中有n个结点,查找一个元素所属集合的算法的时间复杂度.AO(log2?)0()c。(舟dO(71og211)答:A7. 3.2填空题1 .在树形结构的二元组表示中，如果,则称结点a和b是兄弟；如果称a是b的双亲,的孩子.答:a和b有相同的前驱结点a是b的前驱b是a2 .一棵度为2的树中,其结点个数最少为.答：3。一个度为2的结点有2个孩子,加上该结点本身,所以总结点个数最少为3o3 .设某棵树中结点值为单个字符,其后根遍历序列为ABCDEFGH,则根幺吉点值为答:G。4 .对一棵具有n个结点的非空树,其中所有度之和等于.答:nT5 .高度为h、度为m(m2)的树中最少有个结点,最多有个结点.tnb-1答：h+mT机-16 .一棵含有n个结点的k(k22)次树,可能达到的最大高度为最小高度为.答:nlog式唳-1)+1)。最大高度为这样的k次树:只有一层含有k个结点,其余各层均只有一个结点,此时高度为n-k÷lo最小高度为完全k次树,此时高度为RogK"(欠-1)+1)7 .若用孩子兄弟链存储结构来存储具有m个叶子结点、n个分支结点的树,则该存储结构中有个左指针域为空的结点,有个右指针域为空的结点。答:mn+1。在孩子兄弟链存储结构中，只有叶子结点没有孩子,其左指针域为空。每个分支结点一定有一个最右孩子,它是没有兄弟的,除此之外,根结点也是没有兄弟的，即有n÷l个结点没有兄弟,它们的右指针域为空。8.有3个结点的不同形态二叉树有棵。C彳答：5。含有n个结点的不同形态二叉树有，+12n.9 .在高度为h（h20）的的二叉树中最多有0个结点,最少有个结点答:2"-1（为满二叉树时结点最多）h（每层只有一个结点）10 .n个结点的二叉树的最大高度是Q,最小高度是.。答:n（每层只有一个结点）（为完全二叉树时高度最小）。11 .n个结点的二叉树中如果有m个叶子结点,则一定有个度为1的结点，个度为2的结点。答:n-2m+lmT。由二叉树的性质1可知0=%+l,即n2=no-l=m-l,n=no+nl+n2,则n1=n-no-m2=n-m-（m-1）=n-2m+1012 .己知二叉树有50个叶子结点,则该二叉树的总结点数最少是.答:99。结点个数最少的情况是第一层有一个结点,250层有两个结点,这样共有50个叶子结点,49个非叶子结点,总有99个结点。也可以这样推导：no=50,n2=50-l=49,n=no+nl+n2=99+nl,当nl=0时结点个数最少,此时为99.13 .一共8层的完全二叉树至少有Q个结点,具有100个结点的完全二叉树中结点的最大层数为.答:1287。8层完全二叉树具有最少结点的情况是前7层为满二叉树而第8层仅有一个结点，即为27-l+l=128o具有100个结点的完全二叉树的高度是固定的,h=Zz=Plog2（72+1）=Plog2101"|=7,而结点的最大层数恰好等于高度。14 .完全二叉树中结点个数为n（n>2）,按层序编号（根结点编号为1）,则编号最大的分支结点的编号为工,编号最小的叶子结点编号为第一数结相答:1.n/21.n/2+1。15 .一棵含有50个结点的完全二叉树中,第6层有个结点.答：16。该完全二叉树的高度/?=log2（+l）I=log251=6,第5层层是满的，共有25-1二31个结点,所以第6层有50-31=19个结点。16 .一棵含有n个结点的满二叉树有个度为1的结点,个分支结点和个叶子结点,该满二叉树的高度为°答:0伍/2bg2（n+）17 .在二叉树的顺序存储结构中,编号分别为i和j的的两个结点处在同一层的条件是.答:Iog2（i+I）=log2（j+1）1.编号为i的结点所在的层号为1叫4+1）18 .设F是由Tl、T2、T3三棵树组成的森林,与F对应的二叉树为B。已知T1、T2、T3的结点数分别为nl、n2和n3,则二叉树B的左子树中有0个结点，二叉树B的右子树中有个结点。答:nlTn2+n3。根据森林转化为二叉树的方法可知,根结点和左子树来源于森林的第一棵树,而其余的树都在根结点的右子树上。19 .对于高度为3的满二叉树B,将其还原为森林T,其中包含根结点的那棵树中有个结点答：420 .一棵树中结点a的第2个孩子为结点b,转换成二叉树后,a、b两结点的层次相差为答：221 .一棵二叉树的根结点为a,其中序序列的第一个结点是，其中序序列的最后一个结点是。答:a结点的最左下结点a结点的最右下结点。22 .若一个二叉树的叶子结点是其中序序列中的最后一个结点，则它必是该二叉树的序列中的最后一个结点。答:先序遍历。设结点b是中序序列中的最后一个结点,根结点是a,则b一定是a的最右下结点,在先序遍历中，以b为根结点的子树一定是最后遍历的,而b又是叶子结点,所以b必是该二叉树的先序序列中的最后一个结点。23 .在二叉树中结点a的右孩子为结点b,那么在后序序列中必有形式。答:ba。在后序遍历中,子树的根结点最后访问，当a结点的右子树遍历完后立即访问a.24 .二叉树中一个叶子结点a是其中序序列的第一个结点,则a结点一定是该二叉树的序列中的第一个结点。答:后序。a结点是中序序列的第一个结点,说明它是根结点的最左下结点。在后序遍历中，以a为根结点的子树一定是最先遍历的,而它是叶子结点,没有右孩子,所以也一定是后序序列的第一个结点。25 .设一棵完全二叉树（每个结点值为单个字符）的顺序存储结构中存储数据元素为abcdef,则该二叉树的先序序列为中序序列为、后序序列为一鼠答:abdeeldbeafcdebfca。26 .设一棵完全二叉树（每个结点值为单个字符）的先序序列为abdecf,则该二叉树的中序序列为、层次序列为.答:dbeafcabcdef27 .二叉树的先序序列和中序序列相同的条件是答:该二叉树中每个结点最多只有一个右孩子。先序序列为N1.R,中序序列为1.NR,要使N1.R=1.NR,只有1.为空或1.、R均为空时，因此这样的二叉树每层只有一个结点,非叶子结点只有右孩子.28 .在二叉树的非递归中序和后序遍历算法中需要要用来暂存遍历的结点.答:栈.29 .线索二叉树的左线索指向其结点,右栈索指向其心结点。答:前驱后继。30 .若以4,5,6,7,8)作为叶子结点的权值构造哈夫曼树,则其带权路径长度是2_各结点对应的哈夫曼编码为答:69010、011>10、11、OOo如图7.9所示,WP1.=(4+5)X3+(6+7+8)X2=69。图7.9一棵哈夫曼树7.3.3判断题1.判断以下叙述的正确性。(1)树形结构中的每个结点都有一个前驱结点(2)度为m的树中至少有一个度为m的结点,不存在度大于m的结点。(3)在一棵树中，处于同一层上的各结点之间都存在兄弟关系。(4)n(n>2)个结点的二叉树中至少有一个度为2的结点(5)不存在这样的二叉树:它有n个度为0的结点,n-1个度为1的结点,n-2个度为2的结点(6)在任何一棵完全二叉树中，叶子结点或者和分支结点一样多,或者只比分支结点多(7)完全二叉树中的每个结点或者没有孩子或者有两个孩子(8)当二叉树中的结点数多于1个时,不可能根据结点的先序序列和后序序列唯一地确定该二叉树的逻辑结构。(9)只要知道完全二叉树中结点的先序序列就可以唯一地确定它的逻辑结构(10)哈夫曼树中不存在度为1的结点。(11)在哈夫曼树中,权值相同的叶子结点都在同一层上(12)在哈夫曼树中,权值较大的叶子结点一般离根结点较远。答：(1)错误。根结点没有前驱结点(2)正确。(3)错误。处于同一层并且有相同双亲的各结点之间是兄弟关系错误。(5)正确。不满足no=n2+l的性质,所以不存在这样的二叉树。(6)正确。在完全二叉树中,n=0或1,而no=n2+l,所以分支结点个数nl+n2=no或nl÷n2=no-l.(7)错误。完全二叉树中最多有一个单分支结点(8)正确。(9)正确。在完全二叉树中，已知结点总数就可以确定其形态。已知其先序序列，便可知其结点总数,再根据先序序列确定每个结点的位置。实际上,只要已知完全二叉树的任何一种追历序列就可以唯一确定该二叉树。(10)正确(11)错误。在哈夫曼树中,权值相同的叶子结点不一定都在同一层上。例如,某个哈夫曼树中只有3个叶子结点,权值均为1,它们就不可能都在同一层上。(12)错误。在哈夫曼树中,权值较大的叶子结点一般离根结点较近2 .判断以下叙述的正确性。(1)在一棵中度为m的树中,每个结点最多有m-1个兄弟。(2)在一棵有n个结点的树中,其分支数为n(3)如果树中X结点的层次(深度)大于y结点的深度,则X是y的的子孙结点。(4)在一棵3次树中,有n3=2,n2=l,nl=5,则叶子结点个数为6。(5)若一棵二叉树中的所有结点值不相同,可以由其先序序列和层次序列唯一构造出该二叉树(6)若一棵二叉树中的所有结点值不相同,可以由其中序序列和层次序列唯一构造出该二叉树。答：(1)正确(2)错误。一棵有n个结点的树中其分支数为nT(3)错误。(4)正确。m=3,n=n0+nl+n2+m3=no+8,又有nT=nl+2112+3n3=13,n=14,所以no=n-8=14-8=6O(5)错误。(6)正确。层次序列提供了根结点信息3 .判断以下叙述的正确性。(1)存在这样的二叉树,对它采用任何次序的遍历,结果相同。(2)二叉树就是度为2的树。(3)将一棵树转换成二叉树后,根结点没有左子树。(4)对于二叉树,在后序序列中,任一结点的后面都不会出现它的子孙结点(5)在哈夫曼编码中，当两个字符出现的频率相同时其编码也相同。答：(1)正确。当二叉树只有一个根结点时,任何遍历的序列均相同(2)错误(3)错误。通常根结点有左子树而无右子树。正确。(5)错误。哈夫曼编码是一种前缀码,即不允许出现两字符编码相同的情况。7. 3.4简答题1 .简述述二叉树与度为2的树之间的差别。答:二叉树的子树有严格的左、右之分,其次序不能任意颠倒,某个结点即使只有一棵子树,也区分是左子树还是右子树,而在度为2的树中，某个结点只有一棵子树时,是不区分左右性的。除此之外,二叉树可以是空树,而度为2的树至少有一个度为2的结点,所以不能为空树。2 .己知度为k的树中,其度为1,2,k的结点数分别为,%,.心。求该树的结点总数n和和叶子结点数小,并给出推导过程。答:显然有以下关系。kn=7?o+mH+nk=)】孙i=0另外树中分支总数为n-l,所有结点度之和等于分支总数：k-1=7八+2m+knk=)：力储即：kn=Emi+17=1所以：kkkMo=Z?Winc+1=(J-1)川+1>->->>-23.例如,若一棵度为4的树中度为1、2、3、4的结点个数分别为4、3、2、2,求n和阳的过程如下：这里心4,%二4,2二3,%=2,仁2,则：kn=Xj町+1=4+2X3+3X2+4X2+1=25>=1kno=(y-l)w>÷l=3÷2×2÷3×2÷1=144 .试证明：在具有n(ne1)个结点的m次树中,若采用孩子链存储结构,则其中有n(m-1)+1个指针域是空的。证明：具有n个结点的m次树采用孩子链存储结构,总的结点个数为n,每个结点有m个指针域点,共有nm个指针域<>而指向结点的靠空指针域个数为1.l(由指向孩子结点的分支数为1.l个推出)，所以空指针域个数=11n-(nT)=n(m-l)÷lo5 .一棵高度为h的完全k次树,如果按层次自顶向下，同一层自左向右,顺序从1开始对全部结点进行编号,试问：(1)最多有多少个结点?最少有多少个结点？(2)编号为q的结点的第i个孩子结点(若存在)编号是多少？(3)编号为q的结点的双亲结点编号是多少？答：(1)在高度为h的完全k次树中，除第h层以外,其余各层都是满的，即第1层有个结点,第2层有k个结点第卜1层有公7个结点(为满的情况)，最少有一个结点。因此,最多结点个数是：l+k+k2+-+kh2+kh=R-I最少结点个数是：+k+k2-+kh2+1=1"1+1一1(2)设编号为q的结点是完全k次树中第层上从左边数第j个结点,那么q就等于前j层的结点个数加j,即：由于完全k次树的第1层上的第j个结点左边有j一1个结点,它们共有(j-Dk个孩子。因此第j个结点的第i个孩子是第1+1层上从左边数第(jT)k+i个结点,其编号P为：卜I1P=7+k(j-l)+i41,-lj=q将ZT代人上式,化简得到P=(q-l)k+i÷lo所以,当编号为q的结点存在第i个孩子,其编号为(q-Dk+i+l。(3)设编号为q的结点是完全k次树中第层上从左边数第J个结点,那么这j个结点对应有1.k个双亲结点。因此,编号为q的双亲结点是第IT层的第1.k个结点,其编号P为：P=kl-1+0÷1pk-1.氏.klx-n_q+k-2将欠-1代入上式,化简得到1.女.因此,当q=l时,该结点为根结点,无双亲结点;否则,双亲结点的编号为q+欠-2k.6 .对于如图7.10所示的二叉树:画出它的顺序存储结构图将它转换(还原)成森林。答：(1)它的顺序存储结构图如下:123456789101112131415ABCDEF样GH井IJ转换成的森林如图7.11所示。图7.11转换成的森林7 .设F=T1,T2,T3是森林,如图7.12所示,试画出由F转换成的二叉树。答：由F转换成的二叉树如图7.13所示8 .已知一棵树T的先根序列与对应二叉树B的先序序列相同,树T的后根序列与对应二叉树B的中序序列相同。利用树的先根序列和后根序列能否唯一确定一棵树?举例说明。答:能。由树T的先根序列得到二叉树B的先序序列,树T的后根序列得到到B的中序序列，因为二叉树B可以由中先序序列和中序序列唯一确定，因此B是确定的,而二叉树B可以唯一还原为树To所以利用树的先根序列和后根序列能够唯确定一棵树。例如有一棵树,其先根序列为Abcefhidg,后根序列为echfibdgao构造这棵树的过程是以先序序列列Abcefhidg和中序序列Echfibdga构造一棵二叉树,如图7.14(b)所示,该树即为所求。（八）一棵二叉树6(b)还原成的树r图7.M一棵二叉树还原成树9 .任意个有n个结点的二叉树，已知它有m个叶子结点,试证明非叶子结点中有In结点，证明非叶子结点中有(mT)个结点的度为2,其余度为1。证明：设nl为二叉树中度为1的结点数,n2为度为2的结点数,则总的结点数如下。n=7?+7i2+m再看二叉树中的分支数,除根结点以外,其余结点都有一个分支进人,设B为分支数，则有:n=B+1.由于这些分支由度为1和2的结点发出的,所以又有：=21+2n2由以上两支可得：=+In2+1再结合前疝得：111+/I2+/n=n1+In2+1由此推出：n2=n-l10 .为什么说一棵非空完全二叉树,一旦结点个数n确定了，其树形也就确定了。答:在按层序编号时,完全二叉树的结点编号为l"n,如果已知各类结点个数,该完全二叉树的形态一定是确定的。若n已知,则可以根据其奇偶性确定nl:当n为偶数时,nl=l,当n为奇数时,nl=0,而n-n2+l,n=no+n1+n2=2no-1+n1,no-(n-nl+l)2,从而n和n2也确定了，所以这样的完全二叉树的形态就确定了。11 .为什么说一棵非空完全二叉树,仅已知叶子结点个数no,其树形还不能唯一确定。答:在该完全二叉树中，no己知，n2=no-l,n=n÷n1+n2=2no-1+n1,而nl可以为0或1,也就是说,n=2nOT或n=2no,其结点总数不确定,所以该完全二叉树的形态是不能确定的。12 .给定一棵非空二叉树b,采用二叉链存储结构,说明查找中序序列的第一个结点和最后一个结点的过程。答:中序序列的第一个结点就是根结点的最左下结点,其查找过程如下。P=b;while(p->Ichild!=NU1.1.)循环结束，P指向中序序列的第一个结点p=p->Ichild;中序序列的最后一个结点就是根结点的最右下结点,其查找过程如下P=b;while(p->rchild!=NU1.1.)循环结束，P指向中序序列的最后一个结点p=p->rchild;13 .对于二叉树T的两个结点a和b,在不构造出该二叉树的前提下,应该选择T的先序、中序和后序序列中的哪两个序列来判断结点a必定是结点b的祖先,并给出判断的方法。答:可以采用先序序列和后序序列来判断。由先序序列可知结点b的祖先一定在b之前;而在后序序列中,结点b的祖先一定在b之后;取先序序列在b之前的结点集集合以及后序序列在b之后的结点集合,这两个集合的交集即为b的祖先结点集合,则结点a必在该祖先结点集合中。14 .用一维数组存放一棵完全二叉树Abcdefghijkl,给出后序遍历该二叉树的访问结点序列。答:该完全二叉树如图图7.15所示,其后序序列为HidjkeblfgcAo图7.15一棵完全二叉树15 .已知一棵完全二叉树共有892个结点,试求：(1)树的高度；(2)单支结点数；(3)叶子结点数；(4)最后一个分支结点的序号答：该完全二叉树的高度=bg25+l)1=bg2893=10。(2)n=892为偶数,所以nl=lono=n2+l(二叉树的性质),=%+%=2。，%=/2=446。(4)最后一个分支结点的序号二1.n/2=44616 .已知完全二叉树的第8层有8个结点,则其叶子结点数是多少？答：由完全二叉树的定义可知,除最后一层以外,其他各层的结点是满的。这里第8层有8个结点,显然第8层是最后的一层,那么第7层的结点个数为27-1=64个,其中的4个结点有8个叶子结点,余下的为叶子结点,个数为64一4=600所以该完全二叉树的叶子结点个数=60+8=68个。17 .若一棵二叉树的左、右子树均有3个结点,其左子树的先序序列与中序序列相同,右子树的中序序列与后序序列相同,试构造该树形态。答:依题意,左子树的先序序列与中序序列相同，即有以下关系。根左右(先序)=左根右(中序)即以左孩子为根的子树无左孩子。此外,右子树的中序序列与后序序列相同，即有：左根右（中序）=左右根（后序）以右孩子为根的子树无无右孩子。由此构造该树的形态如图7.16所所示。图7.16一棵二叉树18 .若某非空二叉树的先序序列和中序序列正好相反,则该二叉树的形态是什么？答:二叉树的先序序列是N1.R、中序序列是1.NR,要使N1.R=RN1.（中序序列反序）成立,则R必须为空,所以满足条件的二叉树的形态是所有结点没有右子树的单支树。19 .一棵二叉树的先序、中序和后序序列分别如下,其中有一部分未显示出来。试求出空格处的内容,并画出该二叉树。先序序列:BFICEHG中序序列:DKFIAEJC后序序歹U：KFBHJGA答：由后序序列可知根结点为A,先序序列的第一个空为有5个结点，由先序序列可知,左子树中有B、F、I结点,所以中序序列的第一个空为B,可推出先序序列的第2个空为D,第3个空为K;