什么是樹(shù)？數(shù)據(jù)結(jié)構(gòu)之樹(shù)講解!

享受養(yǎng)生的年輕人 2022-03-12 18:17:29 瀏覽數(shù) (4913)

反饋

對(duì)于程序員而言，樹(shù)這種數(shù)據(jù)結(jié)構(gòu)是一種比較常見(jiàn)的數(shù)據(jù)結(jié)構(gòu)，今天小編就來(lái)介紹一下數(shù)這種數(shù)據(jù)結(jié)構(gòu)，然后介紹一個(gè)簡(jiǎn)單的二叉樹(shù)的C語(yǔ)言實(shí)現(xiàn)。

前驅(qū)內(nèi)容

什么是線性表？數(shù)據(jù)結(jié)構(gòu)之線性表講解!

前情回顧

首先，我們先來(lái)溫習(xí)一下什么是數(shù)據(jù)結(jié)構(gòu)，我們之前介紹過(guò)，在實(shí)際使用數(shù)據(jù)的時(shí)候我們會(huì)把一些有關(guān)聯(lián)的點(diǎn)組合起來(lái)進(jìn)行使用，這就是有結(jié)構(gòu)的數(shù)據(jù)。我們也介紹過(guò)一種簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)，這種數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)是一個(gè)數(shù)據(jù)連接著另一個(gè)數(shù)據(jù)，后一個(gè)數(shù)據(jù)連接著前一個(gè)數(shù)據(jù)。最后這些數(shù)據(jù)會(huì)像線一樣連成一串，這就是線性表。

什么是樹(shù)？

那么，有沒(méi)有一種情況，每個(gè)數(shù)據(jù)都可以連接多個(gè)數(shù)據(jù)呢？確實(shí)存在著這樣的情況，當(dāng)每個(gè)數(shù)據(jù)連接著多個(gè)數(shù)據(jù)的時(shí)候，就是圖（后續(xù)文章會(huì)介紹）。當(dāng)每個(gè)數(shù)據(jù)后面連接著0到多個(gè)數(shù)據(jù)，而前面指連接著一個(gè)數(shù)據(jù)的時(shí)候，就是樹(shù)，就像這樣：

樹(shù)狀圖是一種數(shù)據(jù)結(jié)構(gòu)，它是由n（n>=1）個(gè)有限結(jié)點(diǎn)組成一個(gè)具有層次關(guān)系的集合。把它叫做“樹(shù)”是因?yàn)樗雌饋?lái)像一棵倒掛的樹(shù)，也就是說(shuō)它是根朝上，而葉朝下的。

關(guān)于樹(shù)的結(jié)構(gòu)

我們之前有談到數(shù)據(jù)之間的關(guān)系，對(duì)于線性表而言，一個(gè)數(shù)據(jù)只會(huì)連接另一個(gè)數(shù)據(jù)，這樣的關(guān)系我們稱為一對(duì)一的關(guān)系，也就是說(shuō)，一個(gè)數(shù)據(jù)只會(huì)有一個(gè)后繼節(jié)點(diǎn)。

對(duì)于數(shù)而說(shuō)，一個(gè)數(shù)據(jù)后面可能會(huì)連接一個(gè)數(shù)據(jù)，也可能連接多個(gè)數(shù)據(jù)，甚至有可能一個(gè)數(shù)據(jù)都沒(méi)有，這樣的關(guān)系我們稱為一對(duì)多的關(guān)系。

對(duì)于線性表而言，因?yàn)榻Y(jié)構(gòu)比較簡(jiǎn)單，所以數(shù)據(jù)之間互相稱為前驅(qū)節(jié)點(diǎn)，后續(xù)節(jié)點(diǎn)，代表數(shù)據(jù)間的關(guān)系。而在樹(shù)中，明顯復(fù)雜得多。以下是對(duì)一顆數(shù)的結(jié)構(gòu)描述（以下面的樹(shù)狀圖為例）：

1、結(jié)點(diǎn)(Node)：表示樹(shù)中的數(shù)據(jù)元素，由數(shù)據(jù)項(xiàng)和數(shù)據(jù)元素之間的關(guān)系組成。在圖中，共有10個(gè)結(jié)點(diǎn)。

