內(nèi)容整理于魚c工作室教程

1. 樹的基本概念

1.1 樹的定義

樹(Tree)是n(n>=0)個結(jié)點的有限集。

當(dāng)n=0時成為空樹，在任意一棵非空樹中：有且僅有一個特定的稱為根(Root)的結(jié)點；

當(dāng)n>1時，其余結(jié)點可分為m(m>0)個互不相交的有限集T1、T2、…、Tm，其中每一個集合本身又是一棵樹，并且稱為根的子樹(SubTree)。

雖然從概念上很容易理解樹，但是有兩點還是需要大家注意下：

n>0時，根結(jié)點是唯一的，堅決不可能存在多個根結(jié)點。

m>0時，子樹的個數(shù)是沒有限制的，但它們互相是一定不會相交的。

1.2 樹的基本概念

(1) 結(jié)點：如上圖，每一個圈圈我們就稱為樹的一個結(jié)點。

(2) 度: 結(jié)點擁有的子樹數(shù)稱為結(jié)點的度-(Degree)，樹的度取樹內(nèi)各結(jié)點的度的最大值。

(3) 葉結(jié)點(Leaf)或終端結(jié)點: 度為0的結(jié)點。

(4) 內(nèi)部結(jié)點: 度不為0的結(jié)點稱為分支結(jié)點或非終端結(jié)點，除根結(jié)點外，分支結(jié)點也稱為內(nèi)部結(jié)點。

(5) 結(jié)點間的關(guān)系：結(jié)點的子樹的根稱為結(jié)點的孩子(Child)，相應(yīng)的，該結(jié)點稱為孩子的雙親(Parent)，同一雙親的孩子之間互稱為兄弟(Sibling)。結(jié)點的祖先是從根到該結(jié)點所經(jīng)分支上的所有結(jié)點。

(6) 深度：樹中結(jié)點的最大層次稱為樹的深度(Depth)或高度。

(7) 結(jié)點的層次(Level): 從根開始定一起，根為第一層，根的孩子為第二層。其雙親在同一層的結(jié)點互為堂兄弟。

(8) 有序樹: 如果將樹中結(jié)點的各子樹看成從左至右是有次序的，不能互換的，則稱該樹為有序樹, 否則為無序樹。

(9) 森林(Forest):?是 m(m>=0)棵互不相交的樹的集合。對樹中每個結(jié)點而言，其子樹的集合即為森林。

2. 樹的存儲結(jié)構(gòu)

2.1 雙親表示法

雙親表示法，言外之意就是以雙親作為索引的關(guān)鍵詞的一種存儲方式。

我們假設(shè)以一組連續(xù)空間存儲樹的結(jié)點，同時在每個結(jié)點中，附設(shè)一個指示其雙親結(jié)點在數(shù)組中位置的元素。

也就是說，每個結(jié)點除了知道自己是誰之外，還知道它的粑粑媽媽在哪里。

這樣的存儲結(jié)構(gòu)，我們可以根據(jù)某結(jié)點的parent指針找到它的雙親結(jié)點，所用的時間復(fù)雜度是O(1)，索引到parent的值為-1時，表示找到了樹結(jié)點的根。

可是，如果我們要知道某結(jié)點的孩子是什么？那么不好意思，請遍歷整個樹結(jié)構(gòu)。

當(dāng)然可以，我們只需要稍微改變一下結(jié)構(gòu)即可：

那現(xiàn)在我們又比較關(guān)心它們兄弟之間的關(guān)系呢？

2.2 孩子表示法

我們這次換個角度來考慮，由于樹中每個結(jié)點可能有多棵子樹，可以考慮用多重鏈表來實現(xiàn)。

就像我們雖然有計劃生育，但我們還是無法確保每個家庭只養(yǎng)育一個孩子的沖動，那么對于子樹的不確定性也是如此。

方法1: 根據(jù)樹的度，聲明足夠空間存放子樹指針的結(jié)點。

缺點十分明顯，就是造成了浪費！

方法2:

這樣我們就克服了浪費這個概念，我們從此走上了節(jié)儉的社會主義道路！但每個結(jié)點的度的值不同，初始化和維護起來難度巨大吧？

方法3:最佳解決方案。

那只找到孩子找不到雙親貌似還不夠完善，那么我們合并上一講的雙親孩子表示法：

3. 樹的種類

3.1 二叉樹

二叉樹（Binary Tree）是n（n>=0）個結(jié)點的有限集合，該集合或者為空集（空二叉樹），或者由一個根結(jié)點和兩棵互不相交的、分別稱為根結(jié)點的左子樹和右子樹的二叉樹組成。

