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

1. 樹的基本概念

1.1 樹的定義

樹(Tree)是n(n>=0)個(gè)結(jié)點(diǎn)的有限集析藕。

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

當(dāng)n>1時(shí)雾叭，其余結(jié)點(diǎn)可分為m(m>0)個(gè)互不相交的有限集T1、T2落蝙、…织狐、Tm，其中每一個(gè)集合本身又是一棵樹筏勒，并且稱為根的子樹(SubTree)移迫。

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

n>0時(shí)管行，根結(jié)點(diǎn)是唯一的厨埋，堅(jiān)決不可能存在多個(gè)根結(jié)點(diǎn)。

m>0時(shí)捐顷，子樹的個(gè)數(shù)是沒有限制的荡陷，但它們互相是一定不會(huì)相交的。

1.2 樹的基本概念

(1) 結(jié)點(diǎn)：如上圖迅涮，每一個(gè)圈圈我們就稱為樹的一個(gè)結(jié)點(diǎn)废赞。

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

(3) 葉結(jié)點(diǎn)(Leaf)或終端結(jié)點(diǎn): 度為0的結(jié)點(diǎn)唉地。

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

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

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

(7) 結(jié)點(diǎn)的層次(Level): 從根開始定一起浸赫，根為第一層，根的孩子為第二層赃绊。其雙親在同一層的結(jié)點(diǎn)互為堂兄弟既峡。

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

(9) 森林(Forest):?是 m(m>=0)棵互不相交的樹的集合。對(duì)樹中每個(gè)結(jié)點(diǎn)而言忠售，其子樹的集合即為森林传惠。

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

2.1 雙親表示法

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

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

也就是說(shuō)盼砍，每個(gè)結(jié)點(diǎn)除了知道自己是誰(shuí)之外，還知道它的粑粑媽媽在哪里逝她。

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

可是宁昭，如果我們要知道某結(jié)點(diǎn)的孩子是什么跌宛？那么不好意思，請(qǐng)遍歷整個(gè)樹結(jié)構(gòu)积仗。

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

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

2.2 孩子表示法

我們這次換個(gè)角度來(lái)考慮寂曹，由于樹中每個(gè)結(jié)點(diǎn)可能有多棵子樹哎迄，可以考慮用多重鏈表來(lái)實(shí)現(xiàn)回右。

就像我們雖然有計(jì)劃生育，但我們還是無(wú)法確保每個(gè)家庭只養(yǎng)育一個(gè)孩子的沖動(dòng)漱挚，那么對(duì)于子樹的不確定性也是如此翔烁。

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

缺點(diǎn)十分明顯蹬屹，就是造成了浪費(fèi)！

方法2:

這樣我們就克服了浪費(fèi)這個(gè)概念白华，我們從此走上了節(jié)儉的社會(huì)主義道路慨默！但每個(gè)結(jié)點(diǎn)的度的值不同，初始化和維護(hù)起來(lái)難度巨大吧弧腥？

方法3:最佳解決方案厦取。

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

3. 樹的種類

3.1 二叉樹

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

3.1.1 二叉樹的特點(diǎn)

(1) 每個(gè)結(jié)點(diǎn)最多有兩棵子樹霎箍，所以二叉樹中不存在度大于2的結(jié)點(diǎn)。（注意：不是都需要兩棵子樹岁经，而是最多可以是兩棵朋沮，沒有子樹或者有一棵子樹也都是可以的蛇券。）

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

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

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

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

(5)根結(jié)點(diǎn)既有左子樹又有右子樹蒂胞。

3.1.3 特殊二叉樹

(1) 斜樹

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

(2) 滿二叉樹

坡坡有云：“人有悲歡離合蛤织，月有陰晴圓缺，此事古難全鸿染。但愿人長(zhǎng)久指蚜，千里共長(zhǎng)娟≌墙罚”意思就是說(shuō)完美的那是理想摊鸡，不完美的才是人生绽媒。

