擴充二叉樹的特點是什麼

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

二叉樹的使用範圍最廣，一棵多叉樹也可以轉化為二叉樹，因此我們將著重講解二叉樹。

二叉樹中還有連兩種特殊的二叉樹叫做滿二叉樹和完全二叉樹。如果二叉樹中每個內部結點都有兩個兒子，這樣的二叉樹叫做滿二叉樹。或者說滿二叉樹所有的葉結點都有同樣的深度。比如下面這棵二叉樹，是不是感覺很“豐滿”。滿二叉樹的嚴格的定義是一棵深度為h且有2h-1個結點的二叉樹。

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

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

說到這裡我們馬上就要領略到完全二叉樹的魅力了。先想一想一棵完全二叉樹如何儲存呢？其實完全二叉樹中父親和兒子之間有著神奇的規律，我們只需用一個一維陣列就可以儲存完全二叉樹。首先將完全二叉樹進行從上到下，從左到右編號。

透過上圖我們發現如果完全二叉樹的一個父結點編號為k，那麼它左兒子的編號就是2*k，右兒子的編號就是2*k+1。如果已知兒子（左兒子或右兒子）的編號是x，那麼它父結點的編號就是x/2，注意這裡只取商的整數部分。在C語言中如果除號‘/’兩邊都是整數的話，那麼商也只有整數部分（即自動向下取整），即4/2和5/2都是2。另外如果一棵完全二叉樹有N個結點，那麼這個完全二叉樹的高度為log［sub］2［/sub］ N簡寫為log N，即最多有log N層結點。完全二叉樹的最典型應用就是——堆。那麼堆又有什麼作用呢？請關注下週更新：堆——神奇的優先佇列。

歡迎轉載，碼字不容易啊，轉載麻煩註明出處

《啊哈！演算法》演算法10：二叉樹 http：//www。ahalei。com/thread-4850-1-1。html