1、數據結構習題及解析第6 章 樹和二叉樹基礎知識題6.1 已知一棵樹邊的集合為 <I,M>,<I,N> <E,I><B,E><B,D><A,B><G,J><G,K><C,G><C,F>，<H,L><C,H><A,C>請畫出這棵樹，并回答下列問題：（1） 哪個是根結點？（2） 哪些是葉子結點？（3） 哪個是結點G的雙親？（4） 哪些是結點G的祖先？（5） 哪些是結點G的孩子？（6） 哪些是結點E的子孫？（7） 哪些是結點E的兄弟？哪些是結點F的

2、兄弟？（8） 結點B和N的層次號分別是什么？（9） 樹的深度是多少？（10） 以結點C為根的子樹的深度是多少？ 6.2一棵度為2的樹與一棵二叉樹有何區別？ 6.3試分別畫出具有3個結點的樹和3個結點的二叉樹的所有不同形態。 6.4一棵深度為H的滿k叉樹有如下性質；第H層上的結點都是葉子結點，其余各層上每個結點都有k棵非空子樹，如果按層次順序從1開始對全部結點的編號，問：（1） 各層的結點樹目是多少？（2） 編號為p的結點的父結點（若存在）的編號是多少？（3） 編號為p的結點的第i 個兒子結點（若存在）的編號是多少？（4） 編號為p的結點有右兄弟的條件什么？其右兄弟的編號是多少？ 6.5已知一棵

3、樹為k的樹中有n1 個度為1的結點，n2 個度為2的結點,nk 個度為k的結點,問該樹中有多少個葉子結點? 6.6已知在一棵含有n個結點的樹中,只有度為k的分支結點和度為0的葉子結點.試求該樹含有的葉子結點的數目. 6.7一棵含有n個結點的k叉樹，可能達到的最大深度和最小深度各為多少？ 6.8證明：一棵滿k叉樹上的葉子結點數n0 和 非葉子結點數n1 之間滿足以下關系：n0 =（k - 1）n1 + 1 6.9試分別推導出含有n個結點和含有n0 個葉子結點的完全三叉樹的深度H。 6.10對于那些所有非葉子結點均有非空左右子樹的二叉樹：（1） 試問：有n個葉子結點的樹中共有多少個結點？（2） 試

4、證明：2-（li-1 ） =1 其中n 為葉子節點的個數，li 表示第 i 個葉子節點所在的層次（設根結點所在層次為1）。 6.11 在二叉樹的順序存儲結構中，實際上隱含這雙親的信息，因此可和三叉鏈表對應。假設每個指針域占4個字節的存儲，每個信息域占k個字節的存儲，試問：對于一棵有n個結點的二叉樹，且在順序存儲結構中最后一個結點的下標為m，在什么條件下順序存儲結構比三叉鏈表更節省空間？ 6.12 對應6.3所得各種形態的二叉樹，分別寫出前序、中序、后序遍歷的序列。 6.13 假設n和m為二叉樹中二結點，用“1”、“0”或“”（分別表示肯定、恰恰相反或者不一定）填寫下表： 答問已知前序遍歷時 n

5、在m前？中序遍歷時 n在m前？后序遍歷時 n在m前？ n在m左方n在m左方n在m祖先n在m子孫 注意：如果（1）離a 和 b 最近的共同祖先p存在且（2）a 在p 的左子樹中，b在p的右子樹中，則稱a在b的左方（即b在a的右方）。6.14 找出所有滿足下列條件的二叉樹；（a） 它們在先序遍歷和中序遍歷時，得到的結點訪問序列相同；（b） 它們在后序遍歷和中序遍歷時，得到的結點訪問序列相同；（c） 它們在先序遍歷和后序遍歷時，得到的結點訪問序列相同； 6.15請對右圖所示二叉樹進行后序線索化，為每個空指針建立相應的前驅或后繼線索。 6.16將下列二叉鏈表改為先序線索鏈表（不畫出樹的形態）。 1 2

6、 3 4 5 6 7 8 9 10 11 12 13 14InfoABCDEFGHIJKLMNLtag Lchild24607010012130000RtagRchild3500891100014000 6.17 閱讀下列算法，若有錯，則改之。BiTree InSucc（BiTree q） / 已知q 是指向中序線索二叉樹上某個結點的指針， / 本函數返回指向*q的后繼的指針。 r= q->rchild; if (!r->rtag) while (!r->rtag) r=r->rchild; return r; /InSucc6.18試討論，能否在一棵中序全線索二叉樹上

