習(xí)題5 樹和二叉樹課件

1、1 填空題填空題(1)(1)樹是樹是n（n0）個結(jié)點(diǎn)的有限集合。在一棵非空樹個結(jié)點(diǎn)的有限集合。在一棵非空樹中，有（中，有（且僅有一個且僅有一個）根結(jié)點(diǎn)，其余結(jié)點(diǎn)分成）根結(jié)點(diǎn)，其余結(jié)點(diǎn)分成m（m=0）個個( (互不相交互不相交) )的有限集合的有限集合，每個集合又是一每個集合又是一棵樹?？脴?。(2) (2) 樹中某結(jié)點(diǎn)的子樹的個數(shù)稱為該結(jié)點(diǎn)的（樹中某結(jié)點(diǎn)的子樹的個數(shù)稱為該結(jié)點(diǎn)的（ 度度 ），），子樹的根結(jié)點(diǎn)稱為這個結(jié)點(diǎn)的子樹的根結(jié)點(diǎn)稱為這個結(jié)點(diǎn)的( ( 孩子結(jié)點(diǎn)孩子結(jié)點(diǎn) ),),該結(jié)點(diǎn)稱該結(jié)點(diǎn)稱為其子樹根結(jié)點(diǎn)的（為其子樹根結(jié)點(diǎn)的（雙親結(jié)點(diǎn)雙親結(jié)點(diǎn)）. . (3) (3) 一棵二叉樹的第一棵二叉樹

2、的第i（i1）層上最多有層上最多有( ( 2i- -1 ) )個結(jié)個結(jié)點(diǎn)點(diǎn), ,一棵有一棵有n(n0)n(n0)個結(jié)點(diǎn)的滿二叉樹共有個結(jié)點(diǎn)的滿二叉樹共有( ( (n+1)/2 (n+1)/2 ) )個葉子結(jié)點(diǎn)和個葉子結(jié)點(diǎn)和( ( (n-1)/2 (n-1)/2 ) )個非終端結(jié)點(diǎn)個非終端結(jié)點(diǎn)。 (4) (4) 設(shè)高度為設(shè)高度為h的的二叉樹只有度為二叉樹只有度為0 0的和度為的和度為2 2的結(jié)點(diǎn)，的結(jié)點(diǎn)，該二叉樹的結(jié)點(diǎn)數(shù)可能達(dá)到的最大值是該二叉樹的結(jié)點(diǎn)數(shù)可能達(dá)到的最大值是( ( 2h-1 -1 ),),最小最小值是（值是（ 2 2 h -1 -1 ）。）。(5)(5)深度為深度為k k的二叉樹中

3、，所含葉子的個數(shù)最多為的二叉樹中，所含葉子的個數(shù)最多為( (2 2k k-1-1).).(6)(6)具有具有100100個結(jié)點(diǎn)的完全二叉樹的葉子結(jié)點(diǎn)數(shù)為個結(jié)點(diǎn)的完全二叉樹的葉子結(jié)點(diǎn)數(shù)為( (5050) )。 (7) (7) 已知一棵度為已知一棵度為3 3的樹有的樹有2 2個度為個度為1 1的結(jié)點(diǎn)，的結(jié)點(diǎn)，3 3個度為個度為2 2的結(jié)點(diǎn)，的結(jié)點(diǎn)，4 4個度為個度為3 3的結(jié)點(diǎn)。則該樹有的結(jié)點(diǎn)。則該樹有( (1212) )個葉子結(jié)點(diǎn)個葉子結(jié)點(diǎn)。(8) (8) 某二叉樹的前序遍歷序列是某二叉樹的前序遍歷序列是ABCDEFG,ABCDEFG,中序遍歷序中序遍歷序列是列是CBDAFGE,CBDAFGE,