2、結(jié)點(diǎn)的度(Degree of Node)：結(jié)點(diǎn)所擁有的子樹(shù)的個(gè)數(shù)，在圖中，結(jié)點(diǎn)A的度為3（注意，E,F也符合樹(shù)的定義（樹(shù)的定義見(jiàn)下文）所以B的度為2）。

3、樹(shù)的度(Degree of Tree)：樹(shù)中各結(jié)點(diǎn)度的最大值（節(jié)點(diǎn)A和D的度都為最大值3）。上圖中樹(shù)的度為3。

4、葉子結(jié)點(diǎn)(Leaf Node)：度為0的結(jié)點(diǎn)，也叫終端結(jié)點(diǎn)。上圖中，結(jié)點(diǎn)E、F、G、H、I、J都是葉子結(jié)點(diǎn)。

5、分支結(jié)點(diǎn)(Branch Node)：度不為0的結(jié)點(diǎn)，也叫非終端結(jié)點(diǎn)或內(nèi)部結(jié)點(diǎn)。上圖中，結(jié)點(diǎn)A、B、C、D是分支結(jié)點(diǎn)。

6、孩子(Child)：結(jié)點(diǎn)子樹(shù)的根。上圖中，結(jié)點(diǎn)B、C、D是結(jié)點(diǎn)A的孩子。

7、雙親(Parent)：結(jié)點(diǎn)的上層結(jié)點(diǎn)叫該結(jié)點(diǎn)的雙親。上圖中，結(jié)點(diǎn)B、C、D的雙親是結(jié)點(diǎn)A。

8、祖先(Ancestor)：從根到該結(jié)點(diǎn)所經(jīng)分支上的所有結(jié)點(diǎn)。上圖中，結(jié)點(diǎn)E的祖先是A和B。

9、子孫(Descendant)：以某結(jié)點(diǎn)為根的子樹(shù)中的任一結(jié)點(diǎn)。上圖中，除A之外的所有結(jié)點(diǎn)都是A的子孫。

10、兄弟(Brother)：同一雙親的孩子。上圖中，結(jié)點(diǎn)B、C、D互為兄弟。

11、結(jié)點(diǎn)的層次(Level of Node)：從根結(jié)點(diǎn)到樹(shù)中某結(jié)點(diǎn)所經(jīng)路徑上的分支數(shù)稱為該結(jié)點(diǎn)的層次。根結(jié)點(diǎn)的層次規(guī)定為1，其余結(jié)點(diǎn)的層次等于其雙親結(jié)點(diǎn)的層次加1。

12、堂兄弟(Sibling)：同一層的雙親不同的結(jié)點(diǎn)。上圖中，G和H互為堂兄弟。

13、樹(shù)的深度(Depth of Tree)：樹(shù)中結(jié)點(diǎn)的最大層次數(shù)。上圖中，樹(shù)的深度為3。

14、無(wú)序樹(shù)(Unordered Tree)：樹(shù)中任意一個(gè)結(jié)點(diǎn)的各孩子結(jié)點(diǎn)之間的次序構(gòu)成無(wú)關(guān)緊要的樹(shù)。通常樹(shù)指無(wú)序樹(shù)。

15、有序樹(shù)(Ordered Tree)：樹(shù)中任意一個(gè)結(jié)點(diǎn)的各孩子結(jié)點(diǎn)有嚴(yán)格排列次序的樹(shù)。二叉樹(shù)是有序樹(shù)，因?yàn)槎鏄?shù)中每個(gè)孩子結(jié)點(diǎn)都確切定義為是該結(jié)點(diǎn)的左孩子結(jié)點(diǎn)還是右孩子結(jié)點(diǎn)。

16、森林(Forest)：m(m≥0)棵樹(shù)的集合。自然界中的樹(shù)和森林的概念差別很大，但在數(shù)據(jù)結(jié)構(gòu)中樹(shù)和森林的概念差別很小。從定義可知，一棵樹(shù)由根結(jié)點(diǎn)和m個(gè)子樹(shù)構(gòu)成，若把樹(shù)的根結(jié)點(diǎn)刪除，則樹(shù)變成了包含m棵樹(shù)的森林。當(dāng)然，根據(jù)定義，一棵樹(shù)也可以稱為森林。

