資料結構 老師：李崇明 助教：楊斯竣.

Presentation on theme: "資料結構 老師：李崇明 助教：楊斯竣."— Presentation transcript:

1 資料結構 老師：李崇明 助教：楊斯竣

2 課程內容 6-1 樹的基本觀念 6-2 二元樹的基礎 6-3 二元樹的表示法 6-4 二元樹的走訪 6-5 二元搜尋樹
6-6 樹的二元樹表示法 6-7 二元樹的應用 - 運算式處理

3 6-1 樹的基本觀念-說明 「樹」（Trees）是一種模擬現實生活中樹幹和樹枝的資料結構，屬於一種階層架構的非線性資料結構，例如：家族族譜，如下圖所示：

4 6-1 樹的基本觀念-架構1 樹的樹根稱為「根節點」（Root），在根節點之下是樹的樹枝，擁有0到n個「子節點」（Children），即樹的「分支」（Branch），節點A是樹的根節點，B、C、D….和H是節點A的子節點，即樹枝，如下圖所示：

5 6-1 樹的基本觀念-架構2 在樹枝下還可以擁有下一層樹枝，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 6-1 樹的基本觀念-定義 定義 7.1：樹的節點個數是一或多個有限集合，且：
(1) 存在一個節點稱為根節點。 (2) 在根節點下的節點分成n >= 0 個沒有交集的多個子集合t1、t2…, tn，每一個子集合也是一棵樹，而這些樹稱為根節點的「子樹」（Subtree）。 樹在各節點之間不可以有迴圈，或不連結的左、右子樹，如下圖所示：

7 6-1 樹的基本觀念-相關術語1 n元樹：樹的一個節點最多擁有n個子節點。 二元樹（Binary Trees）：樹的節點最多只有兩個子節點。
根節點（Root）：沒有父節點的節點是根節點。例如：節點A。 葉節點（Leaf）：節點沒有子節點的節點稱為葉節點。例如：節點I、J、C、D、K、L、M、F、G和H。 祖先節點（Ancenstors）：指某節點到根節點之間所經過的所有節點，都是此節點的祖先節點。

8 6-1 樹的基本觀念-相關術語2 非終端節點（Noterminal 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。

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

10 6-2 二元樹的基礎-圖例 二元樹 左子樹 右子樹

11 6-2 二元樹的基礎-歪斜樹 左邊這棵樹沒有右子樹，右邊這棵樹沒有左子樹，雖然擁有相同節點，但是這是兩棵不同的二元樹，因為所有節點都是向左子樹或右子樹歪斜，稱為「歪斜樹」（Skewed Tree），如下圖所示：

12 6-2 二元樹的基礎- 完滿二元樹(說明) 若二元樹的樹高是h且二元樹的節點數是2h-1，滿足此條件的樹稱為「完滿二元樹」（Full Binary Tree），如下圖所示：

13 6-2 二元樹的基礎- 完滿二元樹(節點數) 因為二元樹的每一個節點有2個子節點，二元樹樹高是3，也就是有3個階層（Level），各階層的節點數，如下所示： 第1階：1 = 2 (1-1) = 20 = 1 第2階：第1階節點數的2倍，1*2 = 2 (2-1) = 2 第3階：第2階節點數的2倍，2*2 = 2 (3-1) = 4 以此類推，可以得到每一階層的最大節點數是：2 (l-1)，l是階層數，整棵二元樹的節點數一共是： = 7個，即23-1，可以得到： ….+2 (h-1) = 2h-1，h是樹高

14 6-2 二元樹的基礎-完整二元樹 若二元樹的節點不是葉節點，一定擁有兩個子節點，不過節點總數不足2h-1，其中h是樹高，滿足此條件的二元樹稱為「完整二元樹」（Complete Binary Tree），如下圖所示：

15 6-3 二元樹的表示法 6-3-1 二元樹陣列表示法 6-3-2 二元樹物件陣列表示法 6-3-3 二元樹鏈結表示法

16 6-3 二元樹的表示法 二元樹在實作上有多種方法可以建立二元樹，常用的方法有三種，如下所示： 二元樹陣列表示法。 二元樹物件陣列表示法。
二元樹鏈結表示法。

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

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

