第5章樹和二叉樹課后習(xí)題講解

1.填空題

⑴樹是n（n≥0）結(jié)點的有限集合，在一棵非空樹中，有（）個根結(jié)點，其余的結(jié)點分成m（m＞0）個（）的集合，每個集合都是根結(jié)點的子樹。

【解答】有且僅有一個，互不相交⑵樹中某結(jié)點的子樹的個數(shù)稱為該結(jié)點的（），子樹的根結(jié)點稱為該結(jié)點的（），該結(jié)點稱為其子樹根結(jié)點的（）。

【解答】度，孩子，雙親⑶一棵二叉樹的第i（i≥1）層最多有（）個結(jié)點；一棵有n（n>0）個結(jié)點的滿二叉樹共有（）個葉子結(jié)點和（）個非終端結(jié)點。

【解答】2i-1，(n+1)/2，(n-1)/2

【分析】設(shè)滿二叉樹中葉子結(jié)點的個數(shù)為n0，度為2的結(jié)點個數(shù)為n2，由于滿二叉樹中不存在度為1的結(jié)點，所以n=n0+n2；由二叉樹的性質(zhì)n0=n2+1，得n0=(n+1)/2，n2=(n-1)/2。⑷設(shè)高度為h的二叉樹上只有度為0和度為2的結(jié)點，該二叉樹的結(jié)點數(shù)可能達(dá)到的最大值是（），最小值是（）。

【解答】2h-1，2h-1

【分析】最小結(jié)點個數(shù)的情況是第1層有1個結(jié)點，其他層上都只有2個結(jié)點。⑸深度為k的二叉樹中，所含葉子的個數(shù)最多為（）。

【解答】2k-1

【分析】在滿二叉樹中葉子結(jié)點的個數(shù)達(dá)到最多。⑹具有100個結(jié)點的完全二叉樹的葉子結(jié)點數(shù)為（）。

【解答】50

【分析】100個結(jié)點的完全二叉樹中最后一個結(jié)點的編號為100，其雙親即最后一個分支結(jié)點的編號為50，也就是說，從編號51開始均為葉子。⑺已知一棵度為3的樹有2個度為1的結(jié)點，3個度為2的結(jié)點，4個度為3的結(jié)點。則該樹中有（）個葉子結(jié)點。

【解答】12

【分析】根據(jù)二叉樹性質(zhì)3的證明過程，有n0=n2+2n3+1（n0、n2、n3分別為葉子結(jié)點、度為2的結(jié)點和度為3的結(jié)點的個數(shù)）。⑻某二叉樹的前序遍歷序列是ABCDEFG，中序遍歷序列是CBDAFGE，則其后序遍歷序列是（）。

【解答】CDBGFEA

【分析】根據(jù)前序遍歷序列和后序遍歷序列將該二叉樹構(gòu)造出來。⑼在具有n個結(jié)點的二叉鏈表中，共有（）個指針域，其中（）個指針域用于指向其左右孩子，剩下的（）個指針域則是空的。

【解答】2n，n-1，n+1⑽在有n個葉子的哈夫曼樹中，葉子結(jié)點總數(shù)為（），分支結(jié)點總數(shù)為（）。

【解答】n，n-1

【分析】n-1個分支結(jié)點是經(jīng)過n-1次合并后得到的。2.選擇題⑴如果結(jié)點A有3個兄弟，B是A的雙親，則結(jié)點B的度是（）。

A1B2C3D4

【解答】D⑵設(shè)二叉樹有n個結(jié)點，則其深度為（）。

An-1BnC+1D不能確定

【解答】D

【分析】此題并沒有指明是完全二叉樹，則其深度最多是n，最少是+1。⑶二叉樹的前序序列和后序序列正好相反，則該二叉樹一定是（）的二叉樹。

A空或只有一個結(jié)點B高度等于其結(jié)點數(shù)

C任一結(jié)點無左孩子D任一結(jié)點無右孩子

【解答】B

【分析】此題注意是序列正好相反，則左斜樹和右斜樹均滿足條件。⑷線索二叉樹中某結(jié)點R沒有左孩子的充要條件是（）。

AR.lchild=NULLBR.ltag=0CR.ltag=1DR.rchild=NULL

【解答】C

【分析】線索二叉樹中某結(jié)點是否有左孩子，不能通過左指針域是否為空來判斷，而要判斷左標(biāo)志是否為1。⑸深度為k的完全二叉樹至少有（）個結(jié)點，至多有（）個結(jié)點，具有n個結(jié)點的完全二叉樹按層序從1開始編號，則編號最小的葉子的序號是（）。

