樹(shù)

樹(shù)型結(jié)構(gòu)是一類重要的非線性數(shù)據(jù)結(jié)構(gòu)。其中以樹(shù)和二叉樹(shù)最為常用，直觀看來(lái)，樹(shù)是以分支關(guān)系定義的層次結(jié)構(gòu)。把它叫做“樹(shù)”是因?yàn)樗？雌饋?lái)像一棵倒掛的樹(shù)，也就是說(shuō)它常是根朝上，而葉朝下的。

樹(shù)結(jié)構(gòu)在客觀世界中廣泛存在，如人類社會(huì)的族譜和各種社會(huì)組織機(jī)構(gòu)都可用樹(shù)來(lái)形象表示。樹(shù)在計(jì)算機(jī)領(lǐng)域中也得到廣泛應(yīng)用，如在操作系統(tǒng)中,可用樹(shù)來(lái)表示文件系統(tǒng)的結(jié)構(gòu)。又如在數(shù)據(jù)庫(kù)系統(tǒng)中，樹(shù)形結(jié)構(gòu)也是信息的重要組織形式之一1。

定義

常用定義

樹(shù)是個(gè)結(jié)點(diǎn)的有限集1。當(dāng)時(shí)，稱為空樹(shù)。在任意一棵樹(shù)非空樹(shù)中應(yīng)滿足：

(1) 有且僅有一個(gè)特定的稱為根 (root) 的結(jié)點(diǎn)；

(2) 當(dāng)時(shí)，其余結(jié)點(diǎn)可分為個(gè)互不相交的有限集，其中每一個(gè)集合本身又是一顆樹(shù)，并且稱為根的子樹(shù)(SubTree)1。

其他定義

樹(shù)在不同領(lǐng)域也有不同的定義。

1、在數(shù)學(xué)中，樹(shù)是一種無(wú)向圖，其中不存在環(huán)路（即無(wú)回路），且任意兩個(gè)結(jié)點(diǎn)之間有且僅有一條簡(jiǎn)單路徑相連2。這種定義主要用于圖論和離散數(shù)學(xué)中，用于研究樹(shù)的性質(zhì)和特征。

2、在操作系統(tǒng)中，樹(shù)是一種用于表示文件系統(tǒng)的結(jié)構(gòu)，其中根目錄位于樹(shù)的頂部，子目錄和文件位于根目錄下3。這種定義主要用于操作系統(tǒng)設(shè)計(jì)和文件管理。

3、在數(shù)據(jù)庫(kù)中，樹(shù)是一種用于表示層次關(guān)系的數(shù)據(jù)結(jié)構(gòu)，樹(shù)結(jié)構(gòu)常用于實(shí)現(xiàn)數(shù)據(jù)庫(kù)的索引、表示層次數(shù)據(jù)關(guān)系（如組織結(jié)構(gòu)、分類目錄）以及優(yōu)化查詢操作4。這種定義主要用于數(shù)據(jù)庫(kù)設(shè)計(jì)和數(shù)據(jù)管理，以提高數(shù)據(jù)檢索效率和結(jié)構(gòu)化數(shù)據(jù)的存儲(chǔ)。

基本術(shù)語(yǔ)

1. 結(jié)點(diǎn)：包含一個(gè)數(shù)據(jù)元素及若干指向其子樹(shù)的分支；
2. 結(jié)點(diǎn)的度：一個(gè)結(jié)點(diǎn)擁有的子樹(shù)的數(shù)目；
3. 葉子或終端結(jié)點(diǎn)：度為0的結(jié)點(diǎn)；
4. 非終端結(jié)點(diǎn)或分支結(jié)點(diǎn)：度不為0的結(jié)點(diǎn)；
5. 樹(shù)的度：樹(shù)內(nèi)各結(jié)點(diǎn)的度的最大值；
6. 孩子結(jié)點(diǎn)或子結(jié)點(diǎn)：結(jié)點(diǎn)的子樹(shù)的根稱為該結(jié)點(diǎn)的孩子結(jié)點(diǎn)或子結(jié)點(diǎn)；
7. 雙親結(jié)點(diǎn)或父結(jié)點(diǎn)：若一個(gè)結(jié)點(diǎn)含有子結(jié)點(diǎn)，則這個(gè)結(jié)點(diǎn)稱為其子結(jié)點(diǎn)的雙親結(jié)點(diǎn)或父結(jié)點(diǎn)；
8. 兄弟結(jié)點(diǎn)：同一個(gè)雙親的孩子之間互稱兄弟；
9. 祖先結(jié)點(diǎn)：從根到該結(jié)點(diǎn)所經(jīng)分支上的所有結(jié)點(diǎn)；
10. 子孫結(jié)點(diǎn)：以某結(jié)點(diǎn)為根的子樹(shù)中任一結(jié)點(diǎn)都稱為該結(jié)點(diǎn)的子孫；
11. 結(jié)點(diǎn)的層次：從根開(kāi)始定義起，根為第一層，根的孩子為第二層。若某結(jié)點(diǎn)在第層．則其子樹(shù)的根就在第層；
12. 堂兄弟結(jié)點(diǎn)：其雙親在同一層的結(jié)點(diǎn)互為堂兄弟；
13. 樹(shù)的深度或高度：樹(shù)中結(jié)點(diǎn)的最大層次；
14. 森林：由棵互不相交的樹(shù)的集合稱為森林;
15. 有序樹(shù)和無(wú)序樹(shù)：樹(shù)中結(jié)點(diǎn)的各子樹(shù)從左到右是有次序的，不能互換，稱該樹(shù)為有序樹(shù)，否則稱為無(wú)序樹(shù)；
16. 路徑和路徑長(zhǎng)度：路徑是由樹(shù)中的兩個(gè)結(jié)點(diǎn)之間的結(jié)點(diǎn)序列構(gòu)成的。而路徑長(zhǎng)度是路徑上所經(jīng)過(guò)的邊的個(gè)數(shù)5；

