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

?

? ? 二叉樹的使用范圍最廣，一棵多叉樹也可以轉(zhuǎn)化為二叉樹，因此我們將著重講解二叉樹。

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

?

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

???

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

?

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

?

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

? ??歡迎轉(zhuǎn)載，碼字不容易啊，轉(zhuǎn)載麻煩注明出處

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

本文轉(zhuǎn)自 ? ?風(fēng)雨蕭條 博客，原文鏈接： ?http://blog.51cto.com/1095221645/1417939 ? ? ?如需轉(zhuǎn)載請(qǐng)自行聯(lián)系原作者

總結(jié)

以上是生活随笔為你收集整理的【坐在马桶上看算法】算法10：二叉树的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。