# 二叉樹 二叉樹是一種具有層級特性的數據結構，每個節點最多有兩個子樹的樹結構。通常子樹被稱作“左子樹”（left subtree）和“右子樹”（right subtree）。 :-:  ## 二叉樹的基本形態 二叉樹是遞歸定義的，其結點有左右子樹之分，邏輯上二叉樹有五種基本形態： :-:  (1)空二叉樹——如圖(a)； (2)只有一個根結點的二叉樹——如圖(b)； (3)只有左子樹——如圖(c)； (4)只有右子樹——如圖(d)； (5)完全二叉樹——如圖(e)。 ## 滿二叉樹 一棵深度為 k，且有 2^(k-1) 個節點的二叉樹，稱為滿二叉樹。這種樹的特點是每一層上的節點數都是最大節點數。而在一棵二叉樹中，除最后一層外，若其余層都是滿的，并且最后一層或者是滿的，或者是在右邊缺少連續若干節點，則此二叉樹為完全二叉樹。具有n個節點的完全二叉樹的深度為 log2n+1。深度為k的完全二叉樹，至少有 2^(k-1) 個節點，至多有 2^(k-1) 個節點。 :-:  普通二叉樹擴充為完全二叉樹 :-:  ## 順序二叉樹 * 任意節點的左子樹不空，則左子樹上所有結點的值均小于它的根結點的值； * 任意節點的右子樹不空，則右子樹上所有結點的值均大于它的根結點的值； * 任意節點的左、右子樹也分別為二叉查找樹； 一顆排序二叉樹長這樣: :-:  # 參考資料 http://blog.csdn.net/laokdidiao/article/details/51860741