Tree

Size: px

Start display at page:

Download "Tree"

翼绅富
5 years ago
Views:

1 樹狀結構 Tree 講師 : 洪安

2 大綱樹 (Tree) 二元樹 (Binary Tree) 二元搜尋樹 (Binary Search Tree) 課堂練習 2

3 樹樹 (Tree) 是一種模擬現實生活中樹幹和樹枝的資料結構, 屬於一種階層架構的非線性資料結構, 例如 : 家族族譜, 決策模型 3

4 樹的基本術語樹的樹根稱為根節點 (Root), 在根節點之下是樹的樹枝, 擁有 0 到 n 個子節點 (Children), 即樹的分支 (Branch), 節點 A 是樹的根節點,B C D. 和 H 是節點 A 的子節點, 即樹枝 4

5 樹的基本術語在樹枝下還可以擁有下一層樹枝,I 和 J 是 B 的子節點,K L 和 M 是 E 的子節點, 節點 B 是 I 和 J 的父節點 (Parent), 節點 E 是 K L 和 M 的父節點, 節點 I 和 J 擁有共同父節點, 稱為兄弟節點 (Siblings),K L 和 M 是兄弟節點,B C 和 H 節點也是兄弟節點 5

6 樹的相關術語 n 元樹 : 樹的一個節點最多擁有 n 個子節點二元樹 (Binary Trees): 樹的節點最多只有兩個子節點根節點 (Root): 沒有父節點的節點是根節點例如 : 節點 A 葉節點 (Leaf): 節點沒有子節點的節點稱為葉節點例如 : 節點 I J C D K L M F G 和 H 祖先節點 (Ancenstors): 指某節點到根節點之間所經過的所有節點, 都是此節點的祖先節點 6

7 樹的相關術語非終端節點 (Non-terminal Nodes): 除了葉節點之外的其它節點稱為非終端節點例如 : 節點 A B 和 E 是非終端節點分支度 (Dregree): 指每個節點擁有的子節點數例如 : 節點 B 的分支度是 2, 節點 E 的分支度是 3 階層 (Level): 如果樹根是 1, 其子節點是 2, 依序可以計算出樹的階層數例如 : 上述圖例的節點 A 階層是 1,B C 到 H 是階層 2,I J 到 M 是階層 3 樹高 (Height): 樹高又稱為樹深 (Depth), 指樹的最大階層數例如 : 圖例的樹高是 3 7

8 大綱樹 (Tree) 二元樹 (Binary Tree) 二元搜尋樹 (Binary Search Tree) 課堂練習 8

9 二元樹樹依不同分支度可以區分成很多種, 在資料結構中最廣泛使用的樹狀結構是二元樹 (Binary Trees) 二元樹是指樹中的每一個節點 (Node) 最多只能擁有 2 個子節點, 即分支度小於或等於 2 二元樹的定義如下所示 : 二元樹的節點個數是一個有限集合, 或是沒有節點的空集合二元樹的節點可以分成兩個沒有交集的子樹, 稱為左子樹 (Left Sub-tree) 和右子樹 (Right Sub-tree) 9

10 二元樹陣列表示法 (1/2) 一棵樹高 h 擁有 2 h-1 個節點的二元樹, 這是二元樹在樹高 h 所能擁有的最大節點數換句話說, 只需配置 2 h-1 個元素, 我們就可以儲存樹高 h 的二元樹, 如下圖所示 10

11 二元樹陣列表示法 (2/2) 二元樹的節點編號擁有循序性, 根節點 1 的子節點是節點 2 和節點 3, 節點 2 是 4 和 5, 依此類推可以得到節點編號的規則, 如下所示 : 左子樹是父節點編號乘以 2 右子樹是父節點編號乘以 2 加 1 11

12 二元樹鏈結表示法 (1/2) 二元樹節點鏈結表示法資料結構指標 ( 左指標 ) 左節點節點資料右節點結構指標 ( 右指標 ) 二元樹節點 = 資料 + 結構指標 ( 左 ) + 結構指標 ( 右 ) 12

13 二元樹鏈結表示法 (2/2) 二元樹節點鏈結表示法 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 (malloc) right 13

14 二元樹 : 歪斜樹左邊這棵樹沒有右子樹, 右邊這棵樹沒有左子樹, 雖然擁有相同節點, 但是這是兩棵不同的二元樹, 因為所有節點都是向左子樹或右子樹歪斜, 稱為歪斜樹 (Skewed Tree) 資料資料資料資料資料資料 14

15 二元樹 : 完滿二元樹若二元樹的樹高是 h 且二元樹的節點數是 2 h -1, 滿足此條件的樹稱為完滿二元樹 (Full Binary Tree) 資料資料資料資料資料資料資料 15

16 二元樹 : 完滿二元樹因為二元樹的每一個節點有 2 個子節點, 二元樹樹高是 3, 也就是有 3 個階層 (Level), 各階層的節點數, 如下所示 : 第 1 階 :1 = 2 (1-1) = 2 0 = 1 第 2 階 : 第 1 階節點數的 2 倍,1*2 = 2 (2-1) = 2 第 3 階 : 第 2 階節點數的 2 倍,2*2 = 2 (3-1) = 4 以此類推, 得到每一階層的最大節點數是 :2 (l-1),l 是階層數, 整棵二元樹的節點數一共是 : = 7 個, 即 2 3-1, 可以得到 : (h-1) = 2 h -1,h 是樹高