常見(jiàn)類型的樹(shù)

二叉樹(shù)

二叉樹(shù) (Binary Tree)的特點(diǎn)是每個(gè)結(jié)點(diǎn)至多只有兩棵子樹(shù) （即二叉樹(shù)中不存在度大于2的結(jié)點(diǎn)），分別稱為左子樹(shù)和右子樹(shù)。二叉樹(shù)是一種遞歸的數(shù)據(jù)結(jié)構(gòu)，可以是空樹(shù)（即沒(méi)有任何結(jié)點(diǎn)），或者是由根結(jié)點(diǎn)及其左右子樹(shù)組成。并且，二叉樹(shù)的子樹(shù)有左右之分，其次序不能任意顛倒15。

二叉樹(shù)的特點(diǎn)包括：

（1）每個(gè)結(jié)點(diǎn)最多有兩個(gè)子結(jié)點(diǎn)，分別稱為左子結(jié)點(diǎn)和右子結(jié)點(diǎn)。

（2）左子樹(shù)和右子樹(shù)都是二叉樹(shù)，它們本身也可以是空樹(shù)。

（3）二叉樹(shù)的結(jié)點(diǎn)結(jié)構(gòu)包含一個(gè)數(shù)據(jù)元素和指向左右子樹(shù)的指針。

二叉樹(shù)有多種類型，包括：二叉排序樹(shù)、完全二叉樹(shù)、滿二叉樹(shù)、平衡二叉樹(shù)等。二叉樹(shù)在計(jì)算機(jī)科學(xué)中有著廣泛的應(yīng)用，其簡(jiǎn)單的結(jié)構(gòu)和豐富的操作使得它成為了許多其他數(shù)據(jù)結(jié)構(gòu)和算法的基礎(chǔ)。二叉樹(shù)示例，如下圖所示：

二叉排序樹(shù)

二叉排序樹(shù)(Binary Sort Tree)，也稱為二叉查找樹(shù)或二叉搜索樹(shù)。其或者是一棵空樹(shù)；或者是具有下列性質(zhì)的二叉樹(shù)5：

（1）若它的左子樹(shù)不空，則左子樹(shù)上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值；

（2）若它的右子樹(shù)不空，則右子樹(shù)上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值；

（3）它的左、右子樹(shù)也分別為二叉排序樹(shù)。

其中葉結(jié)點(diǎn)除外的所有結(jié)點(diǎn)均含有兩個(gè)子樹(shù)的樹(shù)被稱為滿二叉樹(shù)。除最后一層外，所有層都是滿結(jié)點(diǎn)，且最后一層缺右邊連續(xù)結(jié)點(diǎn)的二叉樹(shù)稱為完全二叉樹(shù)。

二叉排序樹(shù)的特性使得在其中進(jìn)行搜索、插入和刪除操作時(shí)具有較高的效率。因此，二叉排序樹(shù)常被用于實(shí)現(xiàn)集合、字典等數(shù)據(jù)結(jié)構(gòu)，也用于構(gòu)建符號(hào)表、數(shù)據(jù)庫(kù)索引等應(yīng)用。然而，需要注意的是，二叉排序樹(shù)的性能取決于其樹(shù)形態(tài)的平衡性，如果樹(shù)的高度較大，則操作的效率可能會(huì)下降，這時(shí)可以考慮使用平衡二叉樹(shù)來(lái)解決這個(gè)問(wèn)題，例如AVL樹(shù)、紅黑樹(shù)等。二叉排序樹(shù)示例，如下圖所示：

