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

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

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

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