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

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

1 資料結構使用Java 第9章 樹(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 節點程式碼 其節點類別可定義如下： 可使用建構元傳入資料，進行節點初始化 class treeNode{ int data;
treeNode left, right; public treeNode(int value){ data = value; left = right = null; }

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

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

17 普通二元樹程式撰寫 利用節點陣列儲存使用者輸入的資料。 node[0] node[1] node[2] node[3] node[4]
10 left right 59 left right 36 left right 8 left right 24 left right 77 left right

18 普通二元樹程式撰寫 將節點陣列按照順序串成二元樹 node[0] 10 node[2] node[1] 59 36 null node[3]
8 null 24 null 77 null

19 普通二元樹程式撰寫 節點由陣列後面往前串(避免存取錯誤) 若陣列索引值為偶數n 若陣列索引值為奇數n 代表為右節點
node[i/2-1].right = node[i]; 若陣列索引值為奇數n 代表為左節點 其父節點索引值為：(n/2) node[i/2].left = node[i];

20 二元樹的追蹤 Binary TreeTraversals

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

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