滿二叉樹(shù)

對(duì)于一個(gè)二叉樹(shù)，如果每一個(gè)層的結(jié)點(diǎn)數(shù)都達(dá)到最大值，則這個(gè)二叉樹(shù)就是滿二叉樹(shù)。也就是說(shuō)，如果一個(gè)二叉樹(shù)的層數(shù)為，且結(jié)點(diǎn)總數(shù)是，則它就是滿二叉樹(shù)15。

可以對(duì)滿二叉樹(shù)按層序編號(hào)：約定編號(hào)從根結(jié)點(diǎn)（根結(jié)點(diǎn)編號(hào)為1）起，自上而下，自左向右。這樣，每個(gè)結(jié)點(diǎn)對(duì)應(yīng)一個(gè)編號(hào)，對(duì)于編號(hào)為的結(jié)點(diǎn)，若有雙親，則其雙親為，若有左孩子，則左孩子為，若有右孩子，則右孩子為。滿二叉樹(shù)示例，如下圖所示：

完全二叉樹(shù)

對(duì)于一個(gè)高度為，有個(gè)結(jié)點(diǎn)的二叉樹(shù)，當(dāng)且僅當(dāng)其每個(gè)結(jié)點(diǎn)都與高度為的滿二叉樹(shù)中編號(hào)為的結(jié)點(diǎn)一一對(duì)應(yīng)時(shí)，稱為完全二叉樹(shù)15。完全二叉樹(shù)示例，如下圖所示：

平衡二叉樹(shù)

平衡二叉樹(shù)(Balanced Binary Tree 或 Height-Balanced Tree)又稱AVL樹(shù)。它或者是一棵空樹(shù)，或者是具有下列性質(zhì)的二叉樹(shù)：它的任意結(jié)點(diǎn)的左子樹(shù)和右子樹(shù)都是平衡二叉樹(shù)，且左子樹(shù)和右子樹(shù)的深度之差的絕對(duì)值不超過(guò)11。

若將二叉樹(shù)上結(jié)點(diǎn)的平衡因子BF(Balance Factor)定義為該結(jié)點(diǎn)的左子樹(shù)的深度減去它的右子樹(shù)的深度，則平衡二叉樹(shù)上所有結(jié)點(diǎn)的平衡因子只可能是-1、0和1。只要二叉樹(shù)上有一個(gè)結(jié)點(diǎn)的平衡因子的絕對(duì)值大于1，則該二叉樹(shù)就是不平衡的[1]。平衡二叉樹(shù)示例，如下圖所示：

紅黑樹(shù)

為了保持平衡二叉樹(shù)（AVL樹(shù)）的平衡性，插入和刪除操作后，非常頻繁地調(diào)整全樹(shù)整體拓?fù)浣Y(jié)構(gòu)，代價(jià)較大。為此在AVL樹(shù)的平衡標(biāo)準(zhǔn)上進(jìn)一步放寬條件，引入了紅黑樹(shù)（Red-Black Tree）的結(jié)構(gòu)5。

一棵紅黑樹(shù)是滿足如下紅黑性質(zhì)的二叉排序樹(shù)567：

（1）每個(gè)結(jié)點(diǎn)是紅色，或是黑色的；

（2）根結(jié)點(diǎn)是黑色；

（3）葉子結(jié)點(diǎn)（虛構(gòu)的外部結(jié)點(diǎn)、NULL結(jié)點(diǎn)）都是黑色的；

（4）不存在兩個(gè)相鄰的紅結(jié)點(diǎn)（即紅結(jié)點(diǎn)的父結(jié)點(diǎn)和孩子結(jié)點(diǎn)均是黑色的）；

（5）對(duì)每個(gè)結(jié)點(diǎn)、從該結(jié)點(diǎn)到任一葉子結(jié)點(diǎn)的簡(jiǎn)單路徑上，所含黑結(jié)點(diǎn)的數(shù)量相同。

如果插入和刪除操作較少，查找操作較多，采用AVL樹(shù)比較合適，否則使用紅黑樹(shù)更為合適。但由于維護(hù)這種高度平衡所付出的代價(jià)比獲得的收益大得多，因此紅黑樹(shù)的實(shí)際應(yīng)用更廣泛，C++中的map和set（Java中TreeMap和TreeSet就是用紅黑樹(shù)實(shí)現(xiàn)的5）。紅黑樹(shù)示例，如下圖所示：