4、則其后序遍歷序列是則其后序遍歷序列是( ( CDBGFEA CDBGFEA ) )。(9)(9)在具有在具有n n個結(jié)點(diǎn)的二叉鏈表中，共有（個結(jié)點(diǎn)的二叉鏈表中，共有（ 2n 2n ) )個指個指針域，其中針域，其中( ( n-1 n-1 ) )個指針域用于指向其左右孩子，個指針域用于指向其左右孩子，剩下的剩下的( ( n+1 n+1 ) )個指針域則是空的。個指針域則是空的。(10)(10)在有在有n n個葉子的哈夫曼樹中，葉子結(jié)點(diǎn)總數(shù)為個葉子的哈夫曼樹中，葉子結(jié)點(diǎn)總數(shù)為( (n n),),分支結(jié)點(diǎn)總數(shù)為（分支結(jié)點(diǎn)總數(shù)為（ n-1 n-1 ）。）。1 填空題填空題(續(xù)續(xù))(1) (1) 如果結(jié)

5、點(diǎn)如果結(jié)點(diǎn)A A有有3 3個兄弟，個兄弟，B B是是A A的雙親，則的雙親，則B B的度是的度是( ( D D ) )。 A A1 B1 B2 C2 C3 D3 D4 42 選擇題選擇題(2) (2) 設(shè)二叉樹有設(shè)二叉樹有n n個結(jié)點(diǎn)，則其深度為個結(jié)點(diǎn)，則其深度為( ( D D ) )。 A An n一一1 B1 Bn Cn C D D不能定不能定 1log2n(3) (3) 二叉樹的前序序列和后序序列正好相反，則該二叉樹一二叉樹的前序序列和后序序列正好相反，則該二叉樹一定是定是( ( B B ) )的二叉樹。的二叉樹。 A A空或只有一個結(jié)點(diǎn)空或只有一個結(jié)點(diǎn) B B高度等于其結(jié)點(diǎn)數(shù)高度等于其

6、結(jié)點(diǎn)數(shù) C C任一結(jié)點(diǎn)無左孩子任一結(jié)點(diǎn)無左孩子 D D任一結(jié)點(diǎn)無右孩子任一結(jié)點(diǎn)無右孩子(4) (4) 線索二叉樹中某結(jié)點(diǎn)線索二叉樹中某結(jié)點(diǎn)R R沒有左孩子的充要條件是沒有左孩子的充要條件是( ( C C ) )。 A. R.child=NULL B. R.ltag=0 A. R.child=NULL B. R.ltag=0 C. R.ltag=1 D. R.child=NULL C. R.ltag=1 D. R.child=NULL(5) (5) 深度為深度為k k的完全二叉樹至少有的完全二叉樹至少有( ( B B ) )個結(jié)點(diǎn)，至多有個結(jié)點(diǎn)，至多有( ( C C ) )個結(jié)點(diǎn)。個結(jié)點(diǎn)。 A

7、A2 2k-2k-2+1 B+1 B2 2k-1k-1 C C2 2k k-1 D-1 D2 2k-1k-1-1-1 一個高度為一個高度為h h的滿二叉樹共有的滿二叉樹共有n n個結(jié)點(diǎn)，其中有個結(jié)點(diǎn)，其中有m m個葉子結(jié)點(diǎn)個葉子結(jié)點(diǎn)，則有，則有( ( D D ) )成立。成立。 A An nh+m Bh+m Bh+mh+m2n C2n Cm mh-1 Dh-1 Dn n2m2m一一1 1(7) (7) 任何一棵二叉樹的葉子結(jié)點(diǎn)在前序、中序、后序遍歷序列任何一棵二叉樹的葉子結(jié)點(diǎn)在前序、中序、后序遍歷序列中的相對次序中的相對次序( ( A A ) )。 A. A. 肯定不發(fā)生改變肯定不發(fā)生改變 B

