Jul 11, 2020
資料結構 - 二元樹 ( Binary tree )
資料結構 – 二元樹 ( Binary tree )
二元搜尋樹 Binary search tree 又叫做有序二元樹， 二元搜尋樹的特性為：
任何節點的左子樹不為空，則其左子樹的所有值均比其樹根小
任何節點的右子樹不為空，則其右子樹的所有值均比其樹根大
任意節點的左右子樹均為二元搜尋樹
底下就是一個二元搜尋樹(圖片取自維基百科)
二元樹有幾個特殊名詞： 滿二元樹 ( Full binary tree )：特性為每一層的節點都有最大節點數，假設樹高為 n ，節點數量必為 2 的 n 次方 -1 完全二元樹 ( Complete Binary Tree )：假設樹高為 n ， n-1 層擁有最大節點數量，第 n 層節點從缺少的節點開始到該層結束都為空 葉節點 ( Leaf ) ： 沒有子節點的節點稱為葉節點 根節點 ( Root )： 沒有父節點的節點稱為根節點
二元樹的走訪 (Traversal) 可分為： 前序 (…
View On WordPress