3.1.1 二叉樹的特點

(1) 每個結(jié)點最多有兩棵子樹，所以二叉樹中不存在度大于2的結(jié)點。（注意：不是都需要兩棵子樹，而是最多可以是兩棵，沒有子樹或者有一棵子樹也都是可以的。）

(2) 左子樹和右子樹是有順序的，次序不能顛倒。

(3) 即使樹中某結(jié)點只有一棵子樹，也要區(qū)分它是左子樹還是右子樹，下面是完全不同的二叉樹：

3.1.2 二叉樹的基本形態(tài)

從左到右，依次是(1) 空二叉樹, (2)只有一個根結(jié)點, (3)根結(jié)點只有左子樹, (4)根結(jié)點只有右子樹

(5)根結(jié)點既有左子樹又有右子樹。

3.1.3 特殊二叉樹

(1) 斜樹

顧名思義，斜樹是一定要斜的，但斜也要斜得有范兒，例如：

(2) 滿二叉樹

坡坡有云：“人有悲歡離合，月有陰晴圓缺，此事古難全。但愿人長久，千里共長娟。”意思就是說完美的那是理想，不完美的才是人生。

但是對于二叉樹來說，是否存在完美呢？有滴，那就是滿二叉樹啦。

在一棵二叉樹中，如果所有分支結(jié)點都存在左子樹和右子樹，并且所有葉子都在同一層上，這樣的二叉樹稱為滿二叉樹。

葉子只能出現(xiàn)在最下一層。

非葉子結(jié)點的度一定是2。

在同樣深度的二叉樹中，滿二叉樹的結(jié)點個數(shù)一定最多，同時葉子也是最多。

(3) 完全二叉樹

對一棵具有n個結(jié)點的二叉樹按層序編號，如果編號為i(1<=i<=n)的結(jié)點與同樣深度的滿二叉樹中編號為i的結(jié)點位置完全相同，則這棵二叉樹稱為完全二叉樹。

葉子結(jié)點只能出現(xiàn)在最下兩層。

最下層的葉子一定集中在左部連續(xù)位置。

倒數(shù)第二層，若有葉子結(jié)點，一定都在右部連續(xù)位置。

如果結(jié)點度為1，則該結(jié)點只有左孩子。

同樣結(jié)點樹的二叉樹，完全二叉樹的深度最小。

注意：滿二叉樹一定是完全二叉樹，但完全二叉樹不一定是滿二叉樹。

3.1.4 二叉樹性質(zhì)

(1) 在二叉樹的第i層上至多有2^(i-1)個結(jié)點(i>=1)。

(2) 深度為k的二叉樹至多有2^k-1個結(jié)點(k>=1)。

(3) 對任何一棵二叉樹T，如果其終端結(jié)點數(shù)為n0，度為2的結(jié)點數(shù)為n2，則n0=n2+1。

首先我們再假設(shè)度為1的結(jié)點數(shù)為n1，則二叉樹T的結(jié)點總數(shù)n=n0+n1+n2

其次我們發(fā)現(xiàn)連接數(shù)總是等于總結(jié)點數(shù)n-1，并且等于n1+2*n2

所以n-1=n1+2*n2

所以n0+n1+n2-1=n1+n2+n2

最后n0=n2+1

(4) 具有n個結(jié)點的完全二叉樹的深度為?log?n?+1。

由滿二叉樹的定義結(jié)合性質(zhì)二我們知道，深度為k的滿二叉樹的結(jié)點樹n一定是2^k-1

那么對于滿二叉樹我們可以通過n=2^k-1倒推得到滿二叉樹的深度為k=log?(n+1)

由于完全二叉樹前邊我們已經(jīng)提到，它的葉子結(jié)點只會出現(xiàn)在最下面的兩層，我們可以同樣如下推導(dǎo)

那么對于倒數(shù)第二層的滿二叉樹我們同樣很容易回推出它的結(jié)點數(shù)為n=2^(k-1)-1

所以完全二叉樹的結(jié)點數(shù)的取值范圍是：2^(k-1)-1 < n <= 2^k-1

由于n是整數(shù)，n <= 2^k-1可以看成n < 2^k

同理2^(k-1)-1 < n可以看成2^(k-1) <= n

所以2^(k-1) <= n < 2^k

不等式兩邊同時取對數(shù)，得到k-1<=log?n

由于k是深度，必須取整，所以k=?log?n?+1

(5) 如果對一棵有n個結(jié)點的完全二叉樹(其深度為?log?n?+1)的結(jié)點按層序編號，對任一結(jié)點i(1<=i<=n)有以下性質(zhì)：

