Download presentation
Presentation is loading. Please wait.
1
資料結構與C++程式設計進階 樹狀結構(Tree) 講師：林業峻 CSIE, NTU 11/ 12, 2009
2
大綱 樹 (Tree) 二元樹 (Binary Tree) 二元搜尋樹 (Binary Search Tree)
3
樹 「樹」（Tree） 用途：資料大量且常需要做搜索時
是一種模擬現實生活中樹幹和樹枝的資料結構，屬於一種階 層架構的非線性資料結構，例如：家族族譜, 決策模型 用途：資料大量且常需要做搜索時
4
樹的基本術語 樹的樹根稱為「根節點」（Root），在根節點之 下是樹的樹枝，擁有0到n個「子節點」（ Children），即樹的「分支」（Branch） 節點A是樹的根節點，B、C、D….和H是節點A的 子節點
5
樹的基本術語 在樹枝下還可以擁有下一層樹枝，I和J是B的子節 點，K、L和M是E的子節點，節點B是I和J的「父 節點」（Parent），節點E是K、L和M的父節點
6
樹的相關術語 n元樹：樹的一個節點最多擁有n個子節點。 二元樹（Binary Trees）：樹的節點最多只有兩個 子節點。
根節點（Root）：沒有父節點的節點是根節點。 例如：節點A。 葉節點（Leaf）：節點沒有子節點的節點稱為葉 節點。 例如：節點I、J、C、D、K、L、M、F、G和H。
7
樹的相關術語 分支度（Dregree）：指每個節點擁有的子節點數
例如：節點B的分支度是2，節點E的分支度是3。 階層（Level）：如果樹根是1，其子節點是2，依 序可以計算出樹的階層數。 例如：上述圖例的節點A階層是1，B、C到H是階層2，I、J到 M是階層3。 樹高（Height）： 樹高又稱為樹深（Depth） ，指樹的最大階層數。 例如：圖例的樹高是3。
8
大綱 樹 (Tree) 二元樹 (Binary Tree) 二元搜尋樹 (Binary Search Tree)
9
二元樹 樹依不同分支度可以區分成很多種，在資料結構 中最廣泛使用的樹狀結構是「二元樹」（Binary Trees）
二元樹是指樹中的每一個「節點」（Node）最多 只能擁有2個子節點，即分支度小於或等於2。 二元樹的定義如下所示： 二元樹的節點個數是一個有限集合，或是沒有節點的空 集合。二元樹的節點可以分成兩個沒有交集的子樹，稱 為「左子樹」（Left Sub-tree）和「右子樹」（Right Sub-tree）。
10
二元樹節點 = 資料+ 結構指標(左) + 結構指標(右)
二元樹鏈結表示法 二元樹節點鏈結表示法 節點 資料 資料 結構指標 (左指標) 結構指標 (右指標) 左節點 右節點 二元樹節點 = 資料+ 結構指標(左) + 結構指標(右)
11
二元樹鏈結表示法 二元樹節點鏈結表示法 node * root node 資料 (malloc)
struct binary_tree_node { 資料型態 變數名稱; struct binary_tree_node *left; struct binary_tree_node *right; }; typedef struct binary_tree_node node; node *root; root = (node *)malloc(sizeof(node)); root ->left= NULL; root ->right= NULL; node * root node 資料 left NULL NULL right (malloc)
12
練習 試著建立一個二元樹如下圖所示 root 5 5 4 6 4 6 NULL NULL NULL NULL
13
二元樹的走訪 陣列和單向鏈結串列都只能從頭至尾或從尾至頭 執行單向「走訪」（Traverse），不過二元樹的每 一個節點都擁有指向左和右2個子節點的指標，所 以走訪可以有兩條路徑。
14
二元樹的走訪種類 二元樹的走訪過程是持續決定向左或向右走，直 到沒路可走。二元樹的走訪是一種遞迴走訪，依 照遞迴函數中呼叫的排列順序不同，可以分成三 種走訪方式，如下所示： 中序走訪方式（Inorder Traversal）。 前序走訪方式（Preorder Traversal）。 後序走訪方式（Postorder Traversal）。
15
二元樹的走訪種類 中序走訪（Inorder Traversal）。 中序: 1,2,3,4,5,6,7,8,9
void print_inorder(node *ptr) { if(ptr != NULL) print_inorder(ptr->left); printf("[%2d]\n", ptr->data); print_inorder(ptr->right); } 中序: 1,2,3,4,5,6,7,8,9
16
練習 前序走訪（Preorder Traversal）。 後序走訪（Postorder Traversal）。
void print_preorder(node *ptr) { if(ptr != NULL) // 前序: 5,4,2,1,3,6,8,7,9 } void print_postorder(node *ptr) { if(ptr != NULL) // 後序: 1,3,2,4,7,9,8,6,5 }
17
二元樹的搜尋 利用二元樹走訪實作二元樹的搜尋 8 node *searchNode(node *ptr, int value) {
node *temp; if(ptr != NULL) if(ptr->data == value) return ptr; else temp = searchNode(ptr->left, value); if(temp != NULL) return temp; temp = searchNode(ptr->right, value); } return NULL; 8
18
大綱 樹 (Tree) 二元樹 (Binary Tree) 二元搜尋樹 (Binary Search Tree)
19
二元搜尋樹 「二元搜尋樹」（Binary Search Trees）是一種 二元樹，其節點資料的排列擁有一些特性，如下 所示：
二元樹的每一個節點值都不相同，在整棵二元樹中的每一個 節點都擁有不同值。 每一個節點的資料大於左子節點的資料，但是小於右子節點 的資料。 節點的左、右子樹也是一棵二元搜尋樹。 (BinarySearchTree.c)
20
二元搜尋樹: 插入 18 node *insertNode(node *root, node data) { node *new_node; node *current; node *parent; // 建立節點 new_node = (node *)malloc(sizeof(node)); *new_node = data; if(root == NULL) // 目前無資料 return new_node; else current = root; // 從頭找要新節點之插入點 while(current != NULL) parent = current; // 找新節點之父節點 if(current->data > new_node->data) current = current->left; // 往左找 current = current->right; // 往右找 } if(parent->data > new_node->data)// 插入此父節點左邊或右邊 parent->left = new_node; parent->right = new_node; return root; // 回傳此樹 10 5 20 1 8 15 30 10 5 20 1 8 15 30 18
21
二元搜尋樹: 搜尋 利用資料的排列特性可以快速搜尋到資料 比較：一般二元樹的搜尋 10 5 20 1 8 15 30
node *searchNode(node *root, int value) { node *ptr = root; while(ptr != NULL) if(ptr->data == value) // 找到目標 return ptr; // 回傳此節點 else if(ptr->data > value) ptr = ptr->left; // 往左找 ptr = ptr->right; // 往右找 } return NULL; // 找不到 10 5 20 1 8 15 30
22
二元搜尋樹: 刪除 必須先取得欲刪節點之父節點 判斷此節點為父節點之左節點或右節點 考量三種情況： (程式碼詳見範例程式)
情況1: 節點沒有左子樹 情況2: 節點沒有右子樹 情況3: 節點有左右子樹 (程式碼詳見範例程式) 10 5 20 1 8 15 30
23
二元搜尋樹: 刪除 情況1: 節點沒有左子樹 (1)如果要刪的是根節點 (2)要刪除的節點在父節點右方 (3)要刪除的節點在父節點左方
root root 10 30 30 25 35 25 35
24
二元搜尋樹: 刪除 情況1: 節點沒有左子樹 (1)如果要刪的是根節點 (2)要刪除的節點在父節點右方 (3)要刪除的節點在父節點左方
root root 10 10 20 30 30 25 35 25 35
25
二元搜尋樹: 刪除 情況1: 節點沒有左子樹 (1)如果要刪的是根節點 (2)要刪除的節點在父節點右方 (3)要刪除的節點在父節點左方
root root 50 50 20 30 30 25 35 25 35
26
二元搜尋樹: 刪除 情況2: 節點沒有右子樹 (1)如果要刪的是根節點 (2)要刪除的節點在父節點右方 (3)要刪除的節點在父節點左方
root 10 root 5 5 2 7 2 7
27
二元搜尋樹: 刪除 情況2: 節點沒有右子樹 (1)如果要刪的是根節點 (2)要刪除的節點在父節點右方 (3)要刪除的節點在父節點左方
root 1 root 1 8 5 5 2 7 2 7
28
二元搜尋樹: 刪除 情況2: 節點沒有右子樹 (1)如果要刪的是根節點 (2)要刪除的節點在父節點右方 (3)要刪除的節點在父節點左方
root 10 root 8 10 5 5 2 7 2 7
29
二元搜尋樹: 刪除 情況3: 節點有左右子樹 往左子節點之右子樹找最大值當取代點 root root 10 8 5 20 5 20 8 15
30 7 15 30 7
30
練習 使用二元搜尋樹製作一個通訊錄程式 (Addressbook_Tree.c) 功能
輸入’i’ 新增節點,可輸入姓名, 電話, 依據姓名字母順序插入 節點(假設輸入之姓名不會重覆) 輸入’d’接著輸入姓名，可將一筆資料節點中之姓名相同者 刪除(假設輸入之姓名不會重覆) 輸入’f’接著輸入一個姓名，可將一筆資料節點中之姓名相 同者印出資料 輸入’l’依據姓名字母順序印出所有節點內容 輸入’q’ 讀取離開程式
Similar presentations
