二叉樹是一種特殊的樹。二叉樹的特點是每個結(jié)點最多有兩個兒子，左邊的叫做左兒子，右邊的叫做右兒子，或者說每個結(jié)點最多有兩棵子樹。更加嚴(yán)格的遞歸定義是：二叉樹要么為空，要么由根結(jié)點、左子樹和右子樹組成，而左子樹和右子樹分別是一棵二叉樹。 下面這棵樹就是一棵二叉樹。

http://wiki.jikexueyuan.com/project/easy-learn-algorithm/images/10.1.png" alt="picture10.1" />

二叉樹的使用范圍最廣，一棵多叉樹也可以轉(zhuǎn)化為二叉樹，因此我們將著重講解二叉樹。 二叉樹中還有連兩種特殊的二叉樹叫做滿二叉樹和完全二叉樹。如果二叉樹中每個內(nèi)部結(jié)點都有兩個兒子，這樣的二叉樹叫做滿二叉樹。或者說滿二叉樹所有的葉結(jié)點都有同樣的深度。比如下面這棵二叉樹，是不是感覺很“豐滿”。滿二叉樹的嚴(yán)格的定義是一棵深度為 h 且有 2h-1 個結(jié)點的二叉樹。

http://wiki.jikexueyuan.com/project/easy-learn-algorithm/images/10.2.png" alt="picture10.2" />

如果一棵二叉樹除了最右邊位置上一個或者幾個葉結(jié)點缺少外其它是豐滿的，那么這樣的二叉樹就是完全二叉樹。嚴(yán)格的定義是：若設(shè)二叉樹的高度為 h，除第 h 層外，其它各層 (1～h-1) 的結(jié)點數(shù)都達(dá)到最大個數(shù)，第 h 層從右向左連續(xù)缺若干結(jié)點，就是完全二叉樹。也就是說如果一個結(jié)點有右子結(jié)點，那么它一定也有左子結(jié)點。例如下面這三棵樹都是完全二叉樹。其實你可以將滿二叉樹理解成是一種特殊的或者極其完美的完全二叉樹。

http://wiki.jikexueyuan.com/project/easy-learn-algorithm/images/10.3.png" alt="picture10.3" /> http://wiki.jikexueyuan.com/project/easy-learn-algorithm/images/10.4.png" alt="picture10.4" /> http://wiki.jikexueyuan.com/project/easy-learn-algorithm/images/10.5.png" alt="picture10.5" />

其實完全二叉樹類似下面這個形狀。

http://wiki.jikexueyuan.com/project/easy-learn-algorithm/images/10.6.jpg" alt="picture10.6" />

說到這里我們馬上就要領(lǐng)略到完全二叉樹的魅力了。先想一想一棵完全二叉樹如何存儲呢？其實完全二叉樹中父親和兒子之間有著神奇的規(guī)律，我們只需用一個一維數(shù)組就可以存儲完全二叉樹。首先將完全二叉樹進(jìn)行從上到下，從左到右編號。

http://wiki.jikexueyuan.com/project/easy-learn-algorithm/images/10.7.jpg" alt="picture10.7" />

通過上圖我們發(fā)現(xiàn)如果完全二叉樹的一個父結(jié)點編號為 k，那么它左兒子的編號就是 2k，右兒子的編號就是 2k+1。如果已知兒子（左兒子或右兒子）的編號是 x，那么它父結(jié)點的編號就是 x/2，注意這里只取商的整數(shù)部分。在 C 語言中如果除號‘/’兩邊都是整數(shù)的話，那么商也只有整數(shù)部分（即自動向下取整），即 4/2 和 5/2 都是 2。另外如果一棵完全二叉樹有 N 個結(jié)點，那么這個完全二叉樹的高度為 log2 N 簡寫為 log N，即最多有 log N 層結(jié)點。完全二叉樹的最典型應(yīng)用就是——堆。那么堆又有什么作用呢？請關(guān)注下周更新：堆——神奇的優(yōu)先隊列。

【啊哈！算法】算法 10：二叉樹
http://ahalei.blog.51cto.com/4767671/1414035