如何判斷一個(gè)節(jié)點(diǎn)算不算樹(shù)（樹(shù)的定義）

有且僅有一個(gè)稱為根的結(jié)點(diǎn)。
如果n>1, 除根結(jié)點(diǎn)以外其它結(jié)點(diǎn)可以分為m(m>0)個(gè)不相交的集合T1,T2,T3,T4,......,Tm，其中每一個(gè)集合都是一棵樹(shù)。樹(shù)T1, T2, T3,......,Tm稱為這棵樹(shù)的子樹(shù)。

樹(shù)的種類

無(wú)序樹(shù)

樹(shù)的任意節(jié)點(diǎn)的子節(jié)點(diǎn)沒(méi)有順序關(guān)系。

有序樹(shù)

樹(shù)的任意節(jié)點(diǎn)的子節(jié)點(diǎn)有順序關(guān)系。

二叉樹(shù)

樹(shù)的任意節(jié)點(diǎn)至多包含兩棵子樹(shù)。二叉樹(shù)遍歷:二叉樹(shù)的遍歷是指從二叉樹(shù)的根結(jié)點(diǎn)出發(fā)，按照某種次序依次訪問(wèn)二叉樹(shù)中的所有結(jié)點(diǎn)，使得每個(gè)結(jié)點(diǎn)被訪問(wèn)一次，且僅被訪問(wèn)一次。二叉樹(shù)的訪問(wèn)次序可以分為四種：前序遍歷中序遍歷后序遍歷層次遍歷

滿二叉樹(shù)

葉子節(jié)點(diǎn)都在同一層并且除葉子節(jié)點(diǎn)外的所有節(jié)點(diǎn)都有兩個(gè)子節(jié)點(diǎn)。

完全二叉樹(shù)

對(duì)于一顆二叉樹(shù)，假設(shè)其深度為d（d>1）。除第d層外的所有節(jié)點(diǎn)構(gòu)成滿二叉樹(shù)，且第d層所有節(jié)點(diǎn)從左向右連續(xù)地緊密排列，這樣的二叉樹(shù)被稱為完全二叉樹(shù)；

完滿二叉樹(shù)

霍夫曼樹(shù)

帶權(quán)路徑最短的二叉樹(shù)稱為哈夫曼樹(shù)或最優(yōu)二叉樹(shù)。

二叉查找樹(shù)（二叉搜索樹(shù)、二叉排序樹(shù)、BST）[這幾個(gè)都是別名]

若任意節(jié)點(diǎn)的左子樹(shù)不空，則左子樹(shù)上所有節(jié)點(diǎn)的值均小于它的根節(jié)點(diǎn)的值；若任意節(jié)點(diǎn)的右子樹(shù)不空，則右子樹(shù)上所有節(jié)點(diǎn)的值均大于它的根節(jié)點(diǎn)的值；任意節(jié)點(diǎn)的左、右子樹(shù)也分別為二叉查找樹(shù)；沒(méi)有鍵值相等的節(jié)點(diǎn)。

平衡二叉樹(shù)

它是一棵空樹(shù)或它的左右兩個(gè)子樹(shù)的高度差的絕對(duì)值不超過(guò)1，并且左右兩個(gè)子樹(shù)都是一棵平衡二叉樹(shù)，同時(shí)，平衡二叉樹(shù)必定是二叉搜索樹(shù)。

AVL樹(shù)

