資料結構與演算法 第五章 树.pptVIP

第五章　樹 資料結構與演算法 徐熊健 目錄 5.1　樹的概念 5.2　樹的表示法 5.3　二元樹 5.4　二元樹表示法 5.5　二元樹的走訪 5.6　二元樹的複製與相等測試 5.7　引線二元樹 5.8 堆積 5.9 二元搜尋樹 5.10 樹林 5.1　樹的概念 樹 (tree) 是一種重要的離散結構 (discrete structure)，它提供一種「具有層次關係」的概念來結構資料。 樹為節點組成的有限集合，其中 (1)存在一特殊節點R稱為樹根 (root) ； (2)其它節點可分割成n個無交集的集合。T1, T2, …, Tn，n ? 0，而T1、T2、…Tn本身皆為樹，稱其為R的子樹 (subtree) 。 5.1.2　專有名詞 樹的定義：樹為節點組成的有限集合，其中 (1) 存在一特殊節點R稱為樹根 (root) ； (2) 其它節點可分割成n個無交集的集合。 T1, T2, …, Tn，n ? 0，而T1、T2、…Tn本身皆為樹，稱其為R的子樹 (subtree) 。 在本章中若無特別聲明，所提到的樹皆為如定義所描述的「有根樹」 (rooted tree)。 5.1.2　專有名詞(續) 節點:圖中圓圈和向下的分支 樹根:節點A 分支度:一個節點其所有子樹的數目 樹葉:分支度為0的節點 兒子:任何節點X，其子樹的樹根Y，為X的「兒子」 父親:Y是X的「父親」 深度:樹的最高階層 5.2　樹的表示法 一般化的串列表示 左子右兄弟表示法(圖一) 分支度為2的樹示法(圖二) 5.2.1　一般化的串列表示法 上圖的樹可表示成下面的一般化串列： (A, (B, (E, K), (F, L, M), G), (C, H), (D, (I, N), (J, O, P))) 若將節點A的三兒子B、C、D所形成的3個子樹，分別取名為T1、T2、T3，則此樹可簡化成 (A, T1, T2, T3) 其中 T1 = (B, (E, K), (F, L, M), G) T2 = (C, H) T3 = (D, (I, N), (J, O, P)) 程式5-1　一般化串列鍵結節點的宣告 1 struct TreeNode 2 { int tag; 3 union 4 { int data; 5 struct TreeNode *Tlink; 6 } node; 7 struct TreeNode *link; 8 }; 5.2.2　左子右兄弟表示法 每個節點都有唯一的最左兒子 (leftmost child) ； 每個節點都有最靠近它的右兄弟。 5.2.3　分支度為2的樹表示法 分支度為2的樹又稱為二元樹 (binary tree)。 二元樹中任一節點皆有2個 　指標分別指向該節點的左 　子樹和右子樹。 二元樹的節點構造 5.3　二元樹 二元樹是一個由節點組成的有限集合，可以是空集合，或是包含了 (1) 一個樹根節點； (2) 其它節點分割成兩個沒有交集的二元樹，其一為左子樹 (left subtree) ，另一為右子樹 (right subtree) 樹和二元樹之間的差異： (1) 樹不允許空節點，而空二元樹是允許的； (2) 樹的子樹沒有順序，而二元樹的子樹有左右之分。 5.3.1　樹和二元樹的基本性質 樹或二元樹皆擁有下面的性質： 定理5-1：若一棵樹T的總節點數為V，總邊數為 E，則 V = E +1。 5.3.2 二元樹的性質 下圖(a) 稱為歪斜樹 (skew tree) ； (b) 稱為完備二元樹 (complete binary tree) (其樹葉節點皆在相鄰階層，完整定義在後)。 顯而易見地，同樣數目的樹節點放在歪斜樹上，得花較多的階層；放在完備二元樹上，則只須較少的階層。 5.3.2 二元樹的性質(續) 定理5-2說明了： (1) 每一階層上可放的最多節點數； (2) 階層數已知時，二元樹可放的最多節點數。 定理5-2： (1) 二元樹上階層i的節點數目最多為2i-1，i ? 1； (2) 深度為k的二元樹，其節點數目最多為2k-1，k ? 1。 對二元樹而言，任一節點的分支度可能為0、1、或2；分支度為0者是為樹葉。樹葉的數目與分支度為2的節點數目，存在著有趣的關係，請見定理5-3。 定理5-3： 若T為一非空的二元樹，n0為樹葉節點數目，n2為分支度為2的節點數目，則n0 = n2+1。 5.3.2 二元樹的性質(續) 下面是完滿二元樹 (full binary tree) 和完備二元樹 (complete binary tree) 的定義： 定義：一個深度為k的完滿二元樹即為一深度為k且有2k-1 個節點的二元樹，k?0。 由定理5-2