數據結構 第6章_樹型結構

1、1李云清李云清 楊慶紅楊慶紅 揭安全揭安全高等學校精品課程高等學校精品課程（第（第2版）版）（第（第2版）版）23414131211123456789101413121113246578910BDEFGAHIJKC5614131211123456789107141312111234567891089DCEFABDEFABC10BHJKGIEFDCA11ABEFCDGHJKI (C)凹入表示法12 6.2 樹類的定義樹類的定義 13 6.2 樹類的定義樹類的定義 14 6.2 樹類的定義樹類的定義 15 6.2 樹類的定義樹類的定義 161718BCDEFGAHIKJ01234567891019

2、202122rootdatachild0child1 child2 2324012345678910rootBCDEFGAHIKJ252627012345678910child nextdatafirstchildtreelistBCDEFGAHIKJ2829data firstchild rightsiblingrootBCDEFGAHIKJ303132BCDEFGAHI3334353637383940ABCFGHDEJI414243444546ABCFGHDEJI474849505152習題習題66.1 樹最適合用來表示具有（）性和（）性的數據。樹最適合用來表示具有（）性和（）性的數據。6

3、.2 在選擇存儲結構時，既要考慮數據值本身的存儲，還需在選擇存儲結構時，既要考慮數據值本身的存儲，還需要考慮（）的存儲。要考慮（）的存儲。6.3 對于一棵具有對于一棵具有n個結點的樹，該樹中所有結點的度數之和個結點的樹，該樹中所有結點的度數之和為（）。為（）。6.4 已知一棵樹如圖已知一棵樹如圖6.11所示，試回答以下問題：所示，試回答以下問題：圖圖6.11 一棵樹一棵樹53（1）樹中哪個結點為根結點？哪些結點為葉子結點？）樹中哪個結點為根結點？哪些結點為葉子結點？（2）結點）結點B的雙親為哪個結點？其子女為哪些結點？的雙親為哪個結點？其子女為哪些結點？（3）哪些結點為結點）哪些結點為結點I的

4、祖先？哪些結點為結點的祖先？哪些結點為結點B的子孫？的子孫？（4）哪些結點為結點）哪些結點為結點D的兄弟？哪些結點為結點的兄弟？哪些結點為結點K的兄弟？的兄弟？（5）結點）結點J的層次為多少？樹的高度為多少？的層次為多少？樹的高度為多少？（6）結點）結點A、C的度分別為多少？樹的度為多少？的度分別為多少？樹的度為多少？（7）以結點）以結點B為根的子樹的高度為多少？為根的子樹的高度為多少？（8）試給出該樹的括號表示及層號表示形式。）試給出該樹的括號表示及層號表示形式。546.5 試寫出圖試寫出圖6.11所示樹的前序遍歷、后序遍歷和層次遍歷的所示樹的前序遍歷、后序遍歷和層次遍歷的結果。結果。6.6

5、 試給出圖試給出圖6.11所示樹的雙親表示法和數組方式孩子表示法所示樹的雙親表示法和數組方式孩子表示法的表示。的表示。6.7 已知一棵度為已知一棵度為m的樹中有的樹中有n1個度為個度為1的結點，的結點，n2個度為個度為2的的結點，結點，nm個度為個度為m的結點，問該樹中有多少個葉子結的結點，問該樹中有多少個葉子結點？點？6.8 假設樹采用指針方式的孩子表示法表示，試編寫一個非假設樹采用指針方式的孩子表示法表示，試編寫一個非遞歸函數，實現樹的前序遍歷算法。遞歸函數，實現樹的前序遍歷算法。6.9 假設樹采用指針方式的孩子表示法表示，試編寫一個非假設樹采用指針方式的孩子表示法表示，試編寫一個非遞歸函數，實現樹的后序遍歷算法。遞歸函數，實現樹的后序遍歷算法。6.10 假設樹采用指針方式的孩子表示法表示，試編寫一個函假設樹采用指針方式的孩子表示法表示，試編寫一個函數，判斷兩棵給定的