A2k-2+1B2k-1C2k-1D2k–1-1

E2k+1F2k+1-1G2k-1+1H2k

【解答】B，C，A

【分析】深度為k的完全二叉樹最少結(jié)點數(shù)的情況應(yīng)是第k層上只有1個結(jié)點，最多的情況是滿二叉樹，編號最小的葉子應(yīng)該是在結(jié)點數(shù)最少的情況下，葉子結(jié)點的編號。⑹一個高度為h的滿二叉樹共有n個結(jié)點，其中有m個葉子結(jié)點，則有（）成立。

An=h+mBh+m=2nCm=h-1Dn=2m-1

【解答】D

【分析】滿二叉樹中沒有度為1的結(jié)點，所以有m個葉子結(jié)點，則度為2的結(jié)點個數(shù)為m-1。⑺任何一棵二叉樹的葉子結(jié)點在前序、中序、后序遍歷序列中的相對次序（）。

A肯定不發(fā)生改變B肯定發(fā)生改變C不能確定D有時發(fā)生變化

【解答】A

【分析】三種遍歷次序均是先左子樹后右子樹。⑻如果T'是由有序樹T轉(zhuǎn)換而來的二叉樹，那么T中結(jié)點的前序序列就是T'中結(jié)點的（）序列，T中結(jié)點的后序序列就是T'中結(jié)點的（）序列。

A前序B中序C后序D層序

【解答】A，B⑼設(shè)森林中有4棵樹，樹中結(jié)點的個數(shù)依次為n1、n2、n3、n4，則把森林轉(zhuǎn)換成二叉樹后，其根結(jié)點的右子樹上有（）個結(jié)點，根結(jié)點的左子樹上有（）個結(jié)點。

An1-1Bn1Cn1+n2+n3Dn2+n3+n4

【解答】D，A

【分析】由森林轉(zhuǎn)換的二叉樹中，根結(jié)點即為第一棵樹的根結(jié)點，根結(jié)點的左子樹是由第一棵樹中除了根結(jié)點以外其余結(jié)點組成的，根結(jié)點的右子樹是由森林中除第一棵樹外其他樹轉(zhuǎn)換來的。⑽討論樹、森林和二叉樹的關(guān)系，目的是為了（）。

A借助二叉樹上的運(yùn)算方法去實現(xiàn)對樹的一些運(yùn)算

B將樹、森林按二叉樹的存儲方式進(jìn)行存儲并利用二叉樹的算法解決樹的有關(guān)問題

C將樹、森林轉(zhuǎn)換成二叉樹

D體現(xiàn)一種技巧，沒有什么實際意義

【解答】B3.判斷題⑴在線索二叉樹中，任一結(jié)點均有指向其前趨和后繼的線索。

【解答】錯。某結(jié)點是否有前驅(qū)或后繼的線索，取決于該結(jié)點的標(biāo)志域是否為1。⑵在二叉樹的前序遍歷序列中，任意一個結(jié)點均處在其子女的前面。

【解答】對。由前序遍歷的操作定義可知。⑶二叉樹是度為2的樹。

【解答】錯。二叉樹和樹是兩種不同的樹結(jié)構(gòu)，例如，左斜樹是一棵二叉樹，但它的度為1。⑷由樹轉(zhuǎn)換成二叉樹，其根結(jié)點的右子樹總是空的。

【解答】對。因為根結(jié)點無兄弟結(jié)點。⑸用一維數(shù)組存儲二叉樹時，總是以前序遍歷存儲結(jié)點。

【解答】錯。二叉樹的順序存儲結(jié)構(gòu)是按層序存儲的，一般適合存儲完全二叉樹。

4．證明：對任一滿二叉樹，其分枝數(shù)B＝2(n0-1)。（其中，n0為終端結(jié)點數(shù)）

【解答】因為在滿二叉樹中沒有度為1的結(jié)點，所以有：

n=n0+n2

設(shè)B為樹中分枝數(shù)，則

n=B+1

所以

B=n0+n2-1

再由二叉樹性質(zhì)：

n0=n2+1

代入上式有：

B=n0+n0-1-1=2(n0-1)

5．證明：已知一棵二叉樹的前序序列和中序序列，則可唯一確定該二叉樹。

【解答】證明采用歸納法。

設(shè)二叉樹的前序遍歷序列為a1a2a3…an，中序遍歷序列為b1b2b3…bn。

當(dāng)n=1時，前序遍歷序列為a1，中序遍歷序列為b1，二叉樹只有一個根結(jié)點，所以，a1=b1，可以唯一確定該二叉樹；

