資料結構–樹(Tree) 2013.05 綠園.

Presentation on theme: "資料結構–樹(Tree) 2013.05 綠園."— Presentation transcript:

1 資料結構–樹(Tree) 綠園

2 樹(Tree) Tree是一種特殊的資料結構，是由一個或一個以上的節點所組成的有限集合。 具有下列特質：
存在一個特殊的節點，稱為樹根(root)。 其餘的節點分為 n≥0 個互斥的集合，T1,T2, T3,...Tn，且每個集合稱為子樹。

3 樹(Tree) Tree是一種特殊的資料結構，是由一個或一個以上的節點所組成的有限集合。 具有下列特質：
存在一個特殊的節點，稱為樹根(root)。 其餘的節點分為 n≥0 個互斥的集合，T1,T2, T3,...Tn，且每個集合稱為子樹。 A為根節點 A Ｂ、Ｃ、Ｄ、Ｅ 均為Ａ的子節點 B C D E

4 樹(Tree)的專有名詞 樹由一個以上的節點（node)與將節點連接起來的分支（branch)所組成。
節點分支出來的節點稱為「子節點」，其上層的節點稱為「父節點」。 樹的最上面節點稱為「根」（root)。 底下沒有子節點的節點稱為葉子（leaf)。

5 樹(Tree)的專有名詞 樹由一個以上的節點（node)與將節點連接起來的分支（branch)所組成。
節點分支出來的節點稱為「子節點」，其上層的節點稱為「父節點」。 樹的最上面節點稱為「根」（root)。 底下沒有子節點的節點稱為葉子（leaf)。 A B C D E F G H A 為 root DEFGH 為 leaf

6 範例 1 下列哪一種不是樹(Tree)？ (A)一個節點 (B)環狀串列 (C)一個沒有迴路的連通圖(Connected Graph) (D)一個邊數比點數少1的連通圖。 範例 2 下圖中樹(tree)有幾個樹葉節點(leaf node)？ (A)4 (B)5 (C)9 (D)11

7 二元樹(binary tree) 樹的各節點分支如在2個以下（含2個），則稱為二元樹（binary tree)

8 二元樹(binary tree) 樹的各節點分支如在2個以下（含2個），則稱為二元樹（binary tree) A B C F G D E
H

9 二元樹(binary tree) 樹的各節點分支如在2個以下（含2個），則稱為二元樹（binary tree) A B C F G D E
H 二元樹（binary tree)

10 樹的深度、階度與高度 Depth（深度）：由根到某個節點間所通過的分支數，稱為該節點的深度。
Level（階層或階度）：樹的層級，假設樹根A為階層1，BC節點即為階層2，FGH為階層4。 Height（高度）：樹的最大階度，稱為樹的高度。 問： 節點B、G、E的深度分別為？ 樹的高度為？ 節點A（根）的深度為？ A B C F G D E H

11 完全二元樹 v.s 完整二元樹 完滿二元樹(full binary tree) 完整二元樹(complete binary tree) 1
2 3 4 5 6 7 1 2 3 4 5 (full binary tree) (complete binary tree)

12 二元樹串列表示法 所謂二元樹的串列表示法，就是利用鏈結串列來儲存二元樹。 也就是運用動態記憶體及指標的方式來建立二元樹。其節點結構如下：
left *ptr data right *ptr 指向左子樹 節點值 指向右子樹

13 節點宣告方式如下： 可以把下圖二元樹表示成： class Node { public: int data;
class Node *left; class Node *right; } typedef class Node TreeNode; typedef TreeNode *btree;

14 二元樹的走訪 二元樹的走訪(Binary Tree Traversal)，最簡單的說法就是「拜訪樹中所有的節點各一次」，並且在走訪後，將樹中的資料轉化為線性關係。 如右圖，共可以有ABC、ACB、BAC、BCA、CAB、CBA 等6種走訪方法。 如果是依照二元樹特性，一律由左向右，那會只 剩下三種走訪方式，分別是BAC、ABC、BCA三 種。

15 中序走訪（inorder traversal)
中序走訪的順序為：左子樹→樹根→右子樹。就是沿樹的左子樹一直往下，直到無法前進後退回父節點，再往右子樹一直往下。 如果右子樹也走完了就退回上層，再重覆左、中、右的順序走訪。 如上例的中序走訪為：DBEACF

16 遞迴演算法 void inorder (btree ptr) { if (ptr != NULL) {
　{ 　　inorder(ptr->left);　 /* 走訪左子樹 */ 　　cout << ptr->data; /* 走訪列印樹根 */ 　　inorder(ptr->right); /* 走訪右子樹 */ }

17 前序走訪（preorder traversal)
前序走訪的順序為：樹根→左子樹→右子樹。前序走訪就是從根節點開始處理，根節點處理完往左子樹走，直到無法前進再處理右子樹。 如上例的前序走訪為：ABDECF

18 遞迴演算法 void preorder (btree ptr) { if (ptr != NULL) {
　{ 　　　cout << ptr->data; 　 /* 走訪列印樹根 */ 　　　preorder(ptr->left); 　 /* 走訪左子樹 */ 　　　preorder(ptr->right);　/* 走訪右子樹 */ 　　} }

19 後序走訪（postorder traversal)
後序走訪的順序為：左子樹→右子樹→樹根。 後序走訪和前序走訪的方法相反，它是把左子樹的節點和右子樹的節點都處理完了才處理樹根。 如上例的後序走訪為：DEBFCA

20 遞迴演算法 void postorder (btree ptr) { if (ptr != NULL) {
　{ 　　　postorder(ptr->left); /* 走訪左子樹 */ 　　　postorder(ptr->right); /* 走訪右子樹 */ 　　　cout << ptr->data; 　/* 走訪列印樹根 */ 　　} }

21 決定唯一二元樹 在二元樹的三種走訪方法中，如果有中序與前序的走訪結果或者中序與後序的走訪結果，可由這些結果求得唯一的二元樹。
不過如果只具備前序與後序的走訪結果就無法決定唯一二元樹。 馬上來示範一個範例。例如二元樹的中序走訪為BAEDGF，前序走訪為ABDEFG。請畫出此唯一的二元樹。

22 範例 3 某二元樹的中序走訪為HBJAFDGCE，前序走訪為ABHJCDFGE，請繪出此二元樹。

23 解答： 中序走訪：左子樹 樹根 右子樹 前序走訪：樹根 左子樹　右子樹 1. 3. 2. D為右子樹的節點

24 二元運算樹 一般的算術式也可以轉換成二元運算樹(Bianry Expression Tree)的方式，建立的方法可根據以下二種規則：
1.考慮算術式中運算子的結合性與優先權，再適當地加上括號。 2.再由最內層的括號逐步向外，利用運算子當樹根，左邊運算元當左子樹，右邊運算元當右子樹，其中優先權最低的運算子做為此二元運算樹的樹根。

25 範例 4 範例 5 請將 A/B*C+D*E-A*C 化為二元運算樹。 寫出下列算術式的二元樹與後序表示法。
(a+b)*d + e/(f+a*d) + c

26 範例 6 請問以下運算二元樹的中序、後序與前序的表示法為何？