如果i = 1，則結(jié)點 i 是二叉樹的根，無雙親；如果i > 1，則其雙親是結(jié)點?i/2?

如果2i > n，則結(jié)點 i 無做左孩子(結(jié)點 i 為葉子結(jié)點)；否則其左孩子是結(jié)點2i

如果2i+1 > n，則結(jié)點 i 無右孩子；否則其右孩子是結(jié)點2i+1

3.1.4 二叉樹的存儲

在前邊的演示中，我們發(fā)覺很難單單只用順序存儲結(jié)構(gòu)或者鏈?zhǔn)酱鎯Y(jié)構(gòu)來存放。

但是二叉樹是一種特殊的樹，由于它的特殊性，使得用順序存儲結(jié)構(gòu)或鏈?zhǔn)酱鎯Y(jié)構(gòu)都能夠簡單實現(xiàn)。

(1) 順序存儲結(jié)構(gòu)

二叉樹的順序存儲結(jié)構(gòu)就是用一維數(shù)組存儲二叉樹中的各個結(jié)點，并且結(jié)點的存儲位置能體現(xiàn)結(jié)點之間的邏輯關(guān)系。

這下看出完全二叉樹的優(yōu)越性來了吧？由于他的嚴(yán)格定義，在數(shù)組直接能表現(xiàn)出邏輯結(jié)構(gòu)。

當(dāng)然對于一般的二叉樹，盡管層序編號不能反映邏輯關(guān)系，但是也可以按照完全二叉樹編號方式修改一下，把不存在的結(jié)點用“^”代替即可。

但是考慮到一種極端的情況，回顧一下斜樹，如果是一個又斜樹，那么會變成什么樣？

(2) 鏈?zhǔn)酱鎯Y(jié)構(gòu)

既然順序存儲方式的適用性不強，那么我們就要考慮鏈?zhǔn)酱鎯Y(jié)構(gòu)啦。二叉樹的存儲按照國際慣例來說一般也是采用鏈?zhǔn)酱鎯Y(jié)構(gòu)的。

二叉樹每個結(jié)點最多有兩個孩子，所以為它設(shè)計一個數(shù)據(jù)域和兩個指針域是比較自然的想法，我們稱這樣的鏈表叫做二叉鏈表。

3.1.5 二叉樹的遍歷

二叉樹的遍歷(traversing binary tree)是指從根結(jié)點出發(fā)，按照某種次序依次訪問二叉樹中所有結(jié)點，使得每個結(jié)點被訪問一次且僅被訪問一次。

二叉樹的遍歷方式可以很多，如果我們限制了從左到右的習(xí)慣方式，那么主要就分為一下四種：

(1) 前序遍歷

若二叉樹為空，則空操作返回，否則先訪問根結(jié)點，然后前序遍歷左子樹，再前序遍歷右子樹。

遍歷的順序為：ABDHIEJCFKG

(2) 中序遍歷

若樹為空，則空操作返回，否則從根結(jié)點開始（注意并不是先訪問根結(jié)點），中序遍歷根結(jié)點的左子樹，然后是訪問根結(jié)點，最后中序遍歷右子樹。

遍歷的順序為：HDIBEJAFKCG

注意！是先F再K,因為是先遍歷結(jié)點的左子樹然后結(jié)點然后右子樹。因為沒有左子樹，所以直接結(jié)點再右子樹。

(3) 后序遍歷

若樹為空，則空操作返回，否則從左到右先葉子后結(jié)點的方式遍歷訪問左右子樹，最后訪問根結(jié)點。

遍歷的順序為：HIDJEBKFGCA

(4) 層序遍歷

若樹為空，則空操作返回，否則從樹的第一層，也就是根結(jié)點開始訪問，從上而下逐層遍歷，在同一層中，按從左到右的順序?qū)Y(jié)點逐個訪問。

遍歷的順序為：ABCDEFGHIJK

3.2 線索二叉樹

我想正如程序猿發(fā)覺單鏈表并不總能滿足他們設(shè)計的程序某些要求的時候，發(fā)明了雙向鏈表來彌補一樣，線索二叉樹也是在需求中被創(chuàng)造的！那普通的二叉樹到底有什么缺陷讓我們發(fā)指呢？

10個！

沒錯，中序遍歷可以拯救地球！

上圖經(jīng)過中序遍歷后結(jié)果是：HDIBEAFCG

我們發(fā)現(xiàn)紅色的結(jié)點都是剛才“^”造成浪費的結(jié)點，利用中序遍歷剛好它們均處于字符中間，可以很好地利用“^”來存放前驅(qū)和后繼的指針。不過好事總是多磨的，我們是有主觀意識所以可以很容易出來哪些結(jié)點可以利用存放前驅(qū)后繼。這所謂的主觀意識還不簡單，不就是從第一個開始每隔一個結(jié)點都可以？