假設(shè)當(dāng)n<=k時，前序遍歷序列a1a2a3…ak和中序遍歷序列b1b2b3…bk可唯一確定該二叉樹，下面證明當(dāng)n=k+1時，前序遍歷序列a1a2a3…akak+1和中序遍歷序列b1b2b3…bkbk+1可唯一確定一棵二叉樹。

在前序遍歷序列中第一個訪問的一定是根結(jié)點，即二叉樹的根結(jié)點是a1，在中序遍歷序列中查找值為a1的結(jié)點，假設(shè)為bi，則a1=bi且b1b2…bi-1是對根結(jié)點a1的左子樹進(jìn)行中序遍歷的結(jié)果，前序遍歷序列a2a3…ai是對根結(jié)點a1的左子樹進(jìn)行前序遍歷的結(jié)果，由歸納假設(shè)，前序遍歷序列a2a3…ai和中序遍歷序列b1b2…bi-1唯一確定了根結(jié)點的左子樹，同樣可證前序遍歷序列ai+1ai+2…ak+1和中序遍歷序列bi+1bi+2…bk+1唯一確定了根結(jié)點的右子樹。6．已知一棵度為m的樹中有：n1個度為1的結(jié)點，n2個度為2的結(jié)點，……，nm個度為m的結(jié)點，問該樹中共有多少個葉子結(jié)點？

【解答】設(shè)該樹的總結(jié)點數(shù)為n，則

n=n0+n1+n2+……+nm

又：

n=分枝數(shù)+1=0×n0+1×n1+2×n2+……+m×nm+1

由上述兩式可得：

n0=n2+2n3+……+(m-1)nm+1

7．已知二叉樹的中序和后序序列分別為CBEDAFIGH和CEDBIFHGA，試構(gòu)造該二叉樹。

【解答】二叉樹的構(gòu)造過程如圖5-12所示。

8．對給定的一組權(quán)值W＝（5，2，9，11，8，3，7），試構(gòu)造相應(yīng)的哈夫曼樹，并計算它的帶權(quán)路徑長度。

【解答】構(gòu)造的哈夫曼樹如圖5-13所示。樹的帶權(quán)路徑長度為：

WPL=2×4+3×4+5×3+7×3+8×3+9×2+11×2

=1209．已知某字符串S中共有8種字符，各種字符分別出現(xiàn)2次、1次、4次、5次、7次、3次、4次和9次，對該字符串用[0，1]進(jìn)行前綴編碼，問該字符串的編碼至少有多少位。

【解答】以各字符出現(xiàn)的次數(shù)作為葉子結(jié)點的權(quán)值構(gòu)造的哈夫曼編碼樹如圖5-14所示。其帶權(quán)路徑長度=2×5+1×5+3×4+5×3+9×2+4×3+4×3+7×2=98，所以，該字符串的編碼長度至少為98位。10．算法設(shè)計⑴設(shè)計算法求二叉樹的結(jié)點個數(shù)。

【解答】本算法不是要打印每個結(jié)點的值，而是求出結(jié)點的個數(shù)。所以可將遍歷算法中的“訪問”操作改為“計數(shù)操作”，將結(jié)點的數(shù)目累加到一個全局變量中，每個結(jié)點累加一次即完成了結(jié)點個數(shù)的求解。

具體算法如下：⑵設(shè)計算法按前序次序打印二叉樹中的葉子結(jié)點。

【解答】本算法的要求與前序遍歷算法既有相同之處，又有不同之處。相同之處是打印次序均為前序，不同之處是此處不是打印每個結(jié)點的值，而是打印出其中的葉子結(jié)點，即為有條件打印。為此，將前序遍歷算法中的訪問操作改為條件打印即可。算法如下：⑶設(shè)計算法求二叉樹的深度。

【解答】當(dāng)二叉樹為空時，深度為0；若二叉樹不為空，深度應(yīng)是其左右子樹深度的最大值加1，而其左右子樹深度的求解又可通過遞歸調(diào)用本算法來完成。具體算法如下：⑷編寫算法，要求輸出二叉樹后序遍歷序列的逆序。

【解答】要想得到后序的逆序，只要按照后序遍歷相反的順序即可，即先訪問根結(jié)點，再遍歷根結(jié)點的右子樹，最后遍歷根結(jié)點的左子樹。注意和前序遍歷的區(qū)別，具體算法如下：⑸以二叉鏈表為存儲結(jié)構(gòu)，編寫算法求二叉樹中結(jié)點x的雙親。