7、查找給定結點*p 在后序序列中的后繼。6.19 分別畫出和下列樹對應的各個二叉樹；6.20將下列森林轉換為相應的二叉樹，并分別按以下說明進行線索化；（1） 先序前驅線索化；（2） 中序全線索化；（3） 后序后繼線索化。6.21畫出和下列二叉樹相應的森林；6.22對于6.19題中給出的各樹分別求出以下遍歷序列； （1）先序遍歷 （2） 后序遍歷6.23畫出和下列已知序列對應的樹T： 樹的先根次序訪問序列為GFKDAIEBCHG 樹的后跟次序訪問序列為DIAEKFCJHBG。6.24畫出和下列已知序列對應的森林F： 森林的先根次序訪問序列為ABCDEFGHIJKL 樹的后跟次序訪問序列為CBEFD

8、GAJIKLH。6.25證明：在結點數多于1的哈夫曼樹中不存在度為 1的結點。6.26 假設用于通信的電文僅由8個字母組成，字母在電文中出現的頻率分別是0.07。0.19，0.02，0.06，0.32，0.03，0.21，0.10。試為這8個字母設計哈夫編碼，使用07的二進制表示形式是另一種編碼方案，對于上述實例，比較這兩種方案的優缺點。6.27假設一棵二叉樹的先序序列為EBADCFHGIKJ和中序序列為ABCDEFGHIJK。請畫出樹。6.28假設一棵二叉樹的中序序列為D CBGEAHFIJK和后序序列為DCEGBFHKJIA。請畫出樹。6.29假設一棵二叉樹的層序序列為ABCDEFGHIJ

9、和中序序列為DBGEHJACIF。請畫出樹。6.30證明：樹中結點u 是結點v的祖先，當且僅當在先序 序列中u在v之前，且在后序序列中u在v之后。6.31證明：由一棵二叉樹的先序序列和中序序列可唯一確定這棵二叉樹。6.32證明；如果一棵二叉樹的先序序列是u1，u2. un 中序序列為up1 up2.upp 則序列1,2,.,n可以通過一個棧得到序列 p1，p2. pn ;反之,若以上述中的結論作為前提,則存在一棵二叉樹,若其前序序列是u1，u2. un ,則其中序序列為 up1 up2.upp. 算法設計題 6.33假定用兩個一維數組L1n和R1.n作為有n個結點的二叉樹的存儲結構,Li和Ri

10、分別指出結點i的左孩子和右孩子,0表示空,試寫一算法判別結點是否為結點V的子孫.6.34同6.33題條件。先由L和R建立一維數組T1n,使T中第 i ( i=1,2,n )個分量指示結點i 的雙親,然后寫判別結點u是否為結點v的子孫的算法.6.35 假設二叉樹中左分支的標號為”0”,右分支的標號為”1”,并對二叉樹增設一個頭結點,令根結點為其右孩子,則從頭結點到樹中任一點所經分支的序列為一個二進制序列,可以作是某個十進制數的二進制表示.例如,右圖所示二叉樹中,和節點A對應的二進制序列為”110”,即十進制整數6的二進制表示,已知一棵非空二叉樹以順序存儲結構表示,試寫一盡可能簡單的算法,求出與樹

11、的順序存儲結構中下標值為i 的結點對應的十進制數.以下6.36至6.38和6.41至6.53題中,均以二叉鏈表作為二叉樹的存儲結構.6.36若已知兩棵二叉樹B1和B2皆為空,或者皆不為空且B1的左右子樹 和B2的左子樹分別相似,則稱二叉樹B1和B2相似,試編寫算法,判別給定兩棵二叉樹是否相似.6.37試利用棧的基本操作寫出先序遍歷的非遞歸形式的算法。6.38同6.37條件，寫出后序遍歷的非遞歸形式的算法（提示：為分辨后序遍歷時兩次進棧的不同返回點，需在指針進棧時同時將一個標志進棧）。6.39若在二叉鏈表的結點中增設兩個域：雙親域（parent）以指示其雙親結點，標志域（mark取值0.2）以區

12、分在遍歷過程中達到該結點時應繼續向左或向右或訪問該結點，試以存儲結構編寫不用棧進行后序遍歷的遞推形式的算法。6.40若在二叉鏈表的結點中只增設一個雙親域以指示其雙親結點，則在遍歷過程中能否不設棧？試以存儲結構編寫不設棧進行中序遍歷的遞推形式的算法。6.41編寫遞歸算，在二叉樹中求位于先序序列中第k個位置的結點的值。6.42編寫遞歸算法，計算二叉樹中葉子結點的數目。6.43編寫遞歸算法，將二叉樹中所有結點的左、右子樹相互交換。6.44編寫遞歸算法，求二叉樹中以元素值為x 的結點為根的子樹的深度。6.45編寫遞歸算法，對于二叉樹中的每一個元素值為x的結點，刪去以它為根的子樹，并釋放相應的空間。6.