8、. B.肯定發(fā)生改變肯定發(fā)生改變 C. C.不能確定不能確定 D D有時發(fā)生變化有時發(fā)生變化(9) (9) 設(shè)森林中有設(shè)森林中有4 4棵樹，樹中結(jié)點(diǎn)的個數(shù)依次為棵樹，樹中結(jié)點(diǎn)的個數(shù)依次為n1,n1, n2,n2, n3,n3, n4, n4, 則把森林轉(zhuǎn)換成二叉樹后，其根結(jié)點(diǎn)的右子樹上有則把森林轉(zhuǎn)換成二叉樹后，其根結(jié)點(diǎn)的右子樹上有( ( D D ) )個結(jié)點(diǎn)。根結(jié)點(diǎn)的左子樹上有個結(jié)點(diǎn)。根結(jié)點(diǎn)的左子樹上有( ( A A ) )個結(jié)點(diǎn)。個結(jié)點(diǎn)。 A An1-1 Bn1-1 Bnl Cnl Cnl+n2+n3 Dnl+n2+n3 Dn2+n3+n4n2+n3+n4(8) (8) 如果如果TT是由有序

9、樹是由有序樹T T轉(zhuǎn)換而來的二叉樹，那么轉(zhuǎn)換而來的二叉樹，那么T T中結(jié)點(diǎn)的中結(jié)點(diǎn)的前序序列就是前序序列就是TT中結(jié)點(diǎn)的中結(jié)點(diǎn)的( ( A A ) )序列，序列，T T中結(jié)點(diǎn)的后序序列中結(jié)點(diǎn)的后序序列就是就是TT中結(jié)點(diǎn)的中結(jié)點(diǎn)的( ( B B ) )序列。序列。 A A前序前序 B B中序中序 C C后序后序 D D層序?qū)有?10) (10) 討論樹、森林和二叉樹的關(guān)系，目的是為了討論樹、森林和二叉樹的關(guān)系，目的是為了( ( B B ) )。 A A借助二叉樹上的運(yùn)算方法去實(shí)現(xiàn)對樹的一些運(yùn)算借助二叉樹上的運(yùn)算方法去實(shí)現(xiàn)對樹的一些運(yùn)算 B B將樹、森林按二叉樹的存儲方式進(jìn)行存儲并利用二叉將樹、森

10、林按二叉樹的存儲方式進(jìn)行存儲并利用二叉樹的算法解決樹的有關(guān)問題樹的算法解決樹的有關(guān)問題 C. C. 將樹、森林轉(zhuǎn)換成二叉樹將樹、森林轉(zhuǎn)換成二叉樹 D D體現(xiàn)一種技巧，沒有什么實(shí)際意義體現(xiàn)一種技巧，沒有什么實(shí)際意義(11) 下列編碼中，下列編碼中，( B )不是前綴編碼。不是前綴編碼。 A. (00,01,10,11) B. (0,1,00,11) C.(0,10,110,111) D. (1,01,000,001)(12) 為為5個使用頻率不等的字符設(shè)計哈夫曼編碼，不可能個使用頻率不等的字符設(shè)計哈夫曼編碼，不可能的方案是的方案是( C ). A.111,110,10,01,00 B. 000,

11、001,010,011,1 C. 100,11,10,1,0 D. 001,000,01,11,10(13) 為為5個使用頻率不等的字符設(shè)計哈夫曼編碼，不可能個使用頻率不等的字符設(shè)計哈夫曼編碼，不可能的方案是的方案是( D ). A. 000,001,010,011,1 B. 0000,0001,001,01,1 C. 000,001,01,10,11 D. 00,100,101,110,111(14) 設(shè)哈夫曼編碼的長度不超過設(shè)哈夫曼編碼的長度不超過4，若已經(jīng)對兩個字符編，若已經(jīng)對兩個字符編碼為碼為1和和01，則最多還可以為，則最多還可以為( C )個字符編碼個字符編碼. A. 2 B. 3

12、 C. 4 D. 5(3)(3) 已知一棵度為已知一棵度為m m的樹中：的樹中：n n1 1個度為個度為1 1的結(jié)點(diǎn)，的結(jié)點(diǎn)，n n2 2個度個度為為2 2的結(jié)點(diǎn)，的結(jié)點(diǎn)，n nm m個度為個度為m m的結(jié)點(diǎn)，問該樹中共有多的結(jié)點(diǎn)，問該樹中共有多少個葉子結(jié)點(diǎn)？少個葉子結(jié)點(diǎn)？NoImage4. 解答下列問題解答下列問題(1)(1) 證明：任何滿二叉樹的分支數(shù)證明：任何滿二叉樹的分支數(shù)B=2(n0-1).B=2(n0-1).(2) (2) 證明：已知一棵二叉樹的前序序列和中序序列，證明：已知一棵二叉樹的前序序列和中序序列，則可唯一確定該二叉樹。則可唯一確定該二叉樹。(4) 已知一棵二叉樹的中序和后