【解答】對二叉鏈表進(jìn)行遍歷，在遍歷的過程中查找結(jié)點x并記載其雙親。具體算法如下：⑹以二叉鏈表為存儲結(jié)構(gòu)，在二叉樹中刪除以值x為根結(jié)點的子樹。

【解答】對二叉鏈表進(jìn)行遍歷，在遍歷的過程中查找結(jié)點x并記載其雙親，然后將結(jié)點x的雙親結(jié)點中指向結(jié)點x的指針置空。具體算法如下：⑺一棵具有n個結(jié)點的二叉樹采用順序存儲結(jié)構(gòu)，編寫算法對該二叉樹進(jìn)行前序遍歷。

【解答】按照題目要求，設(shè)置一個工作棧以完成對該樹的非遞歸算法，思路如下：

①每訪問一個結(jié)點，將此結(jié)點壓棧，查看此結(jié)點是否有左子樹，若有，訪問左子樹，重復(fù)執(zhí)行該過程直到左子樹為空。

②從棧彈出一個結(jié)點，如果此結(jié)點有右子樹，訪問右子樹執(zhí)行步驟①，否則重復(fù)執(zhí)行步驟②。

具體算法如下：⑻編寫算法交換二叉樹中所有結(jié)點的左右子樹。

【解答】對二叉樹進(jìn)行后序遍歷，在遍歷過程中訪問某結(jié)點時交換該結(jié)點的左右子樹。

具體算法如下：⑼以孩子兄弟表示法做存儲結(jié)構(gòu)，求樹中結(jié)點x的第i個孩子。

【解答】先在鏈表中進(jìn)行遍歷，在遍歷過程中查找值等于x的結(jié)點，然后由此結(jié)點的最左孩子域firstchild找到值為x結(jié)點的第一個孩子，再沿右兄弟域rightsib找到值為x結(jié)點的第i個孩子并返回指向這個孩子的指針。

樹的孩子兄弟表示法中的結(jié)點結(jié)構(gòu)定義如下：

template

structTNode

{

Tdata;

TNode*firstchild,*rightsib;

};

具體算法如下：學(xué)習(xí)自測及答案1．前序遍歷和中序遍歷結(jié)果相同的二叉樹是（）。

A根結(jié)點無左孩子的二叉樹B根結(jié)點無右孩子的二叉樹

C所有結(jié)點只有左子樹的二叉樹D所有結(jié)點只有右子樹的二叉樹

【解答】D1．前序遍歷和中序遍歷結(jié)果相同的二叉樹是（）。A根結(jié)點無左孩子的二叉樹B根結(jié)點無右孩子的二叉樹C所有結(jié)點只有左子樹的二叉樹D所有結(jié)點只有右子樹的二叉樹【解答】D

2．由權(quán)值為{3,8,6,2,5}的葉子結(jié)點生成一棵哈夫曼樹，其帶權(quán)路徑長度為（）。

A24B48C53D72

【解答】C

3．用順序存儲的方法將完全二叉樹中的所有結(jié)點逐層存放在數(shù)組A[1]~A[n]中，結(jié)點A[i]若有左子樹，則左子樹的根結(jié)點是（）。

AA[2i-1]BA[2i+1]CA[i/2]DA[2i]

【解答】D

4．對任何一棵二叉樹T，如果其終端結(jié)點的個數(shù)為n0，度為2的結(jié)點個數(shù)為n2，則（）。

An0=n2-1Bn0=n2Cn0=n2+1D沒有規(guī)律

【解答】C

5．一棵滿二叉樹中共有n個結(jié)點，其中有m個葉子結(jié)點，深度為h，則（）。

An=h+mBh+m=2nCm=h-1Dn=2h-1

【解答】D

6．對于完全二叉樹中的任一結(jié)點，若其右分支下的子孫的最大層次為h，則其左分支下的子孫的最大層次為（）。

AhBh+1Ch或h+1D任意

【解答】C

7．假定一棵度為3的樹中結(jié)點數(shù)為50，則其最小高度應(yīng)為。

A3B4C5D6

【解答】C

8．在線索二叉樹中，一個結(jié)點是葉子結(jié)點的充要條件為（）。

A左線索標(biāo)志為0，右線索標(biāo)志為1B左線索標(biāo)志為1，右線索標(biāo)志為0

C左、右線索標(biāo)志均為0D左、右線索標(biāo)志均為1

【解答】C

9．對于一棵具有n個結(jié)點的樹，其所有結(jié)點的度之和為（）。

【解答】n-1

10．在順序存儲的二叉樹中，編號為i和j的兩個結(jié)點處在同一層的條件是（）。

【解答】11．現(xiàn)有按前序遍歷二叉樹的結(jié)果