資料結構使用Java 樹(Tree)

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

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

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

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

樹的特徵

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

典型的樹狀結構

一般樹的特性

二元樹 Binary Tree

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

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

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

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

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

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

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

例如 : 讀取一維陣列值依序為 : 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[ ]

二元樹的追蹤 Binary TreeTraversals

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

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

二元樹的追蹤 前序(Pre-order) 中序(In-order) 後序(Post-order) 訪問根節點 訪問左子樹 訪問右子樹 上圖的走訪順序為：5 4 2 1 3 6 8 7 9 中序(In-order) 上圖的走訪順序為：1 2 3 4 5 6 7 8 9 後序(Post-order) 上圖的走訪順序為：1 3 2 4 7 9 8 6 5

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

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

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

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