《資料結構與演算法 第五章 树》由会员分享，可在线阅读，更多相关《資料結構與演算法 第五章 树（54页珍藏版）》请在金锄头文库上搜索。
1、第五章 樹,資料結構與演算法,徐熊健,目錄,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的子樹 (subtre
2、e) 。,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 樹的表示法,一般化
3、的串列表示 左子右兄弟表示法(圖一) 分支度為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 Tree
4、Node 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個 指標分別指向該節點的左 子樹和右子樹。,二元樹的節點構造,分支度為2的樹表示法,5.3 二元樹,二元樹是一個由節點組成的有限集合，可以是空集合，或是包含了
5、(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) (其樹葉節點皆在相鄰階層，完
6、整定義在後)。 顯而易見地，同樣數目的樹節點放在歪斜樹上，得花較多的階層；放在完備二元樹上，則只須較少的階層。,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的
7、節點數目，則n0 = n2+1。,5.3.2 二元樹的性質(續),下面是完滿二元樹 (full binary tree) 和完備二元樹 (complete binary tree) 的定義： 定義：一個深度為k的完滿二元樹即為一深度為k且有2k-1 個節點的二元樹，k0。 由定理5-2 (2) 可得深度k的二元樹其最多節點數E 為2k-1。這樣的樹會將樹上所有可能存放節點的 位置都已放滿，完滿 (full) 之名因而生成。 我們可對二元樹上節點予以編號，階層小者先編， 同一階層則自左向右編號，這樣的編號方式， 使我們定義出完備二元樹。 定義：深度為k，節點數為n的二元樹稱為完備二元樹， 若且唯
8、若以階層小者先編號，同一階層由左至右遂一編 號方法，可將1到n號分別找到對應的節點。 完滿或完備二元樹之所以受人注意，乃因它們可 以將節點以較少的階層數存放。,5.3.2 二元樹的性質(續),定理5-4：n個節點的完備或完滿二元樹，其深度為 log2(n+1)。,在二元樹中非樹葉的節點，又稱為內部節點 (internal node) 。若所有內部節點恰有2個子節點，即成為正規二元樹。正式定義如下： 定義：若二元樹中所有內部節點恰有2個子節點，則稱之為正規二元樹 (formal binary tree) 。,正規二元樹常被引用在單淘汰賽制的各項賽程安排。樹葉為參賽隊伍，內部節點為優勝隊伍，樹根即
9、為冠軍隊伍。,5.4 二元樹的表示法,5.4.1以陣列表示二元樹 定理5-5：若一個具有n個節點的完備二元樹以循序的方式編號，並依序存放在陣列A中，即第i個節點放在Ai中，1 i n，則 (1) 節點i的父節點位在Ai2處，i 1（i = 1時，其節點正為樹根，無父節點）。 (2) 若2i n，則節點i的左兒子節點位在A2i處；若2i n，節點i沒有左兒子節點。 (3) 若2i+1 n，節點i的右兒子節點位在A2i+1處；若2i+1 n，節點i沒有左兒子節點。,5.5 二元樹的走訪,假如一組資料已用二元樹的組織在一起，總有需求對其全數資料做動作，例如計算所有數目、印出所有資料、在所有資料中搜尋
10、某項資料、等。此時即須對此二元樹做走訪 (traversal) 的運算，利用走訪二元樹的同時，將計算、列印或搜尋的動作完成。 事實上走訪即在決定二元樹上資料被處理（計算、列印或搜尋）的順序。我們也希望走訪的演算法對任何節點皆一致，是容易撰寫程式實作的。 若對一個二元樹上的節點而言，V表示處理節點上的資料，L表示走訪其左子樹，R表示走訪其右子樹。,5.5 二元樹的走訪(續),因為對稱的緣故，我們可以只考慮先走訪左邊再走訪右邊的情形，那麼圖5-20 (b) 則只剩下三種走訪方式，我們以V所在的相對位置，分別對此三種走訪方式取名如下： (1) LVR中序走訪 (inorder traversal)
11、或中序表示法 (infix notation)； (2) LRV後序走訪 (postorder traversal) 或後序表示法 (postfix notation)； (3) VLR前序走訪 (preorder traversal) 或前序表示法 (prefix notation)。,5.5.1 中序走訪,利用遞迴的方式撰寫中序走訪的程序；希望把二元樹中序走訪的順序印出來。,程式5-3二元樹的中序走訪 1 struct BTreeNode 2 struct BTreeNode *leftchild; 3 char data; 4 struct BTreeNode *rightchild;
12、5 ; 6 struct BTreeNode *root; 7 void inorder(struct BTreeNode *node) 8 if (node != NULL) 9 inorder(node-leftchild); 10 cout data; 11 inorder(node-rightchild); 12 13 ,範例 5-12,下圖為一棵運算式二元樹。,其對應中序表示運算式為 ： (A+B)*C+D/(E-F)。,5.5.2 後序走訪,茲將後序走訪的程序撰寫如下： 程式5-4二元樹的後序走訪 14 void postorder(struct BTreeNode *node)
13、15 if (node !=NULL) 16 postorder(node-leftchild); 17 postorder(node-rightchild); 18 cout data; 19 20 ,以後序走訪，列出右圖之運算式二元樹中的所有資料，可得到： AB+C*D-/+ 其正為對應的後序運算式。,5.5.3 前序走訪,前序走訪的程序可撰寫如下： 程式5-5二元樹的前序走訪 21 void preorder(struct BTreeNode *node) 22 if (node != NULL) 23 cout data; 24 preorder(node-leftchild); 25
14、 preorder(node-rightchild); 26 27 ,以前序走訪，列出右圖之運算式二元樹中的所有資料，可得到： +*+ABC/D-EF 其正為對應的前序運算式。,5.5.5 階層走訪,階層走訪 (level-order traversal) 是依階層的順序，進行二元樹的走訪，先走訪階層小的節點，後走訪階層大的節點，同一階層者則依自左向右的順序走訪。 對下圖的二元樹，進行階層走訪的結果為： ABCDEFGHI。 對同一階層而言，先走訪的節點，其子節點亦在下一階層中先被走訪。這種先進先出的特性，恰可用佇列予以儲存與處,5.6 二元樹的複製與相等測試,5.6.1 二元樹的複製 二元樹
15、的複製可以用遞迴的方式來完成，請看下面的程序： 程式5-8 二元樹的複製 1 struct BTreeNode 2 struct BTreeNode *leftchild; 3 char data; 4 struct BTreeNode *rightchild; 5 ; 6 struct BTreeNode *root; 7 struct BTreeNode *Copy(struct BTreeNode *TreeRoot) 8 struct BTreeNode *CopyRoot; 9 if (TreeRoot = NULL) 10 return NULL; 11 CopyRoot = (s
16、truct BTreeNode *) malloc (sizeof(BTreeNode); 12 CopyRoot-data = TreeRoot-data; 13 CopyRoot-leftchild = Copy(TreeRoot-leftchild); 14 CopyRoot-rightchild = Copy(TreeRoot-rightchild); 15 return CopyRoot; 16 ;,5.6.2 二元樹的相等,下面的程式用遞迴的方式，檢測兩棵二元樹是否相等。 程式5-9 檢測兩棵二元樹是否相等 1 struct BTreeNode 2 struct BTreeNode *leftchild; 3 char data; 4 struct BTreeNode *rightchild; 5 ; 6 struct BtreeNode *rightchild; 7