但是對(duì)于二叉樹來(lái)說(shuō)，是否存在完美呢免猾？有滴是辕，那就是滿二叉樹啦。

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

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

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

在同樣深度的二叉樹中蚓炬，滿二叉樹的結(jié)點(diǎn)個(gè)數(shù)一定最多松逊，同時(shí)葉子也是最多。

(3) 完全二叉樹

對(duì)一棵具有n個(gè)結(jié)點(diǎn)的二叉樹按層序編號(hào)肯夏，如果編號(hào)為i(1<=i<=n)的結(jié)點(diǎn)與同樣深度的滿二叉樹中編號(hào)為i的結(jié)點(diǎn)位置完全相同经宏，則這棵二叉樹稱為完全二叉樹。

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

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

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

如果結(jié)點(diǎn)度為1型雳，則該結(jié)點(diǎn)只有左孩子举娩。

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

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

3.1.4 二叉樹性質(zhì)

(1) 在二叉樹的第i層上至多有2^(i-1)個(gè)結(jié)點(diǎn)(i>=1)槽奕。

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

(3) 對(duì)任何一棵二叉樹T房轿，如果其終端結(jié)點(diǎn)數(shù)為n0粤攒，度為2的結(jié)點(diǎn)數(shù)為n2，則n0=n2+1囱持。

首先我們?cè)偌僭O(shè)度為1的結(jié)點(diǎn)數(shù)為n1夯接，則二叉樹T的結(jié)點(diǎn)總數(shù)n=n0+n1+n2

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

所以n-1=n1+2*n2

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

最后n0=n2+1

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

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

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

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

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

所以完全二叉樹的結(jié)點(diǎn)數(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í)取對(duì)數(shù)肝匆，得到k-1<=log?n

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

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

如果i = 1，則結(jié)點(diǎn) i 是二叉樹的根注整，無(wú)雙親能曾；如果i > 1，則其雙親是結(jié)點(diǎn)?i/2?

如果2i > n肿轨，則結(jié)點(diǎn) i 無(wú)做左孩子(結(jié)點(diǎn) i 為葉子結(jié)點(diǎn))寿冕；否則其左孩子是結(jié)點(diǎn)2i

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

3.1.4 二叉樹的存儲(chǔ)

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

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

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

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

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

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

但是考慮到一種極端的情況浑娜，回顧一下斜樹佑力，如果是一個(gè)又斜樹式散，那么會(huì)變成什么樣筋遭？

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

既然順序存儲(chǔ)方式的適用性不強(qiáng)，那么我們就要考慮鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)啦暴拄。二叉樹的存儲(chǔ)按照國(guó)際慣例來(lái)說(shuō)一般也是采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的漓滔。

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

3.1.5 二叉樹的遍歷

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

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

(1) 前序遍歷

若二叉樹為空琳骡，則空操作返回锅论，否則先訪問(wèn)根結(jié)點(diǎn)，然后前序遍歷左子樹楣号，再前序遍歷右子樹最易。

遍歷的順序?yàn)椋篈BDHIEJCFKG

(2) 中序遍歷

若樹為空，則空操作返回炫狱，否則從根結(jié)點(diǎn)開始（注意并不是先訪問(wèn)根結(jié)點(diǎn)）藻懒，中序遍歷根結(jié)點(diǎn)的左子樹，然后是訪問(wèn)根結(jié)點(diǎn)视译，最后中序遍歷右子樹嬉荆。

遍歷的順序?yàn)椋篐DIBEJAFKCG

注意！是先F再K,因?yàn)槭窍缺闅v結(jié)點(diǎn)的左子樹然后結(jié)點(diǎn)然后右子樹酷含。因?yàn)闆]有左子樹员寇，所以直接結(jié)點(diǎn)再右子樹。

(3) 后序遍歷

