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

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

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

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

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

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" />

其實(shí)完全二叉樹(shù)類似下面這個(gè)形狀。

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

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

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

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

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