樹

樹型結(jié)構(gòu)是一類重要的非線性數(shù)據(jù)結(jié)構(gòu)。其中以樹和二叉樹最為常用，直觀看來，樹是以分支關(guān)系定義的層次結(jié)構(gòu)。把它叫做“樹”是因為它?？雌饋硐褚豢玫箳斓臉洌簿褪钦f它常是根朝上，而葉朝下的。

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

定義

常用定義

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

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

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

其他定義

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

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

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

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

基本術(shù)語

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

常見類型的樹

二叉樹

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

二叉樹的特點包括：

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

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

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

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

二叉排序樹

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

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

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

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

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

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

滿二叉樹

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

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

完全二叉樹

對于一個高度為，有個結(jié)點的二叉樹，當(dāng)且僅當(dāng)其每個結(jié)點都與高度為的滿二叉樹中編號為的結(jié)點一一對應(yīng)時，稱為完全二叉樹15。完全二叉樹示例，如下圖所示：

平衡二叉樹

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

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

紅黑樹

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

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

（1）每個結(jié)點是紅色，或是黑色的；

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

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

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

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

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

哈夫曼樹

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

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

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

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

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

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

哈夫曼樹示例，如下圖所示：

B樹

B樹是為磁盤或其他直接存取的輔助存儲設(shè)備而設(shè)計的一種平衡搜素樹6。B樹類似于紅黑樹，但它們在降低磁盤 I/0操作數(shù)方面要更好一些。許多數(shù)據(jù)庫系統(tǒng)使用B樹或者B樹的變種來存儲信息6。

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

B+樹

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

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

樹的遍歷

二叉樹的遍歷

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

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

若二叉樹為空，則什么也不做；否則，

（1）訪問根結(jié)點；

（2）先序遍歷左子樹；

（3）先序遍歷右子樹。

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

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

若二叉樹為空，則什么也不做；否則，

（1）中序遍歷左子樹；

（2）訪問根結(jié)點；

（3）中序遍歷右子樹。

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

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

若二叉樹為空，則什么也不做；否則，

（1）后序遍歷左子樹；

（2）后序遍歷右子樹；

（3）訪問根結(jié)點。

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

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

（1）首先借助一個隊列，先將二叉樹根結(jié)點入隊，然后出隊，訪問出隊結(jié)點；

（2） 若它有左子樹，則將左子樹根結(jié)點入隊；

（3） 若它有右子樹，則將右子樹根結(jié)點入隊；

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

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

例如：如下圖所示：

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

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

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

其層次遍歷為ABCDEF

一般樹的遍歷

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

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

例如：如下圖所示：

其先根遍歷為ABEFG