13、序序列為已知一棵二叉樹的中序和后序序列為CBEDAFIGH和和CEDBIFHGA,試構(gòu)造該二叉樹。試構(gòu)造該二叉樹。AEBGCHFDI(5) 給給出葉子結(jié)點(diǎn)的權(quán)值集合為出葉子結(jié)點(diǎn)的權(quán)值集合為W=5,2,9,11, 8,3,7的哈夫曼樹的構(gòu)造過程的哈夫曼樹的構(gòu)造過程。 95235101911268715455 算法設(shè)計算法設(shè)計(1) 設(shè)計算法求二叉樹的結(jié)點(diǎn)個數(shù)設(shè)計算法求二叉樹的結(jié)點(diǎn)個數(shù).注：本算法可以用二叉樹遍歷的所有算法，只要把注：本算法可以用二叉樹遍歷的所有算法，只要把cout語句語句換成結(jié)點(diǎn)的計數(shù)就可以了，但是要注意遞歸中的計數(shù)變量應(yīng)換成結(jié)點(diǎn)的計數(shù)就可以了，但是要注意遞歸中的計數(shù)變量應(yīng)該是外

14、部變量。如該是外部變量。如int num=0;int BiTree:count( (BiNode *rt) ) countsub(rt); return num;void BiTree:countSub( (BiNode *rt) ) if ( (rt !=NULL) ) num+; countSub ( (rt-lchild) ); countSub ( (rt-rchild) ); 其他解法一：其他解法一：int BiTree:count( (BiNode *rt) ) if ( (rt =NULL) ) return 0; else return count( (rt-lchild) )

15、+count( (rt-rchild)+1)+1; 其他解法二：用前序遍歷的非遞歸算法其他解法二：用前序遍歷的非遞歸算法int BiTree:CountPreOrder(BiNode *rt) top= -1; p=rt; num=0;/采用順序棧采用順序棧s，并假定不會發(fā)生上溢，并假定不會發(fā)生上溢 while (p!=NULL | | top!= -1) while (p!= NULL) /找此結(jié)點(diǎn)的最左邊的后代找此結(jié)點(diǎn)的最左邊的后代 num+; /訪問訪問 s+top=p; /此結(jié)點(diǎn)進(jìn)棧此結(jié)點(diǎn)進(jìn)棧 p=p-lchild; /轉(zhuǎn)移到左兒子子樹轉(zhuǎn)移到左兒子子樹 if (top!= -1) p=

16、stop-; p=p-rchild; return num; / coutnum(1) 設(shè)計算法求二叉樹的結(jié)點(diǎn)個數(shù)設(shè)計算法求二叉樹的結(jié)點(diǎn)個數(shù).(3) 設(shè)計算法求二叉樹的深度設(shè)計算法求二叉樹的深度.注：本算法也可以用二叉樹遍歷的所有算法。但是在用前注：本算法也可以用二叉樹遍歷的所有算法。但是在用前序和中序算法時要注意深度如何來確定。序和中序算法時要注意深度如何來確定。解法一：解法一：int BiTree:depth( (BiNode *rt) ) if ( (rt =NULL) ) return 0; else hl= depth( (rt-lchild); ); hr= hr= depth(

17、(rt-rchild);); return (hlhr)?hl+1: return (hlhr)?hl+1:hr+1; (3) 設(shè)計算法求二叉樹的深度設(shè)計算法求二叉樹的深度.解法二：用后序遍歷的非遞歸算法解法二：用后序遍歷的非遞歸算法,這是棧的最大頂就是此這是棧的最大頂就是此樹的深度。樹的深度。void BiTree:DepthPostOrder(BiNode *rt) depth=0; top= -1; /采用順序棧，并假定棧不會發(fā)生上溢while (rt!=NULL | | top!= -1) while (rt!=NULL) s+top.ptr=rt; stop.flag=1; rt=r

