資料結構 – 二元樹 ( Binary 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 ]