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