18、t-lchild; if(top=depth) depth=top+1; while (top!= -1 & stop.flag=2) rt=stop-.ptr; if (top!= -1) stop.flag=2; rt=stop.ptr-rchild; coutThe depth of the tree is depth;(3) 設(shè)計算法求二叉樹的深度設(shè)計算法求二叉樹的深度.解法三：用層序遍歷算法解法三：用層序遍歷算法, 設(shè)一個指針來表示目前遍歷到設(shè)一個指針來表示目前遍歷到的層數(shù)，最底層就是此樹的深度。的層數(shù)，最底層就是此樹的深度。void BiTree:Depth(BiNode

19、*rt) int depth=0, flag=0;/depth為樹的深度，flag為當(dāng)前遍歷到的層數(shù)front=rear=-1; /采用順序隊(duì)列，并假定不會發(fā)生上溢if (rt!=NULL) Q+rear=rt; / Q為隊(duì)列while (front!=rear) q=Q+front; if (q-lchild!=NULL) Q+rear=q-lchild; if (q-rchild!=NULL) Q+rear=q-rchild; if(front=flag) depth+; flag=rear; coutdepth;(3) 設(shè)計算法求二叉樹的深度設(shè)計算法求二叉樹的深度.解法四：用前序遍歷算法

20、解法四：用前序遍歷算法, 在棧中設(shè)兩個域，一個表示原遍歷結(jié)點(diǎn)，一個在棧中設(shè)兩個域，一個表示原遍歷結(jié)點(diǎn)，一個表示此結(jié)點(diǎn)的層數(shù)。表示此結(jié)點(diǎn)的層數(shù)。template void BiTree:DepthProOrder(BiNode *rt) top= -1; length=0; /采用順序棧s，并假定不會發(fā)生上溢 while (rt!=NULL | | top!= -1) while (rt!= NULL) /找此結(jié)點(diǎn)的最左邊的后代 s+top.ptr=rt; /此結(jié)點(diǎn)進(jìn)棧 stop.depth=+length; rt=rt-lchild; /轉(zhuǎn)移到左兒子子樹 #2 while if(lengthd

21、epth) depth=length; if (top!= -1) rt=stop.ptr; length=stop-.depth; rt=rt-rchild; /#1 while(6) 以二叉鏈表為存儲結(jié)構(gòu)，在二叉樹中刪除以值以二叉鏈表為存儲結(jié)構(gòu)，在二叉樹中刪除以值x為根結(jié)點(diǎn)為根結(jié)點(diǎn)的子樹的子樹.解法思想解法思想: 若根結(jié)點(diǎn)的值為若根結(jié)點(diǎn)的值為x,則刪除整個樹；否則查找值為則刪除整個樹；否則查找值為x的結(jié)點(diǎn)的的結(jié)點(diǎn)的雙親雙親p，然后刪除此結(jié)點(diǎn)所對應(yīng)的子樹，然后刪除此結(jié)點(diǎn)所對應(yīng)的子樹,同時修改同時修改p的的左左(或右或右)孩子的指針孩子的指針。最好用前序遍歷查找。最好用前序遍歷查找,后序遍歷刪

22、除。后序遍歷刪除。void BiTree:DeleteX(BiNode *rt, T x) if(rt=NULL) return; if(rt-data=x) Release(rt); else DeleteX(rt-lchild, x); DeleteX(rt-rchild, x); void BiTree:DeleteX(BiNode *rt, T x) if(rt!=NULL) if(rt-data=x) Release(rt); rt=NULL; elsep=rt; top= -1; /采用順序棧s，并假定不會發(fā)生上溢 while (p!=NULL | | top!= -1) whil

