數據結構(C語言描述)第六章

1、習題6.1 選擇題1、假定在一棵二叉樹中，度為2 的分支結點個數為15，度為 1 的分支結點個數為30個，則葉子結點數為（b ） 。a、15 b、16 c、17 d、 47 2、設 n，m 為一棵樹上的兩個結點，在中根遍歷時，n 在 m 前的條件是（c） 。a、n 在 m 右方b、n 是 m 祖先c、n 在 m 左方d、n 是 m 子孫3、 由帶權為 9、 2、 5、 7的四個葉子結點構造一棵哈夫曼樹，該樹的帶樹路徑長度為 （ d ） 。a、23 b、37 c、46 d、44 4、 如果 f 是由樹 t 轉換而來的二叉樹， 則 t 中結點的前根就是f 中結點的（b ） 。a、中根遍歷b、先根遍

2、歷c、后根遍歷d、按層遍歷5、某二叉樹的先根遍歷結點序列和后根遍歷結點序列剛好相反，則該二叉樹一定是（d） 。a、空樹或只有一個根結點b、完全二叉樹c、二叉排序樹d、高度等于其結點數6.2 填空題1、在樹形結構中，樹根結點沒有（前驅 ）結點，其余每個結點有且只有（一）個前驅結點；葉子結點沒有（后繼 ）結點，其余結點的后繼結點可以（任意多個 ） 。2、在具有n 個結點的二叉樹中，有（n+1）個空指針。3、深度為k 的完全二叉樹至少有（2k-1）個結點，至多有（2k-1）個結點，若按自上而下，從左到右次序給結點從1 開始編號，則編號最小的葉子結點的編號是（n/2+1 ） 。4、由 a，b，c 三個

3、結點構成的二叉樹，共有（5）種不同形態(tài)。5、樹所對應的二叉樹其根結點的（右 ）子樹一定為空。6.3 應用題1、給定的樹如圖6-24（a）所示，回答以下問題：（1）哪個是根結點，哪些是葉子結點？答：根結點是a，葉子結點是b，k，l，m ， g， d， h， i，j。（2） 哪個是結點f 的雙親結點， 哪些是結點f 的祖先結點， 哪些是結點f 的孩子結點？答：結點f 的雙親結點是c，祖先結點是a，c，孩子結點是k，l，m 。（3）哪些是結點c 的子孫結點，哪些是結點c 的兄弟結點？答：結點c 的子孫結點是f，g，k，l，m ，結點 c 的兄弟結點是b，d，e。（4）給定樹的層數是多少，結點i 所在

4、的層數是多少？答：樹的層數為4，結點 i 在第三屋。（5）寫出先根遍歷、后根遍歷和按層遍歷的結點序列。答 ： 先 根 ： abcfklmgdehij。 后 根 ： bklmfgcdhijea。 按 層 ：abcdefghijklm。2、給定的二叉樹如圖6-25 所示：（ 1）寫出先根遍歷、后根遍歷、中根遍歷和按層遍歷的結點序列。答：先根： abdikecfgn。中根： dikbeafcng。后根： kidebfngca。按層：abcdefgtnk。（ 2）畫出先根遍歷和中根遍歷的線索二叉樹。答：a b d e i k c g n f null a b d e i k c g n f null

5、先根遍歷的線索二叉樹中根遍歷的線索二叉樹a b c d e f g k l m h i j a b c e f i d g h （a）將圖中給定的樹轉換成二叉樹（b）將圖中給定的二叉樹轉換成樹a b c d e f g h j k l m i 0 p q n （c）將圖中給定的森林轉換成二叉樹圖 6-24 題 6.3.5 a b d e i k c g n f 圖 6-25 題 6.3.2 3、圖 6-24 中的樹、森林與二叉樹之間進行轉換：（1）將圖（ a）中給定的樹轉換成二叉樹（2）將圖（ b）中給定的二叉樹轉換成樹答：a b c d e f g k l m h i j a b c e f