17 二元樹 : 完整二元樹若二元樹的節點不是葉節點, 一定擁有 2 個子節點, 不過節點總數不足 2 h -1, 其中 h 是樹高, 而且其節點編號是對應相同高度完滿二元樹的節點編號, 滿足此條件稱為完整二元樹 (Complete Binary Tree) 資料資料資料資料資料

18 小練習試著建立一個二元樹如下圖所示 root NULL NULL NULL NULL

19 二元樹的走訪陣列和單向鏈結串列都只能從頭至尾或從尾至頭執行單向走訪 (Traverse), 不過二元樹的每一個節點都擁有指向左和右 2 個子節點的指標, 所以走訪可以有兩條路徑

20 二元樹的走訪種類二元樹的走訪過程是持續決定向左或向右走, 直到沒路可走二元樹的走訪是一種遞迴走訪, 依照遞迴函數中呼叫的排列順序不同, 可以分成三種走訪方式, 如下所示 : 中序走訪方式 (Inorder Traversal) 前序走訪方式 (Preorder Traversal) 後序走訪方式 (Postorder Traversal)

21 二元樹的走訪種類中序走訪 (Inorder Traversal) 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

22 小練習前序走訪 (Preorder Traversal) void print_preorder(node *ptr) { if(ptr!= NULL) { // 前序 : 5,4,2,1,3,6,8,7,9 } } 後序走訪 (Preorder Traversal) void print_postorder(node *ptr) { if(ptr!= NULL) { // 後序 : 1,3,2,4,7,9,8,6,5 } }

23 二元樹的搜尋利用二元樹走訪實作二元樹的搜尋 node *search_node(node *ptr, int value) { node *temp; } while(ptr!= NULL) { if(ptr->data == value) return ptr; else { temp = search_node(ptr->left, value); if(temp!= NULL) return temp; temp = search_node(ptr->right, value); if(temp!= NULL) return temp; } } return NULL; 8

24 大綱樹 (Tree) 二元樹 (Binary Tree) 二元搜尋樹 (Binary Search Tree) 課堂練習 2

25 二元搜尋樹二元搜尋樹 (Binary Search Trees) 是一種二元樹, 其節點資料的排列擁有一些特性, 如下所示 : 二元樹的每一個節點值都不相同, 在整棵二元樹中的每一個節點都擁有不同值每一個節點的資料大於左子節點的資料, 但是小於右子節點的資料節點的左右子樹也是一棵二元搜尋樹 2

26 二元搜尋樹 : 插入 node *insert_node(node *root, int value) { node *new_node; node *current; node *parent; } new_node = (node *)malloc(sizeof(node)); new_node->data = value; new_node->left = NULL; new_node->right = NULL; if(root == NULL) { return new_node; } else { current = root; while(current!= NULL) { parent = current; if(current->data > value) current = current->left; else current = current->left; } if(parent->data > value) parent->left = new_node; else parent->right = new_node; } return root;

27 二元搜尋樹 : 搜尋比較 : 一般二元樹的搜尋 ( *search_node() ) node *find_node(node *ptr, int value) { while(ptr!= NULL) { if(ptr->data == value) return ptr; else { if(ptr->data > value) ptr = ptr->left; else ptr = ptr->right; } } return NULL; }

28 二元搜尋樹 : 刪除必須先取得欲刪節點之父節點判斷此節點為父節點之左節點或右節點考量三種情況 : 情況 1: 節點沒有左子樹情況 2: 節點沒有右子樹情況 3: 節點有左右子樹

29 二元搜尋樹 : 刪除 root 10 root 30 情況 1: 節點沒有左子樹如果要刪的是根節點其他 root 10 root

30 二元搜尋樹 : 刪除 root 10 root 8 情況 2: 節點沒有右子樹如果要刪的是根節點其他 root 10 root

31 二元搜尋樹 : 刪除情況 3: 節點有左右子樹 ( 找取代點!) 如果要刪的節點之左子節點無右子樹 root 其他 10 root root root

32 二元搜尋樹 : 刪除找父節點並判斷該節點為父節點之左或右節點 node *find_parent(node *ptr, int value, int *pos) 3

33 二元搜尋樹 : 刪除刪除節點 node *delete_node(node *root, int value) 3

34 大綱樹 (Tree) 二元樹 (Binary Tree) 二元搜尋樹 (Binary Search Tree) 課堂練習 3

35 課堂練習使用二元搜尋樹製作一個通訊錄程式功能輸入 i 新增節點, 可輸入姓名, 電話, 依據姓名字母順序插入節點 ( 假設輸入之姓名不會重覆 ) 輸入 d 接著輸入姓名, 可將一筆資料節點中之姓名相同者刪除 ( 假設輸入之姓名不會重覆 ) 輸入 f 接著輸入一個姓名, 可將一筆資料節點中之姓名相同者印出資料輸入 l 依據姓名字母順序印出所有節點內容輸入 q 讀取離開程式輸入格式格式不拘 3

PowerPoint Presentation

PowerPoint Presentation 樹狀結構 (Tree) NTU CSIE 大綱樹 (Tree) 二元樹 (Binary Tree) 二元搜尋樹 (Binary Search Tree) 樹樹 (Tree) 是一種模擬現實生活中樹幹和樹枝的資料結構, 屬於一種階層架構的非線性資料結構, 例如 : 家族族譜, 決策模型樹的基本術語樹的樹根稱為根節點 (Root), 在根節點之下是樹的樹枝, 擁有 0 到 n 個子節點 (Children),