習題5 樹和二叉樹

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

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

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

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

5、點如果結點a a有有3 3個兄弟，個兄弟，b b是是a a的雙親，則的雙親，則b b的度是的度是( ( d d ) )。 a a1 b1 b2 c2 c3 d3 d4 42 選擇題選擇題(2) (2) 設二叉樹有設二叉樹有n n個結點，則其深度為個結點，則其深度為( ( d d ) )。 a an n一一1 b1 bn cn c d d不能定不能定 1log2n(3) (3) 二叉樹的前序序列和后序序列正好相反，則該二叉樹一二叉樹的前序序列和后序序列正好相反，則該二叉樹一定是定是( ( b b ) )的二叉樹。的二叉樹。 a a空或只有一個結點空或只有一個結點 b b高度等于其結點數(shù)高度等于其

6、結點數(shù) c c任一結點無左孩子任一結點無左孩子 d d任一結點無右孩子任一結點無右孩子(4) (4) 線索二叉樹中某結點線索二叉樹中某結點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 ) )個結點，至多有個結點，至多有( ( c c ) )個結點。個結點。 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 (6)(6) 一個高度為一個高度為h h的滿二叉樹共有的滿二叉樹共有n n個結點，其中有個結點，其中有m m個葉子結個葉子結點，則有點，則有( ( d d ) )成立。成立。 a an nh+m bh+m bh+mh+m2n c2n cm mh-1 dh-1 dn n2m2m一一1 1(7) (7) 任何一棵二叉樹的葉子結點在前序、中序、后序遍歷序列任何一棵二叉樹的葉子結點在前序、中序、后序遍歷序列中的相對次序中的相對次序( ( a a ) )。 a. a. 肯定不發(fā)生改變肯定

8、不發(fā)生改變 b. b.肯定發(fā)生改變肯定發(fā)生改變 c. c.不能確定不能確定 d d有時發(fā)生變化有時發(fā)生變化(9) (9) 設森林中有設森林中有4 4棵樹，樹中結點的個數(shù)依次為棵樹，樹中結點的個數(shù)依次為n1,n1, n2,n2, n3,n3, n4, n4, 則把森林轉換成二叉樹后，其根結點的右子樹上有則把森林轉換成二叉樹后，其根結點的右子樹上有( ( d d ) )個結點。根結點的左子樹上有個結點。根結點的左子樹上有( ( a a ) )個結點。個結點。 a an1-1 bn1-1 bnl cnl cnl+n2+n3 dnl+n2+n3 dn2+n3+n4n2+n3+n4(8) (8) 如果如

9、果tt是由有序樹是由有序樹t t轉換而來的二叉樹，那么轉換而來的二叉樹，那么t t中結點的中結點的前序序列就是前序序列就是tt中結點的中結點的( ( a a ) )序列，序列，t t中結點的后序序列中結點的后序序列就是就是tt中結點的中結點的( ( b b ) )序列。序列。 a a前序前序 b b中序中序 c c后序后序 d d層序層序(10) (10) 討論樹、森林和二叉樹的關系，目的是為了討論樹、森林和二叉樹的關系，目的是為了( ( b b ) )。 a a借助二叉樹上的運算方法去實現(xiàn)對樹的一些運算借助二叉樹上的運算方法去實現(xiàn)對樹的一些運算 b b將樹、森林按二叉樹的存儲方式進行存儲并利

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

11、b. 000,001,010,011,1 c. 100,11,10,1,0 d. 001,000,01,11,10(13) 為為5個使用頻率不等的字符設計哈夫曼編碼，不可能個使用頻率不等的字符設計哈夫曼編碼，不可能的方案是的方案是( 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) 設哈夫曼編碼的長度不超過設哈夫曼編碼的長度不超過4，若已經(jīng)對兩個字符編，若已經(jīng)對兩個字符編碼為碼為1和和01，則最多還可以為，則最多還可以為( c )個字符編碼個字符編碼. a.

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

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

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) /找此結點的最左邊的后代找此結點的最左邊的后代 num+; /訪問訪問 s+top=p; /此結點進棧此結點進棧 p=p-lchild; /轉移到左兒子子樹轉移到左兒子子樹 if (top!= -1) p=