在計(jì)算機(jī)科學(xué)中，AVL樹(shù)是最先發(fā)明的自平衡二叉查找樹(shù)。在AVL樹(shù)中任何節(jié)點(diǎn)的兩個(gè)子樹(shù)的高度最大差別為1，所以它也被稱為高度平衡樹(shù)。增加和刪除可能需要通過(guò)一次或多次樹(shù)旋轉(zhuǎn)來(lái)重新平衡這個(gè)樹(shù)。AVL樹(shù)本質(zhì)上還是一棵二叉搜索樹(shù)，它的特點(diǎn)是：1.本身首先是一棵二叉搜索樹(shù)。2.帶有平衡條件：每個(gè)結(jié)點(diǎn)的左右子樹(shù)的高度之差的絕對(duì)值（平衡因子）最多為1。也就是說(shuō)，AVL樹(shù)，本質(zhì)上是帶了平衡功能的二叉查找樹(shù)（二叉排序樹(shù)，二叉搜索樹(shù)）。使用場(chǎng)景：AVL樹(shù)適合用于插入刪除次數(shù)比較少，但查找多的情況。也在Windows進(jìn)程地址空間管理中得到了使用旋轉(zhuǎn)的目的是為了降低樹(shù)的高度，使其平衡

紅黑樹(shù)

紅黑樹(shù)是每個(gè)節(jié)點(diǎn)都帶有顏色屬性的二叉查找樹(shù)，顏色或紅色或黑色。在二叉查找樹(shù)強(qiáng)制一般要求以外，對(duì)于任何有效的紅黑樹(shù)我們?cè)黾恿巳缦碌念~外要求:性質(zhì)1. 節(jié)點(diǎn)是紅色或黑色。性質(zhì)2. 根節(jié)點(diǎn)是黑色。性質(zhì)3. 每個(gè)紅色節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)都是黑色。(從每個(gè)葉子到根的所有路徑上不能有兩個(gè)連續(xù)的紅色節(jié)點(diǎn))性質(zhì)4. 從任一節(jié)點(diǎn)到其每個(gè)葉子的所有路徑都包含相同數(shù)目的黑色節(jié)點(diǎn)。使用場(chǎng)景：紅黑樹(shù)多用于搜索,插入,刪除操作多的情況下紅黑樹(shù)應(yīng)用比較廣泛：1. 廣泛用在C++的STL中。map和set都是用紅黑樹(shù)實(shí)現(xiàn)的。2. 著名的linux進(jìn)程調(diào)度Completely Fair Scheduler,用紅黑樹(shù)管理進(jìn)程控制塊。3.epoll在內(nèi)核中的實(shí)現(xiàn)，用紅黑樹(shù)管理事件塊4.nginx中，用紅黑樹(shù)管理timer等

伸展樹(shù)

伸展樹(shù)（Splay Tree），也叫分裂樹(shù)，是一種二叉排序樹(shù)，它能在O(log n)內(nèi)完成插入、查找和刪除操作。它由丹尼爾·斯立特Daniel Sleator 和羅伯特·恩卓·塔揚(yáng)Robert Endre Tarjan 在1985年發(fā)明的。在伸展樹(shù)上的一般操作都基于伸展操作：假設(shè)想要對(duì)一個(gè)二叉查找樹(shù)執(zhí)行一系列的查找操作，為了使整個(gè)查找時(shí)間更小，被查頻率高的那些條目就應(yīng)當(dāng)經(jīng)常處于靠近樹(shù)根的位置。于是想到設(shè)計(jì)一個(gè)簡(jiǎn)單方法，在每次查找之后對(duì)樹(shù)進(jìn)行重構(gòu)，把被查找的條目搬移到離樹(shù)根近一些的地方。伸展樹(shù)應(yīng)運(yùn)而生。伸展樹(shù)是一種自調(diào)整形式的二叉查找樹(shù)，它會(huì)沿著從某個(gè)節(jié)點(diǎn)到樹(shù)根之間的路徑，通過(guò)一系列的旋轉(zhuǎn)把這個(gè)節(jié)點(diǎn)搬移到樹(shù)根去。它的優(yōu)勢(shì)在于不需要記錄用于平衡樹(shù)的冗余信息。

替罪羊樹(shù)

