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

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

反饋

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

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

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

前情回顧

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

什么是樹？

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

樹狀圖是一種數(shù)據(jù)結(jié)構(gòu)，它是由n（n>=1）個有限結(jié)點組成一個具有層次關(guān)系的集合。把它叫做“樹”是因為它看起來像一棵倒掛的樹，也就是說它是根朝上，而葉朝下的。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

樹的種類

無序樹

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

有序樹

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

二叉樹

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

滿二叉樹

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

完全二叉樹

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

完滿二叉樹

霍夫曼樹

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

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

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

平衡二叉樹

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

AVL樹

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

紅黑樹

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

伸展樹

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

替罪羊樹

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

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

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

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

B+樹

B+樹是B樹的一種變形形式，B+樹上的葉子結(jié)點存儲關(guān)鍵字以及相應(yīng)記錄的地址，葉子結(jié)點以上各層作為索引使用。一棵m階的B+樹定義如下:(1)每個結(jié)點至多有m個子女；(2)除根結(jié)點外，每個結(jié)點至少有[m/2]個子女，根結(jié)點至少有兩個子女；(3)有k個子女的結(jié)點必有k個關(guān)鍵字。B+樹的查找與B樹不同，當(dāng)索引部分某個結(jié)點的關(guān)鍵字與所查的關(guān)鍵字相等時，并不停止查找，應(yīng)繼續(xù)沿著這個關(guān)鍵字左邊的指針向下，一直查到該關(guān)鍵字所在的葉子結(jié)點為止。更適合文件索引系統(tǒng)原因：增刪文件（節(jié)點）時，效率更高，因為B+樹的葉子節(jié)點包含所有關(guān)鍵字，并以有序的鏈表結(jié)構(gòu)存儲，這樣可很好提高增刪效率使用場景：文件系統(tǒng)和數(shù)據(jù)庫系統(tǒng)中常用的B/B+ 樹，他通過對每個節(jié)點存儲個數(shù)的擴(kuò)展，使得對連續(xù)的數(shù)據(jù)能夠進(jìn)行較快的定位和訪問，能夠有效減少查找時間，提高存儲的空間局部性從而減少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é)點再增加指向兄弟的指針；B*樹定義了非葉子結(jié)點關(guān)鍵字個數(shù)至少為(2/3)*M，即塊的最低使用率為2/3（代替B+樹的1/2）。B+樹的分裂：當(dāng)一個結(jié)點滿時，分配一個新的結(jié)點，并將原結(jié)點中1/2的數(shù)據(jù)復(fù)制到新結(jié)點，最后在父結(jié)點中增加新結(jié)點的指針；B+樹的分裂只影響原結(jié)點和父結(jié)點，而不會影響兄弟結(jié)點，所以它不需要指向兄弟的指針；B*樹的分裂：當(dāng)一個結(jié)點滿時，如果它的下一個兄弟結(jié)點未滿，那么將一部分?jǐn)?shù)據(jù)移到兄弟結(jié)點中，再在原結(jié)點插入關(guān)鍵字，最后修改父結(jié)點中兄弟結(jié)點的關(guān)鍵字（因為兄弟結(jié)點的關(guān)鍵字范圍改變了）；如果兄弟也滿了，則在原結(jié)點與兄弟結(jié)點之間增加新結(jié)點，并各復(fù)制1/3的數(shù)據(jù)到新結(jié)點，最后在父結(jié)點增加新結(jié)點的指針；所以，B*樹分配新結(jié)點的概率比B+樹要低，空間使用率更高；

字典樹

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

線索二叉樹