16、stop-; p=p-rchild; return num; / coutnum(1) 設計算法求二叉樹的結點個數(shù)設計算法求二叉樹的結點個數(shù).(3) 設計算法求二叉樹的深度設計算法求二叉樹的深度.注：本算法也可以用二叉樹遍歷的所有算法。但是在用前注：本算法也可以用二叉樹遍歷的所有算法。但是在用前序和中序算法時要注意深度如何來確定。序和中序算法時要注意深度如何來確定。解法一：解法一：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) 設計算法求二叉樹的深度設計算法求二叉樹的深度.解法二：用后序遍歷的非遞歸算法解法二：用后序遍歷的非遞歸算法,這是棧的最大頂就是此這是棧的最大頂就是此樹的深度。樹的深度。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ù)，最底層就是此樹的深度。void bitree:depth(binode

19、*rt) int depth=0, flag=0;/depth為樹的深度，flag為當前遍歷到的層數(shù)front=rear=-1; /采用順序隊列，并假定不會發(fā)生上溢if (rt!=null) q+rear=rt; / q為隊列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) 設計算法求二叉樹的深度設計算法求二叉樹的深度.解法四：用前序遍歷算法

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

21、epth) depth=length; if (top!= -1) rt=stop.ptr; length=stop-.depth; rt=rt-rchild; /#1 while(6) 以二叉鏈表為存儲結構，在二叉樹中刪除以值以二叉鏈表為存儲結構，在二叉樹中刪除以值x為根結點為根結點的子樹的子樹.解法思想解法思想: 若根結點的值為若根結點的值為x,則刪除整個樹；否則查找值為則刪除整個樹；否則查找值為x的結點的的結點的雙親雙親p，然后刪除此結點所對應的子樹，然后刪除此結點所對應的子樹,同時修改同時修改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) /找此結點的最左邊的后代 s+top=p; /此結點進棧 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) /找此結點的最左邊的后代 s+top=p; /此結點進棧 p=p-lchild; /轉移到左兒子子樹 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個結點的二叉樹采用順序存儲結構，編寫算個結點的二叉樹采用順序存儲結構，編寫算法對該二叉樹進行前序遍歷法對該二叉樹進行前序遍歷.void bitree:preorder_seq(int rt) top= -1; p=rt; /采用順序棧采用順序棧s，并假定不會發(fā)生上溢，并假定不會發(fā)生上溢 while (p=length)&(ap!=“ ”) | | top!= -1) while (p=length)&( ap!=“ ”) /找此結點的最左邊的后代

26、找此結點的最左邊的后代 coutap; /訪問訪問 s+top=p; /此結點進棧此結點進棧 p=2*p; /轉移到左兒子子樹轉移到左兒子子樹 if (top!= -1) p=stop-; p=2*p+1; 算法思想算法思想: 套用前序遍歷的原程序，注意查找左右孩子結點套用前序遍歷的原程序，注意查找左右孩子結點的地址和判別孩子是否存在的方法的地址和判別孩子是否存在的方法。(8) 編寫算法交換二叉樹中所有結點的左右子樹編寫算法交換二叉樹中所有結點的左右子樹.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) 設計算法按照前序次序打印二叉樹中的葉子結點設計算法按照前序次序打印二叉樹中的葉子結點.void bitree:leaf( (binode *rt) ) if ( (rt=null) ) return; else if(rt-lchild=null &!rt-rchild) coutdata; postorder( (rt-lchild) ); postorder( (rt-rchild) ); 注注:其實按照其實按照“選擇題選擇題”的的(7)知知:任何一棵二叉樹的葉子結點任何一棵二叉樹的葉子結點在前序、中序、后序遍歷序列中的相對次序肯定不發(fā)生改在前序、中序、后序遍歷序列中的相對次序肯定不發(fā)生改變變解法