上圖經(jīng)過中序遍歷后結(jié)果是：FDGBACE

黃色說明只有一個空閑的指針位置，如果是這樣的話我們就面臨一個問題：機器怎么識別到底是存放指針還是線索？

沒錯，她需要一丁點兒提示，為此我們將已經(jīng)定義好的結(jié)構(gòu)進行“擴容”：

3.3 查找二叉樹

二叉查找樹就是二叉排序樹，也叫二叉搜索樹。二叉查找樹或者是一棵空樹，或者是具有下列性質(zhì)的二叉樹： (1) 若左子樹不空，則左子樹上所有結(jié)點的值均小于它的根結(jié)點的值；(2) 若右子樹不空，則右子樹上所有結(jié)點的值均大于它的根結(jié)點的值；(3) 左、右子樹也分別為二叉排序樹；(4) 沒有鍵值相等的結(jié)點。

對于二叉查找樹來說，當(dāng)給定值相同但順序不同時，所構(gòu)建的二叉查找樹形態(tài)是不同的，下面看一個例子。

可以看到，含有n個節(jié)點的二叉查找樹的平均查找長度和樹的形態(tài)有關(guān)。最壞情況下，當(dāng)先后插入的關(guān)鍵字有序時，構(gòu)成的二叉查找樹蛻變?yōu)閱沃洌瑯涞纳疃葹閚，其平均查找長度(n+1)/2(和順序查找相同），最好的情況是二叉查找樹的形態(tài)和折半查找的判定樹相同，其平均查找長度和log2(n)成正比。平均情況下，二叉查找樹的平均查找長度和logn是等數(shù)量級的，所以為了獲得更好的性能，通常在二叉查找樹的構(gòu)建過程需要進行“平衡化處理”，之后我們將介紹平衡二叉樹和紅黑樹，這些均可以使查找樹的高度為O(log(n))。

3.4 平衡二叉樹

平衡二叉樹又稱AVL樹，它或者是一棵空樹，或者是具有下列性質(zhì)的二叉樹：它的左子樹和右子樹都是平衡二叉樹，且左子樹和右子樹的深度之差的絕對值不超過1。

AVL樹是最先發(fā)明的自平衡二叉查找樹算法。在AVL中任何節(jié)點的兩個兒子子樹的高度最大差別為1，所以它也被稱為高度平衡樹，n個結(jié)點的AVL樹最大深度約1.44log2n。查找、插入和刪除在平均和最壞情況下都是O（log n）。增加和刪除可能需要通過一次或多次樹旋轉(zhuǎn)來重新平衡這個樹。

3.5 紅黑樹

R-B Tree，全稱是Red-Black Tree，又稱為“紅黑樹”，它一種特殊的二叉查找樹。紅黑樹的每個節(jié)點上都有存儲位表示節(jié)點的顏色，可以是紅(Red)或黑(Black)。

紅黑樹的特性:

（1）每個節(jié)點或者是黑色，或者是紅色。

（2）根節(jié)點是黑色。

（3）每個葉子節(jié)點（NIL）是黑色。[注意：這里葉子節(jié)點，是指為空(NIL或NULL)的葉子節(jié)點！]

（4）如果一個節(jié)點是紅色的，則它的子節(jié)點必須是黑色的。

（5）從一個節(jié)點到該節(jié)點的子孫節(jié)點的所有路徑上包含相同數(shù)目的黑節(jié)點。

注意：

(01) 特性(3)中的葉子節(jié)點，是只為空(NIL或null)的節(jié)點。

(02) 特性(5)，確保沒有一條路徑會比其他路徑長出倆倍。因而，紅黑樹是相對是接近平衡的二叉樹。

3.5.1 左旋與右旋

紅黑樹的基本操作是添加、刪除。在對紅黑樹進行添加或刪除之后，都會用到旋轉(zhuǎn)方法。為什么呢？道理很簡單，添加或刪除紅黑樹中的節(jié)點之后，紅黑樹就發(fā)生了變化，可能不滿足紅黑樹的5條性質(zhì)，也就不再是一顆紅黑樹了，而是一顆普通的樹。而通過旋轉(zhuǎn)，可以使這顆樹重新成為紅黑樹。簡單點說，旋轉(zhuǎn)的目的是讓樹保持紅黑樹的特性。

(1) 左旋

更復(fù)雜的例子：

(2) 右旋

更復(fù)雜的例子：