23、e (p!= NULL) /找此結(jié)點(diǎn)的最左邊的后代 s+top=p; /此結(jié)點(diǎn)進(jìn)棧 if(p-lchild!=NULL )&(p-lchild-data=x) Release(p-lchild); p-lchild=NULL; if(p-rchild!=NULL )&(p-rchild-data=x) Release(p-rchild); p-rchild=NULL; p=p-lchild; #2 while if (top!= -1) p=stop-; p=p-rchild; /#1 whilevoid BiTree:DeleteX(BiNode *rt, T x) if(r

24、t!=NULL) if(rt-data=x) Release(rt); rt=NULL; elsep=rt; top= -1; /采用順序棧s，并假定不會發(fā)生上溢 while (p!=NULL | | top!= -1) while (p!= NULL) /找此結(jié)點(diǎn)的最左邊的后代 s+top=p; /此結(jié)點(diǎn)進(jìn)棧 p=p-lchild; /轉(zhuǎn)移到左兒子子樹 if(p!=NULL )&(p-data=x) Release(p) ; stop-lchild=NULL; #2 while if (top!= -1) p=stop; p=p-rchild; if(p!=NULL )&(p

25、-data=x) Release(p); stop-rchild=NULL; top-; /#1 while(7) 一棵具有一棵具有n個結(jié)點(diǎn)的二叉樹采用順序存儲結(jié)構(gòu)，編寫算個結(jié)點(diǎn)的二叉樹采用順序存儲結(jié)構(gòu)，編寫算法對該二叉樹進(jìn)行前序遍歷法對該二叉樹進(jìn)行前序遍歷.void BiTree:PreOrder_Seq(int rt) top= -1; p=rt; /采用順序棧采用順序棧s，并假定不會發(fā)生上溢，并假定不會發(fā)生上溢 while (p=length)&(Ap!=“ ”) | | top!= -1) while (p=length)&( Ap!=“ ”) /找此結(jié)點(diǎn)的最左邊的后代

26、找此結(jié)點(diǎn)的最左邊的后代 coutAp; /訪問訪問 s+top=p; /此結(jié)點(diǎn)進(jìn)棧此結(jié)點(diǎn)進(jìn)棧 p=2*p; /轉(zhuǎn)移到左兒子子樹轉(zhuǎn)移到左兒子子樹 if (top!= -1) p=stop-; p=2*p+1; 算法思想算法思想: 套用前序遍歷的原程序，注意查找左右孩子結(jié)點(diǎn)套用前序遍歷的原程序，注意查找左右孩子結(jié)點(diǎn)的地址和判別孩子是否存在的方法的地址和判別孩子是否存在的方法。(8) 編寫算法交換二叉樹中所有結(jié)點(diǎn)的左右子樹編寫算法交換二叉樹中所有結(jié)點(diǎn)的左右子樹.void BiTree:PostOrderChange( (BiNode *rt) ) if ( (rt=NULL) ) return; e

27、lse PostOrder( (rt-lchild) ); PostOrder( (rt-rchild) ); temp=rt-lchild; rt-lchild=rt-rchild; rt-rchild=temp; 解法思想解法思想: 使用任何使用任何遍歷算法，把遍歷算法，把“coutdata”改成左右孩子指針交換即可。改成左右孩子指針交換即可。(2) 設(shè)計算法按照前序次序打印二叉樹中的葉子結(jié)點(diǎn)設(shè)計算法按照前序次序打印二叉樹中的葉子結(jié)點(diǎn).void BiTree:leaf( (BiNode *rt) ) if ( (rt=NULL) ) return; else if(rt-lchild=NULL &!rt-rchild) coutdata; PostOrder( (rt-lchild) ); PostOrder( (rt-rchild) ); 注注:其實(shí)按照其實(shí)按照“選擇題選擇題”的的(7)知知:任何一棵二叉樹的葉子結(jié)點(diǎn)任何一棵二叉樹的葉子結(jié)點(diǎn)在前序、中序、后序遍歷序列中的相對次序肯定不發(fā)生改在前序、中序、后序遍歷序列中的相對次序肯定不發(fā)生改變變解法