1.1 什麼是二叉樹（Binary Tree)

每個結點至多擁有兩棵子樹的樹結構(即二叉樹中不存在度大于2的結點)。并且，二叉樹的子樹有左右之分，其次序不能任意颠倒。

上面概念中提到了“度”的概念，“度”其實就是某個節點子節點的數量。如果某個節點的子節點數量為1，則該節點的度為1，如果有8個子節點，則度為8，以此類推。

1.2 二叉樹的術語

除了二叉樹的定義外，還有許多相關的術語。單純介紹術語可能不容易理解，這裡給出一幅圖進行說明。

圖1 二叉樹的主要概念

下面是對二叉樹中主要術語的解釋：

結點的度（Degree）：結點的子樹個數；

樹的度：樹的所有結點中最大的度數；

葉結點（Leaf）：度為0的結點；

父結點（Parent）：有子樹的結點是其子樹的根節點的父結點；

子結點/孩子結點（Child）：若A結點是B結點的父結點，則稱B結點是A結點的子結點；

兄弟結點（Sibling）：具有同一個父結點的各結點彼此是兄弟結點；

路徑和路徑長度：從結點n1到nk的路徑為一個結點序列n1，n2，...，nk。ni是ni 1的父結點。路徑所包含邊的個數為路徑的長度；

祖先結點（Ancestor）：沿樹根到某一結點路徑上的所有結點都是這個結點的祖先結點；

子孫結點（Descendant）：某一結點的子樹中的所有結點是這個結點的子孫；

結點的層次（Level）：規定根結點在1層，其他任一結點的層數是其父結點的層數加1；

樹的深度（Depth）：樹中所有結點中的最大層次是這棵樹的深度；

1.3 二叉樹的性質

我們設定二叉樹的根節點為為第1層，則二叉樹有如下性質。這些性質可以通過數學方式進行證明，但本文暫時不做證明，大家了解即可，對于理解後續概念有一些幫助：

性質1：二叉樹第i層上最多有 2^（i-1） 個結點(i≥1)；

性質2：深度（高度）為k的二叉樹至多有2^(k)-1個結點(k≥1，深度k也就是樹的最大層級)；

性質3：包含n個結點的二叉樹的深度（高度）至少為log2 (n 1)；

性質4：在任意一棵二叉樹中，如果其葉子結點(度為0)數為m, 度為2的結點數為n, 則m = n 1。

1.4 二叉樹的數據存儲

二叉樹在C語言中可以通過結構體表示，其定義的方式可以是如下：

struct bitree_node { int b_data; //數據域，指向具體的數據 struct bitree_node *left; //指向左子節點 struct bitree_node *right; //指向右子節點 };

在這個實例中，為了簡單，我們假設其存儲的數據類型為整型數，當然最好的方式是void指針的形式。這樣，二叉樹就是一個通用的數據結構，可以存儲任何類型的數據。

圖2 二叉樹的數據存儲

2. 二叉樹的特例

根據二叉樹存儲數據組織結構的差異，二叉樹有很多特例。比如有些二叉樹所有節點隻有左子節點，或者非葉子節點的每個二叉樹的節點都有2個子節點等等。下面我們分别進行介紹。

2.1 斜二叉樹

隻有左子節點或隻有右子節點的二叉樹稱為斜二叉樹。

圖3 斜二叉樹

2.2 完美二叉樹

一個深度為k(>=-1)且有2^(k 1) - 1個結點的二叉樹稱為完美二叉樹。完美二叉樹也就是滿二叉樹，也就是所有非葉子節點都有2個葉子節點，并且每一次都是滿的。如圖所示：

圖4 完美二叉樹

2.3 完全二叉樹(Complete)

完全二叉樹從根結點到倒數第二層滿足完美二叉樹，最後一層可以不完全填充，其葉子結點都靠左對齊。

下圖就不是一棵完全(Complete)二叉樹

圖5 完全二叉樹

3. 二叉樹相關的算法（面試題）

在面試和筆試的過程中，二叉樹的題目是非常多的。除了常見的關于二叉樹遍曆的題目外，還有其它一些延伸的題目。本文今天先将二叉樹相關的題目羅列到這裡，後續會給出每個題目的解題思路和代碼示例。

3.1 二叉樹的前序遍曆

3.2 二叉樹的中序遍曆

3.3 二叉樹的後序遍曆

3.4 二叉樹層序遍曆

3.5 求二叉樹的高度

3.6 求二叉樹節點個數

3.7 求二叉樹第k層的節點個數

3.8 求二叉樹中葉子節點的個數

3.9 判斷兩棵二叉樹是否相同的樹

3.10 判斷二叉樹是不是平衡二叉樹

3.11 求二叉樹的鏡像

3. 12 判斷兩個二叉樹是否互相鏡像

3.13 求二叉樹中兩個節點的最低公共祖先節點

3.14 判斷是否為二分查找樹BST

3.15 二叉搜索樹中第K小的元素

3.16 填充每個節點的下一個右側節點指針(完美二叉樹)

3.17 填充每個節點的下一個右側節點指針（普通二叉樹）

3.18 表達式轉二叉樹

3.19 表達式求值

,