13、46編寫復制一棵二叉樹的非遞歸算法。6.47已知在二叉樹中，*root 為根結點，*p和*q為二叉樹中的兩個結點，試編寫求距離它們最近的共同祖先的算法。6.48編寫按層次順序中（同一層自左向右）遍歷二叉樹的算法。6.49編寫算法判別給定二叉樹是否為完全二叉樹。6.50假設以三元組（F，C，L/R）的形式輸入一棵二叉樹的諸邊（其中F表示雙親結點的標識，C表示孩子結點標識，L/R表示C為F的左孩子或右孩子），且在輸入的三元組序列中，C是按層次順序出現的，設結點的標識是字符型，F=時C為根結點標識，若C也為，則表示輸入結束，例如，6.15題所示二叉樹的三元組序列輸入格式為： ALABLACRBDLC

14、ELCFRDGRFHLL試編寫算法，由輸入的三元數組序列建二叉樹的二叉鏈表。6.51編寫算法，輸出以二叉樹表示的算術表達式，若該表達式中含有括號，則在輸出時應添上。6.52一棵二叉樹的繁茂度定義為各層結點數的最大值與樹的高度的乘積，試寫一算法求二叉樹的繁茂度。6.53試編寫算法，求給定二叉樹上從根結點到葉子結點的一條其路徑長度等于樹的深度減一的路徑（即列出從根結點到該葉子結點的結點序列），若這樣的路徑存在多條，則輸出路徑終點（葉子結點）在“最左”的時間復雜度。6.54已知一棵完全二叉樹存于順序表sa中，sa.elm1.sa.last含結點值。試編寫算法由此順序存儲結構建立該二叉樹的二叉鏈表。6

15、.55二叉鏈表的結點增加DescNum域，試編寫算法，求二叉樹的每個結點的子孫數目并存入其DescNum域。請給出算法的 時間復雜度。6.56試寫一個算法，在先序后繼線索二叉樹中，查找給定結點*p在先序序列中的后繼（假設二叉樹的根結點未知）。并討論實現此算法對存儲結構有何要求？6.57試編寫一算法，在后序后繼線索二叉樹中 ，查找給定結點*p在后序序列中的后繼（二叉樹的根結點指針并為給出），并討論實現算法對存儲結構有何要求？6.58試寫出一算法，在中序全線索二叉樹的結點*p之下，插入一棵以結點*x為根只有左子樹的中序全線索二叉樹，使*x為根的二叉樹成為*p的左子樹，若*p原來有左子樹，則令它為*

16、x 的右子樹，完成插入之后的二叉樹應保持全線索化特性。6.59試編寫算法完成下列操作：無重復的輸出以孩子兄弟鏈表存儲的樹T中所有的邊。輸出的形式為（k1 k2），（ki kj）. （ki kj）其中，ki， kj 為樹結點中的結點標識。6.60試編寫算法，對一棵以孩子-兄弟鏈表表示的樹統計葉子的個數。6.61試編寫算法，求一棵以孩子-兄弟鏈表表示的樹的深度。6.62對以孩子-兄弟鏈表表示的樹編寫計算樹的深度的算法。6.63對以雙親表示的樹編寫計算樹的深度的算法。6.65已知一棵二叉樹的前序虛癆和中序序列分別存儲于兩個一維數組中，試將編寫算法建立該二叉樹的二叉鏈表。6.66假設有n個結點的樹T采

17、用了雙親表示法，寫出由此建立樹的孩子-兄弟鏈表的算法。6.67假設以二元組（F，C）的形式輸入一棵樹的諸邊（其中F表示雙親結點的標識，C表示孩子結點標識），且在輸入的二元組序列中，C是按層次順序出現的，F=時 C為根結點標識，若C也為，則表示輸入結束，例如，如下所示樹的輸入序列為： A AB AC AD CE CF 試編寫算法，由輸入的二元組序列建立樹的孩子-兄弟鏈表。6.68已知一棵樹的由根至葉子結點按層次輸入的結點序列及每個結點的度（每層中自左向右輸入），試寫出構造此樹的孩子-兄弟鏈表的算法。6.69假設以二叉鏈表存儲的二叉樹中，每個結點所含數據元素均為單字母，試編寫算法，按樹狀打印二叉樹的算法，例如：左下二叉樹印為右下形狀， CFEADB 6.70如果用大小寫字母標識二叉樹結點，則一棵二叉樹可以用符合下面語法圖的字符序列表示，試寫一個遞歸算法，有這種形式的字符序列，建立相應的二叉樹的二叉鏈表存儲結構。 例如：6.69題所示二叉樹的 輸入形式為A（B（#，D），C（E（#，F），#）。 6.71 假設樹上每個結點所含的數據元素為一個字母，并且以孩子-兄弟鏈表為樹的存儲結構，試寫一個按凹入表方式打印一棵樹的算法，例如；左下所示樹印為右下形狀。 A BEFCGD6.72以孩子鏈表為樹的存儲結構，重做6.71題。6.73若用大寫字母標識樹的結點，則可利用帶標號的廣義表形式表