1. 二叉樹(shù)（Binary Tree)的定義
1.1 什么是二叉樹(shù)（Binary Tree)
每個(gè)結(jié)點(diǎn)至多擁有兩棵子樹(shù)的樹(shù)結(jié)構(gòu)(即二叉樹(shù)中不存在度大于2的結(jié)點(diǎn))胧卤。并且惦蚊，二叉樹(shù)的子樹(shù)有左右之分将硝，其次序不能任意顛倒塔淤。
上面概念中提到了“度”的概念干旧，“度”其實(shí)就是某個(gè)節(jié)點(diǎn)子節(jié)點(diǎn)的數(shù)量。如果某個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)數(shù)量為1涕俗，則該節(jié)點(diǎn)的度為1罗丰，如果有8個(gè)子節(jié)點(diǎn)，則度為8再姑，以此類推萌抵。
1.2 二叉樹(shù)的術(shù)語(yǔ)
除了二叉樹(shù)的定義外，還有許多相關(guān)的術(shù)語(yǔ)元镀。單純介紹術(shù)語(yǔ)可能不容易理解绍填，這里給出一幅圖進(jìn)行說(shuō)明。
下面是對(duì)二叉樹(shù)中主要術(shù)語(yǔ)的解釋：
結(jié)點(diǎn)的度（Degree）：結(jié)點(diǎn)的子樹(shù)個(gè)數(shù)栖疑；
樹(shù)的度：樹(shù)的所有結(jié)點(diǎn)中最大的度數(shù)讨永；
葉結(jié)點(diǎn)（Leaf）：度為0的結(jié)點(diǎn)；
父結(jié)點(diǎn)（Parent）：有子樹(shù)的結(jié)點(diǎn)是其子樹(shù)的根節(jié)點(diǎn)的父結(jié)點(diǎn)遇革；
子結(jié)點(diǎn)/孩子結(jié)點(diǎn)（Child）：若A結(jié)點(diǎn)是B結(jié)點(diǎn)的父結(jié)點(diǎn)卿闹，則稱B結(jié)點(diǎn)是A結(jié)點(diǎn)的子結(jié)點(diǎn)；
兄弟結(jié)點(diǎn)（Sibling）：具有同一個(gè)父結(jié)點(diǎn)的各結(jié)點(diǎn)彼此是兄弟結(jié)點(diǎn)萝快；
路徑和路徑長(zhǎng)度：從結(jié)點(diǎn)n1到nk的路徑為一個(gè)結(jié)點(diǎn)序列n1锻霎，n2，...杠巡，nk量窘。ni是ni+1的父結(jié)點(diǎn)雇寇。路徑所包含邊的個(gè)數(shù)為路徑的長(zhǎng)度氢拥；
祖先結(jié)點(diǎn)（Ancestor）：沿樹(shù)根到某一結(jié)點(diǎn)路徑上的所有結(jié)點(diǎn)都是這個(gè)結(jié)點(diǎn)的祖先結(jié)點(diǎn)；
子孫結(jié)點(diǎn)（Descendant）：某一結(jié)點(diǎn)的子樹(shù)中的所有結(jié)點(diǎn)是這個(gè)結(jié)點(diǎn)的子孫锨侯；
結(jié)點(diǎn)的層次（Level）：規(guī)定根結(jié)點(diǎn)在1層嫩海，其他任一結(jié)點(diǎn)的層數(shù)是其父結(jié)點(diǎn)的層數(shù)加1；
樹(shù)的深度（Depth）：樹(shù)中所有結(jié)點(diǎn)中的最大層次是這棵樹(shù)的深度囚痴；
1.3 二叉樹(shù)的性質(zhì)
我們?cè)O(shè)定二叉樹(shù)的根節(jié)點(diǎn)為為第1層叁怪，則二叉樹(shù)有如下性質(zhì)。這些性質(zhì)可以通過(guò)數(shù)學(xué)方式進(jìn)行證明深滚，但本文暫時(shí)不做證明奕谭，大家了解即可，對(duì)于理解后續(xù)概念有一些幫助：
性質(zhì)1：二叉樹(shù)第i層上最多有 2^（i-1） 個(gè)結(jié)點(diǎn)(i≥1)痴荐；
性質(zhì)2：深度（高度）為k的二叉樹(shù)至多有2^(k)-1個(gè)結(jié)點(diǎn)(k≥1血柳，深度k也就是樹(shù)的最大層級(jí))；
性質(zhì)3：包含n個(gè)結(jié)點(diǎn)的二叉樹(shù)的深度（高度）至少為log2 (n+1)生兆；
性質(zhì)4：在任意一棵二叉樹(shù)中难捌，如果其葉子結(jié)點(diǎn)(度為0)數(shù)為m, 度為2的結(jié)點(diǎn)數(shù)為n, 則m = n + 1。
1.4 二叉樹(shù)的數(shù)據(jù)存儲(chǔ)
二叉樹(shù)在C語(yǔ)言中可以通過(guò)結(jié)構(gòu)體表示，其定義的方式可以是如下：
struct bitree_node {
int b_data; //數(shù)據(jù)域根吁，指向具體的數(shù)據(jù)
struct bitree_node *left; //指向左子節(jié)點(diǎn)
struct bitree_node *right; //指向右子節(jié)點(diǎn)
};
在這個(gè)實(shí)例中员淫，為了簡(jiǎn)單，我們假設(shè)其存儲(chǔ)的數(shù)據(jù)類型為整型數(shù)击敌，當(dāng)然最好的方式是void指針的形式介返。這樣，二叉樹(shù)就是一個(gè)通用的數(shù)據(jù)結(jié)構(gòu)沃斤，可以存儲(chǔ)任何類型的數(shù)據(jù)映皆。
2. 二叉樹(shù)的特例
根據(jù)二叉樹(shù)存儲(chǔ)數(shù)據(jù)組織結(jié)構(gòu)的差異，二叉樹(shù)有很多特例轰枝。比如有些二叉樹(shù)所有節(jié)點(diǎn)只有左子節(jié)點(diǎn)捅彻，或者非葉子節(jié)點(diǎn)的每個(gè)二叉樹(shù)的節(jié)點(diǎn)都有2個(gè)子節(jié)點(diǎn)等等。下面我們分別進(jìn)行介紹鞍陨。
2.1 斜二叉樹(shù)
只有左子節(jié)點(diǎn)或只有右子節(jié)點(diǎn)的二叉樹(shù)稱為斜二叉樹(shù)步淹。
2.2 完美二叉樹(shù)
一個(gè)深度為k(>=-1)且有2^(k+1) - 1個(gè)結(jié)點(diǎn)的二叉樹(shù)稱為完美二叉樹(shù)。完美二叉樹(shù)也就是滿二叉樹(shù)诚撵，也就是所有非葉子節(jié)點(diǎn)都有2個(gè)葉子節(jié)點(diǎn)缭裆，并且每一次都是滿的。如圖所示：
2.3 完全二叉樹(shù)(Complete)
完全二叉樹(shù)從根結(jié)點(diǎn)到倒數(shù)第二層滿足完美二叉樹(shù)寿烟，最后一層可以不完全填充澈驼，其葉子結(jié)點(diǎn)都靠左對(duì)齊。
下圖就不是一棵完全(Complete)二叉樹(shù)
3. 二叉樹(shù)相關(guān)的算法（面試題）
在面試和筆試的過(guò)程中筛武，二叉樹(shù)的題目是非常多的缝其。除了常見(jiàn)的關(guān)于二叉樹(shù)遍歷的題目外，還有其它一些延伸的題目徘六。本文今天先將二叉樹(shù)相關(guān)的題目羅列到這里内边，后續(xù)會(huì)給出每個(gè)題目的解題思路和代碼示例。
