數據結構第六章：樹與二叉樹習題解析指南（嚴蔚敏版）

章節概覽

本文彙總了《數據結構》（嚴蔚敏、吳偉民版）第六章「樹和二叉樹」配套習題集的完整解析。內容涵蓋基礎知識題與算法設計題兩大類，並按存儲結構分類，包括順序存儲、二叉鏈表、線索二叉樹、孩子-兄弟鏈表、孩子鏈表、雙親表等多種實現方式。所有習題均附有詳細解題思路、代碼實現及測試數據說明，適合作為數據結構課程輔助教材或考研復習參考。

一、基礎知識題（6.1~6.32）

樹的基本概念與性質

6.1 給定結點關係集合，繪製樹並回答根、葉、雙親、祖先、孩子、子孫、兄弟、層次、深度等核心概念問題。
6.2 區分度為2的樹與二叉樹的本質差異。
6.3 列舉3個結點的樹與二叉樹所有不同形態。
6.4 推導滿k叉樹按層次編號時的結點數、父結點、孩子結點、右兄弟編號公式。
6.5~6.10 利用度與結點數關系求葉子數、證明滿k叉樹葉子與非葉子關系、完全三叉樹深度推導、全二叉樹結點數證明等。
6.11 比較二叉樹順序存儲與三叉鏈表空間效率。
6.12~6.14 遍歷序列計算、中序線索化判斷左右關系、特殊遍歷序列相同條件下的二叉樹結構。
6.15~6.18 後序線索化、先序線索化構建、中序線索樹後繼查找算法修正、中序全線索樹查找後序後繼可行性討論。
6.19~6.24 樹/森林與二叉樹相互轉換、先根/後根遍歷、由遍歷序列重建樹/森林。
6.25~6.26 證明哈夫曼樹無度為1結點、構建哈夫曼編碼並與定長編碼比較。
6.27~6.29 由兩種遍歷序列（先中、中後、層中）重建二叉樹。
6.30~6.32 祖先關系與遍歷序列關系證明、先中序列唯一確定二叉樹、棧排列與二叉樹中序關系證明。

二、算法設計題

二叉樹順序存儲（6.33~6.35）

利用兩個一維數組模擬左/右孩子，或構建父結點數組，判定祖先關系；基於順序存儲下標計算對應二進制路徑編碼。

二叉鏈表基本操作（6.36~6.55）

• 6.36 判斷兩棵二叉樹是否相似（結構同構）。
• 6.37~6.38 先序/後序非遞歸遍歷（後序需標誌位區分返回點）。
• 6.39~6.40 增設父指針與標誌域實現無棧後序/中序遍歷。
• 6.41~6.44 遞歸求先序第k結點、葉子數、交換左右子樹、指定值子樹深度。
• 6.46 非遞歸復制二叉樹。
• 6.47 層次遍歷（廣度優先）。
• 6.48 求兩結點最近公共祖先。
• 6.49 判斷完全二叉樹。
• 6.50 由三元組（父、孩子、左/右）按層次建立二叉鏈表。
• 6.51 輸出帶括號的算術表達式。
• 6.52 計算二叉樹「繁茂度」（最大層寬×高度）。
• 6.53 輸出根到最左最深葉子路徑。
• 6.54 完全二叉樹順序表轉二叉鏈表。
• 6.55 統計每結點子孫數並存入DescNum域，給出時間複雜度。

線索二叉樹（6.56~6.58）

• 6.56 先序後繼線索樹查找後繼（根指針未知）。
• 6.57 後序後繼線索樹查找後繼（根指針未知）。
• 6.58 中序全線索樹插入左子樹並保持線索特性。

孩子-兄弟鏈表（6.59~6.62）

• 6.59 輸出樹所有邊（無重複）。
• 6.60 統計葉子數。
• 6.61 求樹的度。
• 6.62 計算樹的深度。

孩子鏈表（6.63）

計算樹的深度。

雙親表表示（6.64）

計算樹的深度。

由遍歷序列建樹（6.65）

已知先序與中序數組建立二叉鏈表。

孩子-兄弟鏈表構建（6.66~6.68）

• 6.66 由雙親表示法轉孩子-兄弟鏈表。
• 6.67 由二元組（父、孩子）按層次建立孩子-兄弟鏈表。
• 6.68 由層次輸入的結點序列及度構建孩子-兄弟鏈表。

樹形打印與廣義表互轉（6.69~6.76）

• 6.69 二叉鏈表按樹形狀打印。
• 6.70 由語法圖字符序列遞歸建立二叉鏈表。
• 6.71 孩子-兄弟鏈表凹入式打印。
• 6.72 孩子鏈表凹入式打印。
• 6.73~6.74 廣義表字符序列與孩子-兄弟鏈表互轉遞歸算法。
• 6.75~6.76 廣義表字符序列與孩子鏈表互轉遞歸算法。

資源鏈接

課本源碼、習題解析合輯、測試數據下載請參考原文檔說明中的鏈接。