若樹為空第美，則空操作返回蝶锋，否則從左到右先葉子后結(jié)點(diǎn)的方式遍歷訪問(wèn)左右子樹，最后訪問(wèn)根結(jié)點(diǎn)什往。

遍歷的順序?yàn)椋篐IDJEBKFGCA

(4) 層序遍歷

若樹為空扳缕，則空操作返回，否則從樹的第一層别威，也就是根結(jié)點(diǎn)開始訪問(wèn)躯舔，從上而下逐層遍歷，在同一層中省古，按從左到右的順序?qū)Y(jié)點(diǎn)逐個(gè)訪問(wèn)粥庄。

遍歷的順序?yàn)椋篈BCDEFGHIJK

3.2 線索二叉樹

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

10個(gè)琳拭！

沒錯(cuò)训堆，中序遍歷可以拯救地球！

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

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

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

黃色說(shuō)明只有一個(gè)空閑的指針位置画恰，如果是這樣的話我們就面臨一個(gè)問(wèn)題：機(jī)器怎么識(shí)別到底是存放指針還是線索卖怜？

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

3.3 查找二叉樹

二叉查找樹就是二叉排序樹马靠，也叫二叉搜索樹。二叉查找樹或者是一棵空樹蔼两，或者是具有下列性質(zhì)的二叉樹： (1) 若左子樹不空甩鳄，則左子樹上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值；(2) 若右子樹不空额划，則右子樹上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值妙啃；(3) 左、右子樹也分別為二叉排序樹俊戳；(4) 沒有鍵值相等的結(jié)點(diǎn)揖赴。

對(duì)于二叉查找樹來(lái)說(shuō)，當(dāng)給定值相同但順序不同時(shí)抑胎，所構(gòu)建的二叉查找樹形態(tài)是不同的燥滑，下面看一個(gè)例子。

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

3.4 平衡二叉樹

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

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

3.5 紅黑樹

R-B Tree，全稱是Red-Black Tree分尸，又稱為“紅黑樹”锦聊，它一種特殊的二叉查找樹。紅黑樹的每個(gè)節(jié)點(diǎn)上都有存儲(chǔ)位表示節(jié)點(diǎn)的顏色箩绍，可以是紅(Red)或黑(Black)孔庭。

紅黑樹的特性:

（1）每個(gè)節(jié)點(diǎn)或者是黑色，或者是紅色材蛛。

（2）根節(jié)點(diǎn)是黑色圆到。

（3）每個(gè)葉子節(jié)點(diǎn)（NIL）是黑色。[注意：這里葉子節(jié)點(diǎn)卑吭，是指為空(NIL或NULL)的葉子節(jié)點(diǎn)芽淡！]

（4）如果一個(gè)節(jié)點(diǎn)是紅色的，則它的子節(jié)點(diǎn)必須是黑色的豆赏。

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

注意：

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

(02) 特性(5)己单，確保沒有一條路徑會(huì)比其他路徑長(zhǎng)出倆倍。因而耙饰，紅黑樹是相對(duì)是接近平衡的二叉樹纹笼。

3.5.1 左旋與右旋

紅黑樹的基本操作是添加、刪除苟跪。在對(duì)紅黑樹進(jìn)行添加或刪除之后廷痘，都會(huì)用到旋轉(zhuǎn)方法。為什么呢件已？道理很簡(jiǎn)單笋额，添加或刪除紅黑樹中的節(jié)點(diǎn)之后，紅黑樹就發(fā)生了變化篷扩，可能不滿足紅黑樹的5條性質(zhì)兄猩，也就不再是一顆紅黑樹了，而是一顆普通的樹。而通過(guò)旋轉(zhuǎn)枢冤，可以使這顆樹重新成為紅黑樹鸠姨。簡(jiǎn)單點(diǎn)說(shuō)，旋轉(zhuǎn)的目的是讓樹保持紅黑樹的特性淹真。

(1) 左旋

更復(fù)雜的例子：

(2) 右旋

更復(fù)雜的例子：