哈夫曼樹(shù)

哈夫曼樹(shù)（Huffman Tree）是一種特殊的二叉樹(shù)，用于數(shù)據(jù)壓縮中的哈夫曼編碼（Huffman Coding）算法。哈夫曼樹(shù)的構(gòu)建基于字符出現(xiàn)的頻率，通常用于壓縮數(shù)據(jù)，使得出現(xiàn)頻率高的字符使用較短的編碼，而出現(xiàn)頻率低的字符使用較長(zhǎng)的編碼，從而達(dá)到壓縮數(shù)據(jù)的目的561。

構(gòu)建哈夫曼樹(shù)的步驟包括：

（1）統(tǒng)計(jì)字符頻率：首先，統(tǒng)計(jì)待壓縮的數(shù)據(jù)中每個(gè)字符出現(xiàn)的頻率。

（2）構(gòu)建哈夫曼樹(shù)：根據(jù)字符頻率構(gòu)建一棵哈夫曼樹(shù)。構(gòu)建的過(guò)程是通過(guò)將出現(xiàn)頻率最低的兩個(gè)結(jié)點(diǎn)合并為一個(gè)新結(jié)點(diǎn)，新結(jié)點(diǎn)的頻率為原結(jié)點(diǎn)頻率之和，并將新結(jié)點(diǎn)插入到樹(shù)中，重復(fù)這一過(guò)程直到只剩下一個(gè)根結(jié)點(diǎn)為止。

（3）生成編碼：對(duì)于哈夫曼樹(shù)中的每個(gè)字符，從根結(jié)點(diǎn)開(kāi)始沿著路徑向下，每次移動(dòng)到左子結(jié)點(diǎn)則表示該字符編碼中添加一個(gè) 0，每次移動(dòng)到右子結(jié)點(diǎn)則表示添加一個(gè) 1，直到到達(dá)葉子結(jié)點(diǎn)。這樣，每個(gè)字符都可以對(duì)應(yīng)一個(gè)唯一的編碼。

（4）數(shù)據(jù)壓縮：將原始數(shù)據(jù)中的每個(gè)字符替換為對(duì)應(yīng)的哈夫曼編碼，從而實(shí)現(xiàn)數(shù)據(jù)的壓縮。

哈夫曼樹(shù)示例，如下圖所示：

B樹(shù)

B樹(shù)是為磁盤(pán)或其他直接存取的輔助存儲(chǔ)設(shè)備而設(shè)計(jì)的一種平衡搜素樹(shù)6。B樹(shù)類似于紅黑樹(shù)，但它們?cè)诮档痛疟P(pán) I/0操作數(shù)方面要更好一些。許多數(shù)據(jù)庫(kù)系統(tǒng)使用B樹(shù)或者B樹(shù)的變種來(lái)存儲(chǔ)信息6。

B樹(shù)與紅黑樹(shù)的不同之處在于B樹(shù)的結(jié)點(diǎn)可以有很多孩子，從數(shù)個(gè)到數(shù)千個(gè)，能夠保持較低的高度并且保持?jǐn)?shù)據(jù)的有序性，從而提高了數(shù)據(jù)的檢索效率和存儲(chǔ)效率6。B樹(shù)示例，如下圖所示：

B+樹(shù)

B+樹(shù)是一種常見(jiàn)的B樹(shù)變種，類似于B樹(shù)，但在某些方面有所不同。例如：B+樹(shù)的非葉子結(jié)點(diǎn)只包含鍵值，不存儲(chǔ)實(shí)際數(shù)據(jù)。相比之下，B樹(shù)的非葉子結(jié)點(diǎn)不僅包含鍵值，還包含對(duì)應(yīng)的數(shù)據(jù)5；由于B+樹(shù)的葉子結(jié)點(diǎn)是通過(guò)指針相連的有序鏈表，因此范圍查詢的性能更好。相比之下，B樹(shù)需要進(jìn)行中序遍歷來(lái)查找范圍內(nèi)的鍵值5。

B+樹(shù)通常用于數(shù)據(jù)庫(kù)系統(tǒng)和文件系統(tǒng)中，特別是用于實(shí)現(xiàn)索引結(jié)構(gòu)6。B+樹(shù)示例，如下圖所示：

樹(shù)的遍歷

二叉樹(shù)的遍歷

對(duì)于二叉樹(shù)，常用的遍歷方式包括：先序遍歷、中序遍歷、后序遍歷和層次遍歷15。

• **先序遍歷（PreOrder）**的操作過(guò)程如下：

若二叉樹(shù)為空，則什么也不做；否則，

（1）訪問(wèn)根結(jié)點(diǎn)；