6、 i d g h （1）（2）（3）將圖（ c）中給定的森林轉換成二叉樹（4）將圖 6-24 中給定的二叉樹轉換成森林答：a b c d e f g h j k l m i o p q n a b d e i k c g n f （3）（4）4、出所有滿足以下條件的二叉樹：（1）先根遍歷和中根遍歷時，得到的結點序列相同答：空樹、只有根結點的二叉樹或所有的結點都沒有左分支的二叉樹。（2）后根遍歷和中根遍歷時，得到的結點序列相同答：空樹、只有根結點的二叉樹或所有的結點都沒有右分支的二叉樹。（3）先根遍歷和后根遍歷時，得到的結點序列相同答：空樹或只有根結點的二叉樹。5、已知，一棵二叉樹中根遍歷的結點

7、序列為dcbgeahfijk ，先根遍歷的結點序列為abcdegfhjik ，畫出對應的二叉樹，并寫出后根遍歷的結點序列。答：解題依據：對先根遍歷得到的結點序列來講，第一個訪問的結點肯定是二叉樹的根結點，根據根結點可以將中根遍歷的結點序列分為左子樹、根結點和右子樹三部分。根據分到的左、右子樹包含的結點將先根遍歷結點序列分出根結點、左子樹和右子樹。對左、右子樹也是按先根遍歷，所以可重復使用上述規(guī)則，就可以分出所有結點在二叉樹中的位置。得到的二叉樹如圖所示：a b c e g f j i h d k 6、一個度為2 的樹與一棵二叉樹有什么區(qū)別？答：一個度為2 的樹是一棵無序樹，它的兩個分支不分順序

8、；二叉樹是一棵有序樹，它的兩個分支是有順序的，分別稱為左右子樹。7、已知如下所示長度為12 的表（ jan,feb,mar,apr,may,june,july,aug,sep,oct,nov,dec ）,按表中元素的順序構造一棵二叉排序樹，插入時按字典序大小進行比較。答：jan feb mar apr aug dec june july may sep oct nov 8、有 7 個帶權結點，其權值分別為：4，7，8，2，5，16，30，試以它們?yōu)槿~子結點構造一棵哈夫曼樹（要求按每個結點的左子樹根結點的權值小于等于右子樹根結點的權值的次序構造） 。答：構造的哈夫曼樹為：30 16 5 7 8

9、2 4 9、假設用于通信的電文僅由8 個字母組成，字母在電文中出現(xiàn)的頻率分別為：0.07，0.19，0.02，0.06， 0.32，0.03，0.21，0.10。試為這8 個字母設計哈夫曼編碼。使用另一種編碼方式是采用二進數的等長編碼，給出每個字母的編碼，并比較兩種編碼方案的優(yōu)缺點。答：第一種方法：哈夫曼編碼。為了簡簡化求哈夫曼樹的過程，將每個字母的出現(xiàn)頻率看成整數，即將0.07 看到是 7，依次類推。則構造的哈夫曼樹如下所示：19 21 6 2 3 7 10 32 0 0 0 0 0 0 1 0 1 1 1 1 1 1 按左分支是0，右分支是1 的規(guī)則編碼，則8 個字母的編碼依次為：1010

10、，00，10000，1001，11，10001，01，1011（如圖所示） 。第二種方法：等長編碼。電文由8 個字母組成，所以共有八種情況，可以用三位二進制數來表示。則8個字母的編碼依次為：000，001， 010， 011，100，101，110，111 。比較：哈夫曼編碼采用了高頻率字母的編碼較短的特點，所以同等個數的電文發(fā)送時翻譯后所得的電文總長會比采用等長編碼要短。假設發(fā)送的電文是52715326451275785，以數字代表八個字母，即數字1 代表第一個字母，依次類推。通過計算可得，蛤夫曼編碼的總長為 48，等長編碼的總長為51。若發(fā)送的電文越長這個優(yōu)點體現(xiàn)的越明顯。6.4 算法題（算法沒做要求）1、編寫一個以二叉鏈表形式存儲的二叉樹中所有葉子結點的個數。2、編寫一個交換二叉鏈表形式存儲的二叉樹中所有結點的左、右子樹的算法。（可作為上機實踐題目）3、編寫一個按從大到小的順序輸出一個以二叉鏈表形式存儲的二叉排序樹的所有結點的算法。4、編寫一個判斷兩棵二叉樹是否等價的算法。等價的條件：如果t1和 t2都是空二叉樹；或者 t1和 t2的根結點的值相同，并且t1的左子樹與t2的左子樹等價，t1的右子樹與t2的右子樹是等價的，則稱t1和 t2是等價的。5、編寫一個復制一棵以二叉鏈