
樹狀演算法
樹狀結構是一種日常生活中應用相當廣泛的非線性結構,樹狀演算法在程式中建立與應用大多使用鏈結串列來處理,因為鏈結串列的指標用來處理樹是相當方便,只需改變指標即可。此外,當然也可以使用陣列這樣的連續記憶體來表示二元樹,至於使用陣列或鏈結串列都各有利弊,本章將分別為各位介紹常見的相關演算法。

由於二元樹的應用相當廣泛,所以衍生了許多特殊的二元樹結構。我們首先為您介紹如下:
完滿二元樹(Full Binary Tree)

H=4 高度
2^4-1=2*2*2*2-1=15 節點數
完整二元樹(Complete BinaryTree)
如果二元樹的深度為h,所含的節點數小於2^h-1,但其節點的編號方式如同深度為h的完滿二元樹一般,從左到右,由上到下的順序一一對應結合。如下圖:

對於完整二元樹而言,假設有N個節點,那麼此二元樹的階層(Level)為[log^2(N+1)]。
歪斜樹(Skewes Binary Tree)
當一個二元樹完全沒有右節點或左節點時,我們就把它稱為左歪斜樹或右歪斜樹。

嚴格二元樹(strictly binary tree)
