資料結構 - 二元樹 ( Binary tree )

二元搜尋樹 Binary search tree 又叫做有序二元樹，

二元搜尋樹的特性為：

• 任何節點的左子樹不為空，則其左子樹的所有值均比其樹根小
• 任何節點的右子樹不為空，則其右子樹的所有值均比其樹根大
• 任意節點的左右子樹均為二元搜尋樹

底下就是一個二元搜尋樹(圖片取自維基百科)

二元樹有幾個特殊名詞：

滿二元樹 ( Full binary tree )：特性為每一層的節點都有最大節點數，假設樹高為 n ，節點數量必為 2 的 n 次方 -1

完全二元樹 ( Complete Binary Tree )：假設樹高為 n ， n-1 層擁有最大節點數量，第 n 層節點從缺少的節點開始到該層結束都為空

葉節點 ( Leaf ) ： 沒有子節點的節點稱為葉節點

根節點 ( Root )： 沒有父節點的節點稱為根節點

二元樹的走訪 (Traversal) 可分為：

前序 ( Preorder ) ：

走訪依據根節點、左子節點、右子節點，根節點在前，

以上圖為範例，前序走訪為：

[ 8, 3, 1, 6, 4, 7, 10, 14, 13 ]

中序 ( Inorder )：

走訪依據左子節點、根節點、右子節點，根節點在中間，

以中序走訪的數列會由小到大的排序，

以上圖為範例，中序走訪為：

[ 1, 3, 4, 6, 7, 8, 10, 13, 14 ]

後序 ( Postorder )

走訪依據左子節點、右子節點、根節點，根節點在後，

以上圖為範例，後序走訪為：

[ 1, 4, 7, 6, 3, 13, 14, 10, 8 ]

層序 ( Level-order )

走訪依據層數由左至右，

以上圖為範例，層序走訪為：

[ 8, 3, 10, 1, 6, 14, 4, 7, 13 ]