PowerPoint Presentation

Size: px

Start display at page:

Download "PowerPoint Presentation"

禅川家
5 years ago
Views:

1 樹狀結構 (Tree) NTU CSIE

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 的父節點節點 I 和 J 擁有共同父節點, 稱為兄弟節點 (Siblings), K L 和 M 是兄弟節點,B C 和 H 節點也是兄弟節點

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

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

8 大綱樹 (Tree) 二元樹 (Binary Tree) 二元搜尋樹 (Binary Search Tree)

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

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

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

12 二元樹 : 完滿二元樹因為二元樹的每一個節點有 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 是樹高

13 二元樹 : 完整二元樹若二元樹的節點總數不足 2 h -1, 其中 h 是樹高, 除最後一層外全填滿, 最後一層節點全靠左, 而且其節點編號是對應相同高度完滿二元樹的節點編號, 因為編號完整, 中間沒有空號, 因此稱為完整二元樹 (Complete Binary Tree) 0 資料 1 2 資料資料 3 4 資料資料

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

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

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

17 二元樹鏈結表示法 struct binary_tree_node { 資料型態變數名稱 ; int data; struct binary_tree_node *left; struct binary_tree_node *right; ; typedef struct binary_tree_node node; node *root; root = (node *)malloc(sizeof(node)); root ->data= 10; root ->left= NULL; root ->right= NULL; left node * root node data 10 NULL NULL (malloc) right

18 小練習 (Binarry_Tree.c) 試著建立一個二元樹如下圖所示 5 5 root node *root; 4 6 // Level 1 root = (node *)malloc(sizeof(node)); root->data = 5; root->left = NULL; root->right = NULL; 4 6 NULL NULL NULL NULL // Level 2 root->left = (node *)malloc(sizeof(node)); root->left->data = 4; root->left->right = NULL; root->left->left = NULL; root->right = (node *)malloc(sizeof(node)); root->right->data = 6; root->right->left = NULL; root->right->right = 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) 每節點皆會比它的左子節點及右子節點先印左子節點又比右子節點先印 ( 自已 -> 左 -> 右 ) 5,4,2,1,3,6,8,7,9 後序走訪 (Postorder Traversal) 印自己前先印左節點再印右節點自己最後 ( 左 -> 右 -> 自已 ) 1,3,2,4,7,9,8,6,5

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

24 二元樹的搜尋 (Tree_LinearSearch.c) 利用二元樹走訪實作二元樹的搜尋 node *search_node(node *ptr, int value) { node *temp; if(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

25 大綱樹 (Tree) 二元樹 (Binary Tree) 二元搜尋樹 (Binary Search Tree)

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

27 二元搜尋樹 : 插入 node *insert_node(node *root, int value) { node *new_node; node *current; node *parent; node * root, *ptr; char key; int value; root = NULL; 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->right; if(parent->data > value) parent->left = new_node; else parent->right = new_node; return root; scanf("%d",&value); ptr = root; root=insert_node(root, value); printf("insert ok\n");

28 小練習 (BinarySearchTree.c) 請實作上述之二元搜尋樹的插入演算法並製做一選單讓使用者輸入 i 新增節點可輸入數字並依據數值大小順序插入節點 ( 假設輸入之數字不會重覆 ) 並試著建構出如上頁圖中的二元樹 Hint: 輸入的次序很重要, 為什麼? 輸入 l 可選擇列印順序印出所有節點內容各以前 / 中 / 後序列印出來

29 二元搜尋樹 : 搜尋比較 : 一般二元樹的搜尋 ( 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; scanf("%d",&value); ptr = find_node(root, value); if(ptr!= NULL) printf("found: %d\n", ptr->data); else printf("not found\n");

30 二元搜尋樹 : 刪除必須先取得欲刪節點之父節點判斷此節點為父節點之左節點或右節點考量三種情況 : 情況 1: 節點沒有左子樹情況 2: 節點沒有右子樹情況 3: 節點有左右子樹 ( 程式碼詳見範例程式 ) scanf("%d",&value); ptr = find_node(root, value); if(ptr!= NULL) root= delete_node(root, value); printf("delete ok\n"); else printf("can not delete\n");

31 二元搜尋樹 : 刪除情況 1: 節點沒有左子樹如果要刪的是根節點要刪除的節點在父節點右方要刪除的節點在父節點左方 parrent -> ptr -> root 10 root = root->right; free(ptr); root

32 二元搜尋樹 : 刪除情況 1: 節點沒有左子樹如果要刪的是根節點要刪除的節點在父節點右方要刪除的節點在父節點左方 parrent -> root 10 parent->right = ptr->right; free(ptr); root 10 ptr ->

33 二元搜尋樹 : 刪除情況 1: 節點沒有左子樹如果要刪的是根節點其他要刪除的節點在父節點右方要刪除的節點在父節點左方 parrent -> root 50 parent->left = ptr->right; free(ptr); root 50 ptr ->

34 二元搜尋樹 : 刪除情況 2: 節點沒有右子樹如果要刪的是根節點其他 parrent -> ptr -> 10 root 5 root = root->left; free(ptr); root

35 二元搜尋樹 : 刪除情況 2: 節點沒有右子樹如果要刪的是根節點其他要刪除的節點在父節點右方要刪除的節點在父節點左方 parrent -> root 1 parent->right = ptr->left; free(ptr); root 1 ptr ->

36 二元搜尋樹 : 刪除情況 2: 節點沒有右子樹如果要刪的是根節點其他要刪除的節點在父節點右方要刪除的節點在父節點左方 parrent -> root 10 parent->left = ptr->left; free(ptr); root 10 ptr ->

37 二元搜尋樹 : 刪除情況 3: 節點有左右子樹往左子節點之右子樹找最大值當取代點 next-> parent-> ptr-> root parent = ptr; next = ptr->left;// 找取代點 next, 從左邊開始找 if(next->right!= NULL) { while(next->right!= NULL) { // 往左子節點之右子樹找最大值當取代點 parent = next; //parent 為 next 父節點 next = next->right; // 繞過 next 節點 parent->right = next->left; else { ptr->left = NULL; ptr->data = next->data; // 取代!! free(next); // 刪除 next ( 注意 : 不是刪除 ptr) root

38 二元搜尋樹 : 刪除情況 3: 節點有左右子樹往左子節點之右子樹找最大值當取代點 8 parent = ptr; next = ptr->left;// 找取代點 next, 從左邊開始找 if(next->right!= NULL) { while(next->right!= NULL) { // 往左子節點之右子樹找最大值當取代點 parent = next; //parent 為 next 父節點 next = next->right; // 繞過 next 節點 parent->right = next->left; else { ptr->left = NULL; ptr->data = next->data; // 取代!! free(next); // 刪除 next ( 注意 : 不是刪除 ptr) 5 ptr-> 20 root 8 7 next->

39 小練習 (BinarySearchTree.c) 完成實做以上介紹之二元搜尋樹功能 : 輸入 i 新增節點, 可輸入數字, 依據數值大小順序插入節點 ( 假設輸入之數字不會重覆 ) 輸入 d 接著輸入數字, 可將一筆資料節點中之數字相同者刪除 ( 假設輸入之數字不會重覆 ) 輸入 f 接著輸入一個數字, 可將一筆資料節點中之數字相同者印出資料輸入 l 依據數字順序印出所有節點內容輸入 q 讀取離開程式

40 回家作業 (Addressbook_Tree.c) 使用二元搜尋樹製作一個電話簿功能 : 輸入 i 新增節點, 可輸入姓名, 電話, 依據姓名字母順序插入節點 ( 假設輸入之姓名不會重覆 ) 輸入 d 接著輸入姓名, 可將一筆資料節點中之姓名相同者刪除 ( 假設輸入之姓名不會重覆 ) 輸入 f 接著輸入一個姓名, 可將一筆資料節點中之姓名相同者印出資料輸入 l 依據姓名字母順序印出所有節點內容輸入 q 讀取離開程式

Tree

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