19 6-3-1 二元樹陣列表示法-二元樹類別 class BTree_Array { // 二元樹類別
private int[] btree; // 二元樹陣列宣告 // 建構子: 建立二元樹 public BTree_Array(int size, int[] array) { … … } // 方法: 顯示二元樹 public void printBTree() { …… } }

20 6-3-1 二元樹陣列表示法-成員方法

21 6-3-1 二元樹陣列表示法-建立二元樹(規則)
BTree_Array()建構子以參數size的尺寸建立一維陣列儲存節點資料後，其建立規則，如下： 將第1個陣列元素插入成為二元樹的根節點。 將陣列元素值與二元樹的節點值比較，如果元素值大於節點值，將元素值插入成為節點的右子節點，如果右子節點不是空的，重覆比較節點值，直到找到插入位置後，將元素值插入二元樹。 如果元素值小於節點值，將元素值插入成為節點的左子節點，如果左子節點不是空的，繼續重覆比較，以便將元素值插入二元樹。

22 6-3-1 二元樹陣列表示法-建立二元樹(圖例)
二元樹陣列表示法圖例的索引值0並沒有使用，整個二元樹在16個陣列元素中使用的元素一共有9個，括號內是陣列的索引值，如下圖所示：

23 6-3-1 二元樹陣列表示法-顯示二元樹 printBTree()方法：顯示二元樹
printBTree()方法只是走訪btree[]陣列，將元素值不是-1的元素都顯示出來。

24 程式

25 6-3-1 二元樹陣列表示法-問題 一棵歪斜樹的二元樹陣列表示法使用不到三分之一的陣列元素4/16，因為二元樹的節點是以循序方式儲存在陣列中，如果需要插入或刪除節點，都需要在陣列中搬移大量元素，如下圖所示：

26 6-3-2二元樹物件陣列表示法-說明 在二元樹的每一個節點可以使用Java語言的節點物件來儲存，整棵二元樹是一個一維的物件陣列，data是節點資料，使用left和right成員變數的索引值指向子節點的索引值，如為-1表示沒有子節點，如下圖所示：

27 6-3-2二元樹物件陣列表示法-節點與二元樹類別
class Node { // 樹節點類別 int data; // 節點資料 int left; // 參考左子樹 int right; // 參考右子樹 } class BTree_Node { // 二元樹類別 private Node[] btree; // 二元樹陣列宣告 // 建構子: 建立二元樹 public BTree_Node(int size, int[] data) { …… } // 方法: 顯示二元樹 public void printBTree() { …… }

28 6-3-2二元樹物件陣列表示法-圖例 例如：一棵二元樹和其物件陣列表示法，如下圖所示：

29 6-3-3 二元樹鏈結表示法-說明 二元樹鏈結表示法是使用動態記憶體配置來建立二元樹，類似結構陣列表示法的節點結構，只是成員變數改成兩個指向左和右子樹的指標，如下圖所示：

30 6-3-3 二元樹鏈結表示法-TreeNode類別
鏈結串列實作的節點與二元樹類別：TreeNode和BTree class TreeNode { // 樹節點類別 int data; // 節點資料 TreeNode left; // 參考左子樹 TreeNode right; // 參考右子樹 // 建構子 public TreeNode(int data) { …… } }

31 6-3-3 二元樹鏈結表示法-BTree類別 public class BTree { // 二元樹類別
public TreeNode head; // 參考樹的根節點 // 建構子: 使用陣列建立二元樹 public BTree(int[] array) { …… } // 方法: 檢查二元樹是否是空的 boolean isBTreeEmpty() { …… } // 方法: 在二元樹插入節點 public void insertBTreeNode(int data) { …… } // 方法: 顯示二元樹的節點資料 public void printBTree() { …… } }

32 6-3-3 二元樹鏈結表示法-成員方法

33 6-3-3 二元樹鏈結表示法-建立二元樹(說明)
BTree()建構子和insertBTreeNode()方法：建立二元樹 BTree()建構子只是使用for迴圈走訪參數的陣列元素，依序呼叫insertBTreeNode()方法將一個一個陣列元素的節點插入二元樹。 首先是二元樹的根節點5，left和right指標指向null，在建立二元樹的根節點5後，第二次呼叫insertBTreeNode()方法插入元素6，在比較二元樹根節點值5後，結果比較大，所以鏈結至右子樹。第三次呼叫插入元素4，經比較插入成為根節點的左子樹。等到執行完建構子的for迴圈後，建立的二元樹。

34 6-3-3 二元樹鏈結表示法-建立二元樹(圖例)

35 6-3-3 二元樹鏈結表示法-顯示二元樹 printBTree()方法：顯示二元樹
printBTree()方法使用while迴圈分別走訪二元樹的左右分支，不過這個方法並沒有辦法顯示二元樹的全部節點資料。

36 程式

37 6-4 二元樹的走訪 6-4-1 中序走訪方式 6-4-2 前序走訪方式 6-4-3 後序走訪方式

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

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

40 6-4-1 中序走訪方式-說明 中序走訪是沿著二元樹的左方往下走，直到無法繼續前進後，顯示節點，退回到父節點顯示父節點，然後繼續往右走，如果右方都無法前進，顯示節點，再退回到上一層。依照中序走訪第6-4節的二元樹，其顯示的節點順序，如下所示： 1,2,3,4,5,6,7,8,9 在上述中序走訪節點順序中，可以看出根節點5是位在正中間，之前都是左子樹的節點，之後都是右子樹的節點。

41

42 6-4-1 中序走訪方式-演算法 中序走訪的遞迴方法inOrder()使用二元樹指標ptr進行走訪，中序走訪的步驟，如下所示：
Step 1：檢查是否可以繼續前進，即指標ptr不等於null。 Step 2：如果可以前進，其處理方式如下所示： (1) 遞迴呼叫inOrder(ptr.left)向左走。 (2) 處理目前的節點，顯示節點資料。 (3) 遞迴呼叫inOrder(ptr.right)向右走。

43 程式

44 6-4-1 中序走訪方式-遞迴呼叫

45 6-4-2 前序走訪方式-說明 前序走訪方式是走訪到的二元樹節點，就立刻顯示節點資料，走訪的順序是先向樹的左方走直到無法前進後，才轉往右方走。依照前序走訪第6-4節的二元樹，其顯示的節點順序，如下所示： 5,4,2,1,3,6,8,7,9 在上述前序走訪節點順序中，可以看出根節點5一定是第1個，左右子樹的根節點一定在其它節點之前。

46 6-4-2 前序走訪方式-演算法 前序走訪的遞迴方法preOrder()使用二元樹指標ptr進行走訪，前序走訪的步驟，如下所示：
Step 1：先檢查是否已經到達葉節點，也就是指標ptr等於null。 Step 2：如果不是葉節點表示可以繼續走，其處理方式如下所示： (1) 處理目前的節點，顯示節點資料。 (2) 遞迴呼叫preOrder(ptr.left)向左走。 (3) 遞迴呼叫preOrder(ptr.right)向右走。

47 6-4-2 前序走訪方式-遞迴呼叫

48 程式

49 6-4-3 後序走訪方式-說明 後序走訪方式剛好和前序走訪相反，它是等到節點的2個子節點都走訪過後才執行處理，顯示節點資料。依照後序走訪第6-4節的二元樹，其顯示的節點順序，如下所示： 1,3,2,4,7,9,8,6,5 在上述後序走訪節點順序中，可以看出根節點5是最後1個，而且左右子樹的根節點一定在其它節點之後。

50 6-4-3 後序走訪方式-演算法 後序走訪的遞迴方法postOrder()使用二元樹指標ptr進行走訪，後序走訪的步驟，如下所示：
Step 1：先檢查是否已經到達葉節點，就是指標ptr等於null。 Step 2：如果不是葉節點表示可以繼續走，其處理方式如下所示： (1) 遞迴呼叫postOrder(ptr.left)向左走。 (2) 遞迴呼叫postOrder(ptr.right)向右走。 (3) 處理目前的節點，顯示節點資料。

51 6-4-3 後序走訪方式-遞迴呼叫

52 程式

53 Binary Search Tree 二元搜尋樹

54 二元搜尋樹(Binary Search Tree)
為一種「有大小順序」的二元樹。 任何節點 左子樹之值小於節點的值 右子樹之值大於節點的值 左子樹和右子樹亦是二元搜尋樹。 將二元搜尋樹中序追蹤，即可得到排序後由小至大的資料。 50 30 72 42 95

55 建立二元搜尋樹 建立二元搜尋樹時，必須加入大小排序規則： 以第一個資料當作樹根 之後之資料與樹根比較 若小於樹根則成為樹根之左子樹
若大於樹根則成為樹根之右子樹 如此一直遞迴之進行。

56 建立二元搜尋樹 輸入資料： 37, 57, 23, 15, 32。

57 建立二元搜尋樹-程式碼 使用者輸入的第一個數字成為樹根節點(root)。 建立insert方法來新增節點。
treeNode root = new treeNode(sc.nextInt()); 建立insert方法來新增節點。 呼叫insert時傳入新節點(newNode)參數。 root.insert(new treeNode(sc.nextInt())); insert方法判斷目前節點與新節點的data大小 新節點data較小：新增到左子樹。 新節點data較大：新增到右子樹。 若左、右子樹為空，則直接將新節點掛上。

58 建立二元搜尋樹-程式碼 if(newNode.data < data){ //新節點data較小 if(left == null) //左子樹為空 left = newNode; else left.insert(newNode); //新增到左子樹 }else{ if(right == null) right = newNode; right.insert(newNode); }

59 刪除二元搜尋樹節點 若是樹葉節點：直接刪除 若是內部節點： 例：刪除右圖50 在左子樹找數值最大的節點取代之
或是在右子樹找數值最小的節點取代之 例：刪除右圖50 50 40 65 45 30 60

60 刪除二元搜尋樹節點 60 40 65 45 30 取右子樹最小的節點 或是取左子樹最大的節點 45 40 65 60 30