數(shù)據(jù)結(jié)構(gòu)課后習(xí)題及解析第六章

1、第六章習(xí)題第六章習(xí)題1試分別畫(huà)出具有3個(gè)結(jié)點(diǎn)的樹(shù)和3個(gè)結(jié)點(diǎn)的二叉樹(shù)的所有不同形態(tài)。2對(duì)題1所得各種形態(tài)的二叉樹(shù)，分別寫(xiě)出前序、中序和后序遍歷的序列。3已知一棵度為k的樹(shù)中有n1個(gè)度為1的結(jié)點(diǎn)，n2個(gè)度為2的結(jié)點(diǎn)，……，nk個(gè)度為k的結(jié)點(diǎn)，則該樹(shù)中有多少個(gè)葉子結(jié)點(diǎn)并證明之。4.假設(shè)一棵二叉樹(shù)的先序序列為EBADCFHGIKJ，中序序列為ABCDEFGHIJK，請(qǐng)畫(huà)出該二叉樹(shù)。5已知二叉樹(shù)有50個(gè)葉子結(jié)點(diǎn)，則該二叉樹(shù)的總結(jié)點(diǎn)數(shù)至少應(yīng)有多少個(gè)

2、？6給出滿(mǎn)足下列條件的所有二叉樹(shù)：①前序和后序相同②中序和后序相同③前序和后序相同7n個(gè)結(jié)點(diǎn)的K叉樹(shù)，若用具有k個(gè)child域的等長(zhǎng)鏈結(jié)點(diǎn)存儲(chǔ)樹(shù)的一個(gè)結(jié)點(diǎn)，則空的Child域有多少個(gè)？8畫(huà)出與下列已知序列對(duì)應(yīng)的樹(shù)Ｔ：樹(shù)的先根次序訪(fǎng)問(wèn)序列為GFKDAIEBCHJ；樹(shù)的后根次序訪(fǎng)問(wèn)序列為DIAEKFCJHBG。9假設(shè)用于通訊的電文僅由8個(gè)字母組成，字母在電文中出現(xiàn)的頻率分別為：0.07，0.19，0.02，0.06，0.32，0.03，0.

3、21，0.10請(qǐng)為這8個(gè)字母設(shè)計(jì)哈夫曼編碼。10已知二叉樹(shù)采用二叉鏈表存放要求返回二叉樹(shù)T的后序序列中的第一個(gè)結(jié)點(diǎn)指針是否可不用遞歸且不用棧來(lái)完成請(qǐng)簡(jiǎn)述原因.11.畫(huà)出和下列樹(shù)對(duì)應(yīng)的二叉樹(shù)：3如題1要求建立好二叉樹(shù)，按凹入表形式打印二叉樹(shù)結(jié)構(gòu)，如下圖所示。2.按凹入表形式打印樹(shù)形結(jié)構(gòu)，如下圖所示。第六章答案61分別畫(huà)出具有3個(gè)結(jié)點(diǎn)的樹(shù)和3個(gè)結(jié)點(diǎn)的二叉樹(shù)的所有不同形態(tài)。【解答】具有3個(gè)結(jié)點(diǎn)的樹(shù)具有3個(gè)結(jié)點(diǎn)的二叉樹(shù)6.3已知一棵度為k的樹(shù)中