（2）先序遍歷左子樹(shù)；

（3）先序遍歷右子樹(shù)。

<pre data-lang="clike">void PreOrder(BiTree T){ //先序遍歷 if(T!=NULL){ visit(T);    //訪問(wèn)根結(jié)點(diǎn) PreOrder(T->lchild); //遞歸遍歷左子樹(shù) PreOrder(T->rchild); //遞歸遍歷右子樹(shù) }}

• **中序遍歷（InOrder）**的操作過(guò)程如下：

若二叉樹(shù)為空，則什么也不做；否則，

（1）中序遍歷左子樹(shù)；

（2）訪問(wèn)根結(jié)點(diǎn)；

（3）中序遍歷右子樹(shù)。

<pre data-lang="clike">void InOrder(BiTree T){ //中序遍歷 if(T!=NULL){ InOrder(T->lchild); //遞歸遍歷左子樹(shù) visit(T);    //訪問(wèn)根結(jié)點(diǎn) InOrder(T->rchild); //遞歸遍歷右子樹(shù) }}

• **后序遍歷（PostOrder）**的操作過(guò)程如下：

若二叉樹(shù)為空，則什么也不做；否則，

（1）后序遍歷左子樹(shù)；

（2）后序遍歷右子樹(shù)；

（3）訪問(wèn)根結(jié)點(diǎn)。

<pre data-lang="clike">void PostOrder(BiTree T){ //后序遍歷偽代碼 if(T!=NULL){ PostOrder(T->lchild); //遞歸遍歷 PostOrder(T->rchild); //遞歸遍歷右子樹(shù) visit(T);    //訪問(wèn)根結(jié)點(diǎn) }}

• **層次遍歷（LevelOrder）**的操作過(guò)程如下：

（1）首先借助一個(gè)隊(duì)列，先將二叉樹(shù)根結(jié)點(diǎn)入隊(duì)，然后出隊(duì)，訪問(wèn)出隊(duì)結(jié)點(diǎn)；

（2） 若它有左子樹(shù)，則將左子樹(shù)根結(jié)點(diǎn)入隊(duì)；

（3） 若它有右子樹(shù)，則將右子樹(shù)根結(jié)點(diǎn)入隊(duì)；

（4） 然后出隊(duì)，訪問(wèn)出隊(duì)結(jié)點(diǎn)。如此反復(fù)，直到隊(duì)列為空[1,5]。

<pre data-lang="clike">void LevelOrder(BiTree T){ //層次遍歷 InitQueue(Q);    //初始化輔助隊(duì)列 BiTree P; EnQueue(Q,T);    //將根結(jié)點(diǎn)入隊(duì) while(!IsEmpty(Q)){  //隊(duì)列不空則循環(huán) DeQueue(Q,P);   //隊(duì)頭結(jié)點(diǎn)出隊(duì) visit(p);     //訪問(wèn)出隊(duì)結(jié)點(diǎn) if(p->lchild!=NULL)  EnQueue(Q,p->lchild); //左子樹(shù)不空，則左子樹(shù)根結(jié)點(diǎn)入隊(duì) if(p->rchild!=NULL)  EnQueue(Q,p->rchild); //右子樹(shù)不空，則右子樹(shù)根結(jié)點(diǎn)入隊(duì) }}

例如：如下圖所示：

其先序遍歷為ABDECF（根-左-右）

其中序遍歷為DBEAFC（左-根-右）（僅二叉樹(shù)有中序遍歷）

其后序遍歷為DEBFCA（左-右-根）

其層次遍歷為ABCDEF

一般樹(shù)的遍歷

樹(shù)的遍歷是指用某種方式訪問(wèn)樹(shù)中的每個(gè)結(jié)點(diǎn)，且僅訪問(wèn)一次。主要有三種方式15：

1. 先根遍歷：若樹(shù)非空，先訪問(wèn)樹(shù)的根結(jié)點(diǎn)，然后依次先根遍歷根結(jié)點(diǎn)的每棵子樹(shù)。其遍歷序列與其轉(zhuǎn)換為二叉樹(shù)的先序序列相同。
2. 后根遍歷：若樹(shù)非空，先依次后根遍歷根結(jié)點(diǎn)的每棵子樹(shù)，然后訪問(wèn)樹(shù)的根結(jié)點(diǎn)。其遍歷序列與其轉(zhuǎn)換為二叉樹(shù)的中序序列相同。
3. 層次遍歷：與二叉樹(shù)的層次遍歷思想基本相同，即按層序依次訪問(wèn)各結(jié)點(diǎn)。

例如：如下圖所示：

其先根遍歷為ABEFG