資料結構使用Java 樹(Tree).

Presentation on theme: "資料結構使用Java 樹(Tree)."— Presentation transcript:

1 資料結構使用Java 樹(Tree)

2 課程內容 樹(Tree)的特色與特性。 一般樹的基本結構與定義。 二元樹的定義與種類 二元樹儲存於陣列中的格式 二元樹程式碼撰寫 二元樹追蹤

3 樹的基本結構與特性 陣列、鏈結串列、堆疊與佇列都屬於線性的 (linear)資料結構。
有些應用的資料展現的並不是這種線性的結構， 需要用到像樹(tree)或圖型(graph)這一類非線性 的(nonlinear)資料結構。

4 一般樹的基本結構 大自然中的樹(tree)是一種有起源和分支的結構， 由樹根、樹葉與枝幹所組成。

5 一般樹(general tree)的基本定義
樹是一種由節點(node)連結而成的有限集合。 至少具有一個稱為樹根(root)的節點，因此一般 的樹不會是空集合。 具有下列兩個性質的圖形（graph） 相連結(connected)： 節點之間至少必須有一個以上的連結。 非迴圈性(circuit-free)： 點與點之間不能形成無出口的迴圈。

6 樹的特徵

7 樹的基本定義 樹為非線性之資料結構，資料與資料之間藉由分 支(Branch)組成階層式(Hierarchical)之關係。
樹狀結構為一個或多個節點所構成之有限集合， 並具有以下之特性： 有一個特定節點稱為樹根 (Root) 其餘節點為分成n個獨立之集合T1,T2,…Tn 其中各個集合為一樹狀結構 T1,T2,…,Tn稱為樹根(Root)之子樹(Sub-tree)

8 典型的樹狀結構

9 一般樹的特性

10 二元樹 Binary Tree

11 二元樹(Binary Tree) 是一個由有限個節點所組成的集合 可能是空集合，或者是由一個樹根及兩個互斥的 二元樹稱為左子樹和右子樹所構成
又稱為Knuth樹，每個節點的分支度≦2 左邊的節點稱為左子樹(Left Child) 右邊的節點稱為右子樹(Right Child) 因其左右有次序之分，故又稱為有序樹(Ordered Tree)。

12 節點結構 每個節點的結構如下： 優點：插入與刪除一個節點相當容易。 缺點：很難找到該節點的父點(Parent)。
其中DATA欄存放節點值。 left欄存放其左子樹的節點物件 right欄存放其右子樹的節點物件。 優點：插入與刪除一個節點相當容易。 缺點：很難找到該節點的父點(Parent)。 LCHILD DATA RCHILD

13

14 二元樹種類 歪斜樹(Skewed Binary Tree)： 當一個二元樹的所有節點都只有左子點(Left Child)或只有右子點時稱之。
完滿二元樹(Full Binary Tree)： 一個二元樹含有的節點數最多時稱之，若階度 (level)為k且含有2k-1個節點。

15 二元樹種類 完整二元樹(Complete Binary Tree)： 一個二元樹的階度(level)為k，而其所含節點數少 於2k-1個，但其節點的編號順序如同完滿二元樹 一般時稱之。 嚴格二元樹(Strictly Binary Tree)： 若二元樹的每一個非終端節點均有非空的左右子 樹時稱之。

16 二元樹儲存於陣列中的格式 btree[ ] A B C D E F G

17 普通二元樹程式撰寫 節點由陣列後面往前串(避免存取錯誤) 父節點階層編號 : level 左節點是父節點編號乘以2 右節點是父節點編號乘以2
level = level * 2 ; 右節點是父節點編號乘以2 level = level * 2 + 1;

18 創建二元樹步驟 建立二元樹 函數createBTree()讀取一維陣列的元素來建立二元樹。 將陣列元素值與二元樹的節點做比較
如果元素值大於節點值，將元素值插入為右子節點，如果 右子節點不是空的，重複比較節點值，直到找到可插入位 置。 如果元素值小於節點值，將元素值插入為左子節點，如果 左子節點不是空的，重複比較節點值，直到找到可插入位 置。

19 例如 : 讀取一維陣列值依序為 : 5 6 4 8 2 3 7 1 9，依據上 述規則建立二元樹。 樹根 1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 btree[ ]

20 二元樹的追蹤 Binary TreeTraversals

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

22 二元樹的追蹤 前序(Pre-order) 中序(In-order) 後序(Post-order) 訪問根節點 訪問左子樹 訪問右子樹
上圖的走訪順序為：ABDECFG 中序(In-order) 上圖的走訪順序為：DBEAFCG 後序(Post-order) 上圖的走訪順序為：DEBFGCA

23 二元樹的追蹤 前序(Pre-order) 中序(In-order) 後序(Post-order) 訪問根節點 訪問左子樹 訪問右子樹
上圖的走訪順序為： 中序(In-order) 上圖的走訪順序為： 後序(Post-order) 上圖的走訪順序為：

24 二元樹走訪程式流程 中序走訪方式 Step1 : Step2 : 檢查是否可以繼續前進，指標不可大於陣列的最大值
如果可以前進，其處理方式如下 (1) 遞迴呼叫 inOrder(i*2) 向左走 (2) 顯示目前節點資料 (3) 遞迴呼叫 inOrder(i*2+1) 向右走

25 二元樹走訪程式流程 前序走訪方式 Step1 : Step2 : 檢查是否可以繼續前進，指標不可大於陣列的最大值
如果可以前進，其處理方式如下 (1) 顯示目前節點資料 (2) 遞迴呼叫 inOrder(i*2) 向左走 (3) 遞迴呼叫 inOrder(i*2+1) 向右走

26 二元樹走訪程式流程 後序走訪方式 Step1 : Step2 : 檢查是否可以繼續前進，指標不可大於陣列的最大值
如果可以前進，其處理方式如下 (1) 遞迴呼叫 inOrder(i*2) 向左走 (2) 遞迴呼叫 inOrder(i*2+1) 向右走 (3) 顯示目前節點資料

27 前序式走訪(遞迴演算法) 若樹根節點不為空節點，則執行下列步驟： １.走訪樹根 ２.走訪左子樹(遞迴) ３.走訪右子樹(遞迴)
若樹根節點不為空節點，則執行下列步驟： １.走訪樹根 ２.走訪左子樹(遞迴) ３.走訪右子樹(遞迴) public void preOrder(){ if(i<MAX_NODE){ if(btree[i]!=0) System.out.print(btree[i]); preorder(i*2); preorder(i*2+1); }