數(shù)據(jù)結(jié)構第6章二叉樹作業(yè)及答案教材(編輯修改稿)
2024-07-19 17:06 本頁面
【文章內(nèi)容簡介】 列算法traversal(root)，試指出其輸出結(jié)果；2. 假定二叉樹B共有n個結(jié)點，試分析算法traversal(root)的時間復雜度。（共8分）AB D C F G E二叉樹B解：這是“先根再左再根再右”，比前序遍歷多打印各結(jié)點一次，輸出結(jié)果為：A B C C E E B A D F F D G G特點：①每個結(jié)點肯定都會被打印兩次；②但出現(xiàn)的順序不同，其規(guī)律是：凡是有左子樹的結(jié)點，必間隔左子樹的全部結(jié)點后再重復出現(xiàn)；如A，B，D等結(jié)點。反之馬上就會重復出現(xiàn)。如C，E，F(xiàn)，G等結(jié)點。時間復雜度以訪問結(jié)點的次數(shù)為主，精確值為2*n，時間漸近度為O(n).，分別是：前序遍歷序列：D，A，C，E，B，H，F(xiàn)，G，I； 中序遍歷序列：D，C，B，E，H，A，G，I，F(xiàn)，試畫出二叉樹B，并簡述由任意二叉樹B的前序遍歷序列和中序遍歷序列求二叉樹B的思想方法。解：方法是：由前序先確定root，由中序可確定root的左、右子樹。然后由其左子樹的元素集合和右子樹的集合對應前序遍歷序列中的元素集合，可繼續(xù)確定root的左右孩子。將他們分別作為新的root，不斷遞歸，則所有元素都將被唯一確定，問題得解。 D A C FE GB H I2825 3340 60 08 54 55，請畫出與其對應的中序線索二叉樹。解：要遵循中序遍歷的軌跡來畫出每個前驅(qū)和后繼。中序遍歷序列：55 40 25 60 28 08 33 54282540555560330854NILNIL 2825 33 40 60 08 54 55已知一棵二叉樹，其中序序列DBCAFGE，后序序列DCBGFEA，構造該二叉樹。解：已知葉子結(jié)點值2，3，5，6，9，11，構造哈夫曼樹，計算其帶權路徑長度。解：給定權值{8，12，4，5，26，16，9}，構造一棵帶權路徑長度最短的二叉樹，并計算其帶權路徑長度。解：或： WPL=83+44+54+162+93+123+262 =207[注]：哈夫曼樹的左右子樹可以互換。8. （P60 426）試寫出如圖所示的二叉樹分別按先序、中序、后序遍歷時得到的結(jié)點序列。答：DLR：A B D F J G K C E H I L M LDR: B F J D G K A C H E L I M LRD：J F K G D B H L M I E C A （把如圖所示的樹轉(zhuǎn)化成二叉樹。答：注意全部兄弟之間都要連線（包括度為2的兄弟）,并注意原有連線結(jié)點一律歸入左子樹，新添連線結(jié)點一律歸入右子樹。 A B E C K F H D L G I M J10畫出和下列二叉樹相應的森林。答：注意根右邊的子樹肯定是森林，而孩子結(jié)點的右子樹均為兄弟。6. 1假設用于通信的電文僅由8個字母組成，，，。試為這8個字母設計哈夫曼編碼。使用0～7的二進制表示形式是另一種編碼方案。對于上述實例，比較兩種方案的優(yōu)缺點。解：方案1；哈夫曼編碼先將概率放大100倍，以方便構造哈夫曼樹。 w={7,19,2,6,32,3,21,10}，按哈夫曼規(guī)則：【[（2,3），6], (7,10)】, ……19, 21, 32 0 1 0 1 0 119 21 32 0 10 1 0 17 10 6 0 12 3 （100）（40） （60）19 21 32 （28）（17） （11） 7 10 6 （5） 2 3方案比較：字母編號對應編碼出現(xiàn)頻率111002003111104111051061111170181101字母編號對應編碼出現(xiàn)頻率10002001301040115100610171108111方案1的WPL＝2(++)+4(++)+5(+)=++=方案2的WPL＝3(+++++++)=3結(jié)論：哈夫曼編碼優(yōu)于等長二進制編碼六、算法設計題，計算二叉樹中葉子結(jié)
范文總結(jié)相關推薦
鄂ICP備17016276號-1