資料結構與C++程式設計進階 樹狀結構(Tree) 講師：林業峻 CSIE, NTU 11/ 12, 2009

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

樹 「樹」（Tree） 用途：資料大量且常需要做搜索時 是一種模擬現實生活中樹幹和樹枝的資料結構，屬於一種階 層架構的非線性資料結構，例如：家族族譜, 決策模型 用途：資料大量且常需要做搜索時

樹的基本術語 樹的樹根稱為「根節點」（Root），在根節點之 下是樹的樹枝，擁有0到n個「子節點」（ Children），即樹的「分支」（Branch） 節點A是樹的根節點，B、C、D….和H是節點A的 子節點

樹的基本術語 在樹枝下還可以擁有下一層樹枝，I和J是B的子節 點，K、L和M是E的子節點，節點B是I和J的「父 節點」（Parent），節點E是K、L和M的父節點

樹的相關術語 n元樹：樹的一個節點最多擁有n個子節點。 二元樹（Binary Trees）：樹的節點最多只有兩個 子節點。 根節點（Root）：沒有父節點的節點是根節點。 例如：節點A。 葉節點（Leaf）：節點沒有子節點的節點稱為葉 節點。 例如：節點I、J、C、D、K、L、M、F、G和H。

樹的相關術語 分支度（Dregree）：指每個節點擁有的子節點數 例如：節點B的分支度是2，節點E的分支度是3。 階層（Level）：如果樹根是1，其子節點是2，依 序可以計算出樹的階層數。 例如：上述圖例的節點A階層是1，B、C到H是階層2，I、J到 M是階層3。 樹高（Height）： 樹高又稱為樹深（Depth） ，指樹的最大階層數。 例如：圖例的樹高是3。

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

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

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

二元樹鏈結表示法 二元樹節點鏈結表示法 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)

練習 試著建立一個二元樹如下圖所示 root 5 5 4 6 4 6 NULL NULL NULL NULL

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

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

二元樹的走訪種類 中序走訪（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

練習 前序走訪（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 }

二元樹的搜尋 利用二元樹走訪實作二元樹的搜尋 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

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

二元搜尋樹 「二元搜尋樹」（Binary Search Trees）是一種 二元樹，其節點資料的排列擁有一些特性，如下 所示： 二元樹的每一個節點值都不相同，在整棵二元樹中的每一個 節點都擁有不同值。 每一個節點的資料大於左子節點的資料，但是小於右子節點 的資料。 節點的左、右子樹也是一棵二元搜尋樹。 (BinarySearchTree.c)

二元搜尋樹: 插入 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

二元搜尋樹: 搜尋 利用資料的排列特性可以快速搜尋到資料 比較：一般二元樹的搜尋 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

二元搜尋樹: 刪除 必須先取得欲刪節點之父節點 判斷此節點為父節點之左節點或右節點 考量三種情況： (程式碼詳見範例程式) 情況1: 節點沒有左子樹 情況2: 節點沒有右子樹 情況3: 節點有左右子樹 (程式碼詳見範例程式) 10 5 20 1 8 15 30

二元搜尋樹: 刪除 情況1: 節點沒有左子樹 (1)如果要刪的是根節點 (2)要刪除的節點在父節點右方 (3)要刪除的節點在父節點左方 root root 10 30 30 25 35 25 35

二元搜尋樹: 刪除 情況1: 節點沒有左子樹 (1)如果要刪的是根節點 (2)要刪除的節點在父節點右方 (3)要刪除的節點在父節點左方 root root 10 10 20 30 30 25 35 25 35

二元搜尋樹: 刪除 情況1: 節點沒有左子樹 (1)如果要刪的是根節點 (2)要刪除的節點在父節點右方 (3)要刪除的節點在父節點左方 root root 50 50 20 30 30 25 35 25 35

二元搜尋樹: 刪除 情況2: 節點沒有右子樹 (1)如果要刪的是根節點 (2)要刪除的節點在父節點右方 (3)要刪除的節點在父節點左方 root 10 root 5 5 2 7 2 7

二元搜尋樹: 刪除 情況2: 節點沒有右子樹 (1)如果要刪的是根節點 (2)要刪除的節點在父節點右方 (3)要刪除的節點在父節點左方 root 1 root 1 8 5 5 2 7 2 7

二元搜尋樹: 刪除 情況2: 節點沒有右子樹 (1)如果要刪的是根節點 (2)要刪除的節點在父節點右方 (3)要刪除的節點在父節點左方 root 10 root 8 10 5 5 2 7 2 7

二元搜尋樹: 刪除 情況3: 節點有左右子樹 往左子節點之右子樹找最大值當取代點 root root 10 8 5 20 5 20 8 15 30 7 15 30 7

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