506.9.2决定唯一的二元树.ppt

第 6 章 樹狀結構 目次 6.1 樹狀結構的專有名詞 6.2 二元樹 6.3 二元樹的表示方法 6.4 二元樹追蹤 6.5 引線二元樹 6.6 二元搜尋樹 6.7 堆積 6.8 集合的表示法 6.9 其它論題 6.1 樹狀結構的專有名詞 樹的表示法 6.1 樹狀結構的專有名詞 (con.t) 樹狀結構的專有名詞 節點(node)與邊(edge) 祖先(ancestor)節點與子孫(descendant)節點 父節點(parent node)與子節點(children node) 兄弟節點(sibling node) 非終點節點 終點節點(terminal node)或樹葉節點(leaf node) 6.1 樹狀結構的專有名詞 (con.t) 樹狀結構的專有名詞 分支度(degree) 階度(level) 高度(height) 深度(depth) 樹林(forest) 6.2 二元樹 為何使用二元樹？ 為了減少儲存空間的浪費 二元樹 二元樹是由節點所組成的有限集合，這個集合若不是空集合；就是由樹根、右子樹(right subtree)及左子樹(left subtree)所組合而成。 其中右子樹和左子樹可以是空集合。 6.2 二元樹 (con.t) 二元樹與一般樹的不同處 二元樹的節點個數可以為零 二元樹的節點有排列順序的關係 二元樹中每一節點的分支度至多為 2 二元樹的種類 左/右斜樹(left/right skewed tree)：圖(a) 滿枝二元樹(fully binary tree) ：圖(b) 完整二元樹(complete binary tree) ：圖(c) 6.2 二元樹 (con.t) 6.2 二元樹 (con.t) 二元樹的特徵 二元樹在第 i 階度的最多節點數為 2i-1，i≧1 階度(或深度)為k的二元樹，最多的節點數為2k-1，k≧1 二元樹，若n0表示所有的樹葉節點，n2表示所有分支度為 2 的節點，則n0=n2+1 Ex：圖6.3 6.3 二元樹的表示方法 如何將二元樹的節點儲存在一維陣列？ 下圖為圖(c)儲存在一維陣列的表示法 若運用在非完整二元樹或滿枝二元樹時，可能會造成許多空間的浪費 → 使用鏈結串列 6.3 二元樹的表示方法(con.t) 鏈結串列方式 每個節點包含三個欄位： 左鏈結(left link)、資料(data)、右鏈結(right link) 二元樹的資料結構 6.4 二元樹追蹤 二元樹的追蹤(traversal) 中序追蹤(inorder)：左子樹 → 樹根 → 右子樹 前序追蹤(preorder)：樹根 → 左子樹 → 右子樹 後序追蹤(postorder)：左子樹 → 右子樹 → 樹根 6.4 二元樹追蹤(con.t) 中序追蹤(inorder)：左子樹 → 樹根 → 右子樹 void inorder(Node type *tree) { if (tree != NULL){ inorder(tree-llink); printf(%d, tree-data); inorder(tree-rlink); } } 6.4 二元樹追蹤(con.t) 前序追蹤(preorder)：樹根→左子樹→ 右子樹 void preorder(Node type *tree) { if (tree != NULL){ printf(%d, tree-data); preorder(tree-llink); preorder(tree-rlink); } } 6.4 二元樹追蹤(con.t) 後序追蹤(postorder)：左子樹→右子樹→樹根 void postorder(Node type *tree) { if (tree != NULL){ postorder(tree-llink); postorder(tree-rlink); printf(%d, tree-data); } } 6.5 引線二元樹 為何使用引線二元樹？ 為了便利儲存及節省LINK欄位的浪費，而有二元樹的產生。但二元樹中仍然會造成n+1個LINK欄位的浪費(n為節點數目)，因此將空的LINK欄位換成引線(thread)的指標。 引線二元樹 二元樹中的LINK欄位以引線的指標取代，而引線是指到二元樹的其它節點 引線二元樹的有一個「開頭節點(head node) 」，並且不存放任何資料。 6.5 引線二元樹(con.t) 二元樹 → 引線二元樹 先將二元樹的資料以中序追蹤方式排列