替罪羊樹(shù)是計(jì)算機(jī)科學(xué)中，一種基于部分重建的自平衡二叉搜索樹(shù)。在替罪羊樹(shù)上，插入或刪除節(jié)點(diǎn)的平攤最壞時(shí)間復(fù)雜度是O(log n)，搜索節(jié)點(diǎn)的最壞時(shí)間復(fù)雜度是O(log n)。在非平衡的二叉搜索樹(shù)中，每次操作以后檢查操作路徑，找到最高的滿足max(size(son_L),size(son_R))>alpha*size(this)的結(jié)點(diǎn)，重建整個(gè)子樹(shù)。這樣就得到了替罪羊樹(shù)，而被重建的子樹(shù)的原來(lái)的根就被稱為替罪羊節(jié)點(diǎn)。替罪羊樹(shù)替罪羊樹(shù)是一棵自平衡二叉搜索樹(shù)，由ArneAndersson提出。替罪羊樹(shù)的主要思想就是將不平衡的樹(shù)壓成一個(gè)序列,然后暴力重構(gòu)成一顆平衡的樹(shù)。

B-tree（B-樹(shù)或者B樹(shù)）

一棵m階B樹(shù)(balanced tree of order m)是一棵平衡的m路搜索樹(shù)。它或者是空樹(shù)，或者是滿足下列性質(zhì)的樹(shù)：1、根結(jié)點(diǎn)至少有兩個(gè)子女；2、每個(gè)非根節(jié)點(diǎn)所包含的關(guān)鍵字個(gè)數(shù) j 滿足：┌m/2┐ - 1 <= j <= m - 1；3、除根結(jié)點(diǎn)以外的所有結(jié)點(diǎn)（不包括葉子結(jié)點(diǎn)）的度數(shù)正好是關(guān)鍵字總數(shù)加1，故內(nèi)部子樹(shù)個(gè)數(shù) k 滿足：┌m/2┐ <= k <= m ；4、所有的葉子結(jié)點(diǎn)都位于同一層。

B樹(shù)(B-Tree)是一種自平衡的樹(shù),它是一種多路搜索樹(shù)（并不是二叉的），能夠保證數(shù)據(jù)有序。同時(shí)它還保證了在查找、插入、刪除等操作時(shí)性能都能保持在O(logn)，為大塊數(shù)據(jù)的讀寫(xiě)操作做了優(yōu)化,同時(shí)它也可以用來(lái)描述外部存儲(chǔ)(支持對(duì)保存在磁盤(pán)或者網(wǎng)絡(luò)上的符號(hào)表進(jìn)行外部查找)

B+樹(shù)

B+樹(shù)是B樹(shù)的一種變形形式，B+樹(shù)上的葉子結(jié)點(diǎn)存儲(chǔ)關(guān)鍵字以及相應(yīng)記錄的地址，葉子結(jié)點(diǎn)以上各層作為索引使用。一棵m階的B+樹(shù)定義如下:(1)每個(gè)結(jié)點(diǎn)至多有m個(gè)子女；(2)除根結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)至少有[m/2]個(gè)子女，根結(jié)點(diǎn)至少有兩個(gè)子女；(3)有k個(gè)子女的結(jié)點(diǎn)必有k個(gè)關(guān)鍵字。B+樹(shù)的查找與B樹(shù)不同，當(dāng)索引部分某個(gè)結(jié)點(diǎn)的關(guān)鍵字與所查的關(guān)鍵字相等時(shí)，并不停止查找，應(yīng)繼續(xù)沿著這個(gè)關(guān)鍵字左邊的指針向下，一直查到該關(guān)鍵字所在的葉子結(jié)點(diǎn)為止。更適合文件索引系統(tǒng)原因：增刪文件（節(jié)點(diǎn)）時(shí)，效率更高，因?yàn)锽+樹(shù)的葉子節(jié)點(diǎn)包含所有關(guān)鍵字，并以有序的鏈表結(jié)構(gòu)存儲(chǔ)，這樣可很好提高增刪效率使用場(chǎng)景：文件系統(tǒng)和數(shù)據(jù)庫(kù)系統(tǒng)中常用的B/B+ 樹(shù)，他通過(guò)對(duì)每個(gè)節(jié)點(diǎn)存儲(chǔ)個(gè)數(shù)的擴(kuò)展，使得對(duì)連續(xù)的數(shù)據(jù)能夠進(jìn)行較快的定位和訪問(wèn)，能夠有效減少查找時(shí)間，提高存儲(chǔ)的空間局部性從而減少I(mǎi)O操作。他廣泛用于文件系統(tǒng)及數(shù)據(jù)庫(kù)中，如：Windows：HPFS 文件系統(tǒng)Mac：HFS，HFS+ 文件系統(tǒng)Linux：ResiserFS，XFS，Ext3FS，JFS 文件系統(tǒng)數(shù)據(jù)庫(kù)：ORACLE，MYSQL，SQLSERVER 等中B樹(shù)：有序數(shù)組+平衡多叉樹(shù)B+樹(shù)：有序數(shù)組鏈表+平衡多叉樹(shù)

