第10章 二元搜尋樹 (Binary Search Tree)

Presentation on theme: "第10章 二元搜尋樹 (Binary Search Tree)"— Presentation transcript:

1 第10章 二元搜尋樹 (Binary Search Tree)
資料結構使用Java 第10章 二元搜尋樹 (Binary Search Tree)

2 課程內容 二元樹追蹤 前序追蹤 中序追蹤 後序追蹤 二元搜尋樹 建立二元搜尋樹的方法 程式碼撰寫實作 刪除二元搜尋樹

3 二元樹的追蹤 二元樹追蹤(binary tree traversal)是樹最重要的 基本運算。 追蹤時保存著3項重要的資訊： 節點資料
指向左子樹的鏈結 指向右子樹的鏈結。

4 二元樹的追蹤 前序(Preorder)： 中序(Inorder) ： 後序(Postorder)： 樹根→左子樹→右子樹(DLR)
左子樹→樹根→右子樹(LDR) 後序(Postorder)： 左子樹→右子樹→樹根(LRD)

5 前序追蹤(Preorder traversal)
追蹤順序： 節點資料 拜訪左子樹 拜訪右子樹

6 【範例一】 試寫出下圖之前序追蹤順序。 B C E F I D G J H A L K

7 前序追蹤 (遞迴演算法) 若樹根節點不為空節點，則執行下列步驟： １.走訪樹根 ２.走訪左子樹(遞迴) ３.走訪右子樹(遞迴) 下載原程式碼
若樹根節點不為空節點，則執行下列步驟： １.走訪樹根 ２.走訪左子樹(遞迴) ３.走訪右子樹(遞迴) 下載原程式碼 public void preOrder(){ System.out.print(data+" "); if(left!=null) left.preOrder(); if(right!=null) right.preOrder(); }

8 中序追蹤(Inorder traversal)
追蹤順序： 拜訪左子樹 節點資料 拜訪右子樹

9 【範例二】 試寫出下圖之中序追蹤順序。 B C E F I D G J H A L K

10 中序追蹤 (遞迴演算法) 若樹根節點不為空節點，則執行下列步驟： １.走訪左子樹(遞迴) ２.走訪樹根 ３.走訪右子樹(遞迴)
若樹根節點不為空節點，則執行下列步驟： １.走訪左子樹(遞迴) ２.走訪樹根 ３.走訪右子樹(遞迴) public void inOrder(){ if(left!=null) left.preOrder(); System.out.print(data+" "); if(right!=null) right.preOrder(); }

11 後序追蹤(Postorder traversal)
追蹤順序： 拜訪左子樹 拜訪右子樹 節點資料

12 【範例三】 試寫出下圖之後序追蹤順序。 B C E F I D G J H A L K

13 後序追蹤 (遞迴演算法) 若樹根節點不為空節點，則執行下列步驟： １.走訪左子樹(遞迴) ２.走訪右子樹(遞迴) ３.走訪樹根
若樹根節點不為空節點，則執行下列步驟： １.走訪左子樹(遞迴) ２.走訪右子樹(遞迴) ３.走訪樹根 public void postOrder(){ if(left!=null) left.preOrder(); if(right!=null) right.preOrder(); System.out.print(data+" "); }

14 二元搜尋樹 Binary Search Tree

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

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

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

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

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

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

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