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

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

反饋

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

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

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

前情回顧

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

什么是樹？

那么，有沒有一種情況，每個(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ù)據(jù)結(jié)構(gòu)，它是由n（n>=1）個(gè)有限結(jié)點(diǎn)組成一個(gè)具有層次關(guān)系的集合。把它叫做“樹”是因?yàn)樗雌饋硐褚豢玫箳斓臉洌簿褪钦f它是根朝上，而葉朝下的。

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

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

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

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

1、結(jié)點(diǎn)(Node)：表示樹中的數(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)所擁有的子樹的個(gè)數(shù)，在圖中，結(jié)點(diǎn)A的度為3（注意，E,F也符合樹的定義（樹的定義見下文）所以B的度為2）。

3、樹的度(Degree of Tree)：樹中各結(jié)點(diǎn)度的最大值（節(jié)點(diǎn)A和D的度都為最大值3）。上圖中樹的度為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)子樹的根。上圖中，結(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)為根的子樹中的任一結(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)到樹中某結(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、樹的深度(Depth of Tree)：樹中結(jié)點(diǎn)的最大層次數(shù)。上圖中，樹的深度為3。

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

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

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

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

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

樹的種類

無序樹

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

有序樹

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

二叉樹

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

滿二叉樹

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

完全二叉樹

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

完滿二叉樹

霍夫曼樹

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

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

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

平衡二叉樹

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

AVL樹

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

紅黑樹

紅黑樹是每個(gè)節(jié)點(diǎn)都帶有顏色屬性的二叉查找樹，顏色或紅色或黑色。在二叉查找樹強(qiáng)制一般要求以外，對于任何有效的紅黑樹我們增加了如下的額外要求:性質(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)。使用場景：紅黑樹多用于搜索,插入,刪除操作多的情況下紅黑樹應(yīng)用比較廣泛：1. 廣泛用在C++的STL中。map和set都是用紅黑樹實(shí)現(xiàn)的。2. 著名的linux進(jìn)程調(diào)度Completely Fair Scheduler,用紅黑樹管理進(jìn)程控制塊。3.epoll在內(nèi)核中的實(shí)現(xiàn)，用紅黑樹管理事件塊4.nginx中，用紅黑樹管理timer等

伸展樹

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

替罪羊樹

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

B-tree（B-樹或者B樹）

一棵m階B樹(balanced tree of order m)是一棵平衡的m路搜索樹。它或者是空樹，或者是滿足下列性質(zhì)的樹：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)部子樹個(gè)數(shù) k 滿足：┌m/2┐ <= k <= m ；4、所有的葉子結(jié)點(diǎn)都位于同一層。

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

B+樹

B+樹是B樹的一種變形形式，B+樹上的葉子結(jié)點(diǎn)存儲(chǔ)關(guān)鍵字以及相應(yīng)記錄的地址，葉子結(jié)點(diǎn)以上各層作為索引使用。一棵m階的B+樹定義如下:(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+樹的查找與B樹不同，當(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)锽+樹的葉子節(jié)點(diǎn)包含所有關(guān)鍵字，并以有序的鏈表結(jié)構(gòu)存儲(chǔ)，這樣可很好提高增刪效率使用場景：文件系統(tǒng)和數(shù)據(jù)庫系統(tǒng)中常用的B/B+ 樹，他通過對每個(gè)節(jié)點(diǎn)存儲(chǔ)個(gè)數(shù)的擴(kuò)展，使得對連續(xù)的數(shù)據(jù)能夠進(jìn)行較快的定位和訪問，能夠有效減少查找時(shí)間，提高存儲(chǔ)的空間局部性從而減少IO操作。他廣泛用于文件系統(tǒng)及數(shù)據(jù)庫中，如：Windows：HPFS 文件系統(tǒng)Mac：HFS，HFS+ 文件系統(tǒng)Linux：ResiserFS，XFS，Ext3FS，JFS 文件系統(tǒng)數(shù)據(jù)庫：ORACLE，MYSQL，SQLSERVER 等中B樹：有序數(shù)組+平衡多叉樹B+樹：有序數(shù)組鏈表+平衡多叉樹

B*樹

B*樹是B+樹的變體，在B+樹的非根和非葉子結(jié)點(diǎn)再增加指向兄弟的指針；B*樹定義了非葉子結(jié)點(diǎn)關(guān)鍵字個(gè)數(shù)至少為(2/3)*M，即塊的最低使用率為2/3（代替B+樹的1/2）。B+樹的分裂：當(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+樹的分裂只影響原結(jié)點(diǎn)和父結(jié)點(diǎn)，而不會(huì)影響兄弟結(jié)點(diǎn)，所以它不需要指向兄弟的指針；B*樹的分裂：當(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*樹分配新結(jié)點(diǎn)的概率比B+樹要低，空間使用率更高；

字典樹

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

線索二叉樹