B*樹(shù)

B*樹(shù)是B+樹(shù)的變體，在B+樹(shù)的非根和非葉子結(jié)點(diǎn)再增加指向兄弟的指針；B*樹(shù)定義了非葉子結(jié)點(diǎn)關(guān)鍵字個(gè)數(shù)至少為(2/3)*M，即塊的最低使用率為2/3（代替B+樹(shù)的1/2）。B+樹(shù)的分裂：當(dāng)一個(gè)結(jié)點(diǎn)滿時(shí)，分配一個(gè)新的結(jié)點(diǎn)，并將原結(jié)點(diǎn)中1/2的數(shù)據(jù)復(fù)制到新結(jié)點(diǎn)，最后在父結(jié)點(diǎn)中增加新結(jié)點(diǎn)的指針；B+樹(shù)的分裂只影響原結(jié)點(diǎn)和父結(jié)點(diǎn)，而不會(huì)影響兄弟結(jié)點(diǎn)，所以它不需要指向兄弟的指針；B*樹(shù)的分裂：當(dāng)一個(gè)結(jié)點(diǎn)滿時(shí)，如果它的下一個(gè)兄弟結(jié)點(diǎn)未滿，那么將一部分?jǐn)?shù)據(jù)移到兄弟結(jié)點(diǎn)中，再在原結(jié)點(diǎn)插入關(guān)鍵字，最后修改父結(jié)點(diǎn)中兄弟結(jié)點(diǎn)的關(guān)鍵字（因?yàn)樾值芙Y(jié)點(diǎn)的關(guān)鍵字范圍改變了）；如果兄弟也滿了，則在原結(jié)點(diǎn)與兄弟結(jié)點(diǎn)之間增加新結(jié)點(diǎn)，并各復(fù)制1/3的數(shù)據(jù)到新結(jié)點(diǎn)，最后在父結(jié)點(diǎn)增加新結(jié)點(diǎn)的指針；所以，B*樹(shù)分配新結(jié)點(diǎn)的概率比B+樹(shù)要低，空間使用率更高；

字典樹(shù)

又稱單詞查找樹(shù)，Trie樹(shù)，是一種樹(shù)形結(jié)構(gòu)，是一種哈希樹(shù)的變種。典型應(yīng)用是用于統(tǒng)計(jì)，排序和保存大量的字符串（但不僅限于字符串），所以經(jīng)常被搜索引擎系統(tǒng)用于文本詞頻統(tǒng)計(jì)。它的優(yōu)點(diǎn)是：利用字符串的公共前綴來(lái)減少查詢時(shí)間，最大限度地減少無(wú)謂的字符串比較，查詢效率比哈希樹(shù)高。它有3個(gè)基本性質(zhì)：根節(jié)點(diǎn)不包含字符，除根節(jié)點(diǎn)外每一個(gè)節(jié)點(diǎn)都只包含一個(gè)字符；從根節(jié)點(diǎn)到某一節(jié)點(diǎn)，路徑上經(jīng)過(guò)的字符連接起來(lái)，為該節(jié)點(diǎn)對(duì)應(yīng)的字符串；每個(gè)節(jié)點(diǎn)的所有子節(jié)點(diǎn)包含的字符都不相同。

線索二叉樹(shù)

在二叉樹(shù)的結(jié)點(diǎn)上加上線索的二叉樹(shù)稱為線索二叉樹(shù)，對(duì)二叉樹(shù)以某種遍歷方式（如先序、中序、后序或?qū)哟蔚龋┻M(jìn)行遍歷，使其變?yōu)榫€索二叉樹(shù)的過(guò)程稱為對(duì)二叉樹(shù)進(jìn)行線索化。