樹型結構 是一類重要的非線性數據結構，其中以樹和二叉樹最為常用，直觀來看，樹是以分支關系定義的層次結構。樹型結構在客觀世界中廣泛存在，比如人類社會中的祖輩關系，社會機構組織等等都可以用樹來形象表示。樹型結構在計算機領域中也得到了廣泛應用。

Part1 樹

1.1 樹的定義

樹（Tree） 是n（n>=0）n（n>=0） n （ n >=0）個結點的有限集，在任意一棵非空樹中滿足：

• 有且僅有一個特定的結點稱為 根（Root） 的結點；
• 當n>1 n>1 n>1時，其余結點可分為m（m>0） m（m>0）m（m>0）個互不相交的有限集T1、T2、?????、TmT1、T2、·····、TmT1、T2、?????、Tm，其中每一個集合本身又是一棵樹，并且稱為根的子樹（SubTree）。**

樹的結構定義是一個遞歸的定義，即在樹的定義中又用到樹的概念， 遞歸是樹固有的特性 。在樹型結構中，除了根結點以外，任何一個結點有且僅有一個前驅，每個結點可以有0個或多個后繼。結點數為0的樹又稱之為空樹。

1.2 樹的基本術語

樹的結點包含一個數據元素及若干指向其子樹的分支。結點擁有的子樹數稱為結點的 度（Degree） **，**以上圖為例，結點D的度為3，因為結點D有三條分支結構；依次列舉，結點C的度為1，結點B的度為2等等。

度為0的結點稱為葉子（Leaf）結點或 終端結點 ，以上圖為例，結點K、L、F、G、M、I、J都是度為0的結點，所以他們也被稱為葉子結點或終端結點。

度不為0的結點稱為非終端結點或 分支結點 。除根節點外，分支結點也稱為內部結點，以上圖為例，結點B、C、D、E、H的度都不為零，所以他們稱為非終端結點或分支結點。

樹的度是樹內各結點的度的最大值，以上圖為例，在整棵樹中，結點中度的最大值是3，所以樹的度就為3。

結點的子樹的根稱為該結點的 孩子（Child） ，相應地，該結點稱為孩子的 雙親（Parent） ，以上圖為例，結點B的孩子結點為E和F，反之，結點B也是結點E、F的雙親結點。

同一個雙親的孩子之間互稱 兄弟（Sibling）， 以上圖為例，結點H、I、J的雙親為同一個結點D，所以結點H、I、J互為兄弟結點。

結點的祖先是從根到該結點所經分支上的所有結點，反之，以某結點為根的子樹中的任一結點都稱為該結點的 子孫 。以上圖為例，結點G的祖先就為結點A和C，反之，結點C的子孫就為結點G。

結點的層次（Level） 是從根開始定義的，根為第一層，根的孩子為第二層（自上往下數）以上圖為例，結點G的層次為3。

樹中結點的最大層次稱為樹的深度(Depth) 或高度（其實就是整棵樹總共有多少層）以上圖為例，樹的深度或高度為4。

結點數 = 總度數 + 1 以上圖為例，結點A的度數為3；結點B的度數為2；結點C的度數為1，結點D的度數為3；結點E的度數為2；結點H的度數為1；其余結點K、L、F、G、M、I、J的度數為0，所以這棵樹的結點數就等于：

T結點數 = 3+2+1+3+2+1+1；最后結果為13

1.3 有序樹和無序樹

• 有序樹 ——邏輯上看，樹中結點的各子樹從左至右是有次序的，不能互換；
• 無序樹 ——邏輯上看，樹中結點的各子樹從左至右是無次序的，可以互換。

1.4 森林

森林（Forest） 是m（m>=0) m（m>=0）m（m>=0）棵互不相交的樹的集合，對樹中的每個結點而言，其子樹的集合即為森林。

森林可以為空

Part2 二叉樹

2.1 二叉樹的定義

二叉樹（Binary Tree） 是另一種樹型結構，它的特點是每個結點至多只有兩棵子樹（即二叉樹中不存在度大于2的結點），并且，二叉樹的子樹有左右之分， 其次序不能任意顛倒 。

二叉樹或為空，或是由一個根結點加上兩棵分別稱為左子樹和右子樹的、互不相交的二叉樹構成，由于這兩棵子樹也是二叉樹，則由二叉樹的定義，它們也可以是空樹。由此， 二叉樹可以有5種基本形態 。

2.2 二叉樹的性質

二叉樹具有下列重要特性

• 性質一： 在二叉樹的第iii層上之多有2i-1個結點（i> =1 i>=1 i>=1）；
• 性質二： 深度為kkk的二叉樹之多有2k-1個結點（k> =1 k>=1 k>=1）；
• 性質三： 對任何一棵二叉樹T，如果其終端結點數為n0 n0 n0，度為2的結點數為n 2 n2 n2，則有n0=n2+n1n0=n2+n1n0=n2+1。

2.3 二叉樹的分類

2.3.1 滿二叉樹

一棵深度為 kkk且有2k-1個結點的二叉樹稱為 滿二叉樹 ，這種樹的特點是每一層上的結點數都是最大結點數，只有最后一層是葉子結點且不存在度為1的結點。

2.3.2 完全二叉樹

深度為 kkk的，有 nnn 個結點的二叉樹，當且僅當其每一個結點都與深度為 kkk的滿二叉樹中編號從1至nnn的結點一一對應時，稱之為 完全二叉樹 ，在一棵完全二叉樹中只有最后兩層可能為葉子結點，且最多只有一個度為1的結點。

完全二叉樹的三個重要特性：

• 特性一 : 具有nnn個結點的完全二叉樹的深度為log2nlog2nlog2n向下取整+1；
• 特性二: 如果對一棵有nnn個結點的完全二叉樹（其深度為log2nlog2nlog2n向下取整+1）的結點按層序編號（從第一層到第log2nlog2nlog2n向下取整+1層，每層從左到右），則對任一結點i （1<=i<=n）i（1<=i<=n）i（1<=i<=n），有以下結論：

1. 如果i = 1 i=1 i=1，則結點iii是二叉樹的根，無雙親，如果i >1 i>1 i>1，則雙親（Parent）為結點i /2i/2i/2向下取整；
2. 如果2i >n2i>n2 i>n，則結點i無左孩子（結點iii為葉子結點）；否則其左孩子（Lchild）是結點2i；
3. 如果2i+1>n2i+1>n2i+1>n，則結點i無右孩子，否則其右孩子（Rchild）是結點2i+1 2i+1 2i+1；

• 特性三： 滿二叉樹是一種特殊的完全二叉樹，但完全二叉樹不一定是滿二叉樹。

2.3.3 二叉排序樹

左子樹上所有結點的關鍵字均小于根結點的關鍵字，右子樹上所有結點的關鍵字均大于根結點的關鍵字，左子樹和右子樹又各是一棵二叉排序樹。

二叉排序樹用于元素的搜索和排序:

2.3.4 平衡二叉樹

• 樹上任何一個結點的左子樹和右子樹的深度之差不超過1；
• 平衡二叉樹能有更高的搜索效率。

2.4 二叉樹的存儲結構

2.4.1 順序存儲結構

按照 順序存儲結構的定義 ，用一組地址連續的存儲單元依次自上而下、從左往右存儲完全二叉樹的結點元素，即將完全二叉樹上編號為i ii的結點元素存儲在如上定義的一維數組中下標為i?1 i-1 i?1的分量中。

//二叉樹的順序存儲表示
#define MaxSize 100     //二叉樹的最大結點數
struct TreeNode
{
   ElemType value;      //結點中的數據元素
   bool isEmpty;        //結點是否為空
};

//定義一個長度為MaxSize的數組t，按照從上而下，從左至右的順序依次存儲二叉樹中的各個結點
TreeNode t[MaxSize];

對于一般二叉樹，則應將其每個結點與完全二叉樹上的結點相對照，存儲在一維數組中的對應分量中。順序存儲結構更多僅適用于完全二叉樹的存儲。

2.4.2 鏈式存儲結構

由二叉樹的定義得知， 二叉樹的結點由一個數據元素和分別指向其左、右子樹的兩個分支構成 ，則表示二叉樹的鏈表中的結點至少包含三個域： 數據域 和 左、右指針域 。有時，為了便于找到結點的雙親，則還可以在結點結構中增加一個指向其雙親結點的指針域。 利用這兩種結點結構所得的二叉樹的存儲結構分別稱之為 二叉鏈表 和三叉鏈表。

//二叉樹的二叉鏈表存儲表示
typedefstruct BiTNode
{
    TElemType data;		//數據域
    struct BiTNode *lchild, *rchild      //左右孩子指針
}BiTNode,*BiTree;

2.5 二叉樹的遍歷

在二叉樹的一些應用中，常常要求在樹中查找具有某種特征的結點，或者對樹中全部結點逐一進行某種處理。回顧二叉樹的遞歸定義可知，二叉樹是由三個基本單元組成： 根節點、左子樹和右子樹 ，因此，二叉樹的遍歷分為先（根）序遍歷、中（根）序遍歷、后（根）序遍歷和層次遍歷。

2.5.1 先（根）序遍歷

若二叉樹為空，則空操作，否則：

• 訪問根結點；
• 先序遍歷左子樹；
• 先序遍歷右子樹；

2.5.2 中（根）序遍歷

若二叉樹為空，則空操作，否則：

• 中序遍歷左子樹；
• 訪問根結點；
• 中序遍歷右子樹；

2.5.3 后（根）序遍歷

若二叉樹為空，則空操作，否則：

• 后序遍歷左子樹；
• 后序遍歷右子樹；
• 訪問根結點；

2.5.4 層次遍歷

• 初始化一個隊列；
• 根結點入隊；
• 若隊列非空，則隊頭結點出隊，訪問該結點，并將其左、右孩子插入隊尾；
• 重復上一步，直到隊列為空。

2.6 線索二叉樹

在遍歷二叉樹時，要想找到某個結點的前驅和后繼的信息，得運用二叉樹已知的遍歷方法從頭開始遍歷，然后在遍歷的過程中動態獲取其結點的前驅和后繼的信息，那有沒有一種方法是已知該結點就已經知道其前驅和后繼的信息了呢？答案肯定是有的，為了解決二叉樹遍歷時所存在的一些問題，線索二叉樹也孕育而生。那什么是 線索二叉樹 呢？

簡單理解就是利用空鏈域來存放結點的前驅和后繼的信息，方便尋找前驅結點和后繼結點，提高遍歷效率。因為n個結點的二叉樹，有n+1 n+1 n+1個空鏈域，所以可以利用這些空鏈域來記錄前驅，后繼的信息。若結點有左子樹，則其lchild lchildlchild域指示其左孩子，否則令lchild lchildlchild域指示其前驅；若結點有右子樹，則其rchild rchildrchild域指示其右孩子，否則令rchild rchildrchild域指示其后繼。為了避免混淆，尚需改變結點結構，增加兩個標志域。

以這種結點結構構成的二叉鏈表作為二叉樹的存儲結構，叫做 線索鏈表 。其中指向結點前驅和后繼的指針，叫做 線索 。加上線索的二叉樹又稱之為 線索二叉樹（Threaded Binary Tree） 。對二叉樹以某種次序遍歷使其變為線索二叉樹的過程叫做 線索化 。

在線索樹上進行遍歷，只要先找到序列中的第一個結點，然后依次找結點后繼直至其后繼為空時而止。

Part3樹和森林

3.1 樹的存儲結構

3.1.1 雙親表示法

每個結點中保存指向 “雙親” 的指針；
優點：查找指定結點的雙親很方便；
缺點：查找指定結點的孩子只能從頭遍歷。

//樹的雙親表示法存儲表示
#define MAX_TREE_SIZE 100
typedefstruct PTNode{//結點結構
    TElemType data;
    int parent;     //雙親位置域
}PTNode;
typedefstruct{//樹結構
    PTNode nodes[MAX_TREE_SIZE];
    int r,n;    //根的位置和結點數
}PTree;

3.1.2 孩子表示法（順序+鏈式存儲）

//樹的孩子表示法鏈表存儲表示
typedefstruct CTNode{//孩子結點
    int child;
    struct CTNode *next;
}*ChildPtr;
typedefstruct{
    TElemType data;
    ChildPtr firstchild;    //孩子鏈表頭指針
}CTBox;
typedefstruct{
    CTBox nodes[MAX_TREE_SIZE];
    int n,r;        //結點數和根的位置
}CTree;

3.1.3 子兄弟表示法（鏈式存儲）

優點：可以利用二叉樹操作來處理樹

//樹的孩子兄弟表示法鏈表存儲表示
typedefstruct CSNode{//孩子結點
    ElemType data;
    struct CSNode *firstchild, *nextsibling;
}CSNode,*CSTree;

3.2 樹和森林的遍歷

3.2.1 樹的遍歷

樹的 先根遍歷 ：若樹非空、先訪問根結點，再依次對每棵子樹進行先根遍歷；
樹的 后根遍歷 ：若樹非空、先依次對每棵子樹進行后根遍歷，最后再訪問根結點。
樹的 層次遍歷 （用隊列實現）：

• 若樹非空，則根結點入隊；
• 若隊列非空，隊頭元素出隊并訪問，同時將該元素的孩子依次入隊；
• 重復2直到隊列為空。

3.2.2 森林的遍歷

（1）先序遍歷森林

若森林非空，則可按照下述規則遍歷：

• 訪問森林中第一棵樹的根結點；
• 先序遍歷第一棵樹中根結點的子樹森林；
• 先序遍歷除去第一棵樹之后剩余的樹構成的森林。

（2）中序遍歷森林

若森林非空，則可按照下述規則遍歷：

• 中序遍歷森林中第一顆樹的根結點的子樹森林；
• 訪問第一棵樹的根結點；
• 中序遍歷除去第一棵樹的根結點的子樹森林。

Part4 哈夫曼樹

哈夫曼（Huffman）樹 ，又稱為 最優樹 ，是一類帶權路徑長度最短的樹。

4.1 最優二叉樹（哈夫曼樹）

假設有nnn個權值( W1，W2，???????，Wm) (W1，W2，·······，Wm)(W1，W2，???????，Wm)，試構造一棵有n個葉子結點的二叉樹，每個葉子結點帶權值為WiWiWi，則其中帶權路徑長度WPL最小的二叉樹稱為最優二叉樹或哈夫曼樹。

• 路徑和路徑長度的概念

從樹中的一個結點到另一個結點之間的分支構成這兩個結點之間的路徑，路徑上的分支數目稱之為 路徑長度 。 樹的路徑長度 是從樹根到每一個結點的路徑長度之和。

結點的帶權路徑長度為該結點到樹根之間的路徑長度與結點上權值的乘積， 樹的帶權路徑長度 為樹中所有葉子結點的帶權路徑長度之和，通常記作WPL。

樹的帶權路徑長度

4.2 哈夫曼樹的構造

根據給定的nnn個權值( W1，W2，??????，Wn)(W1，W2，······，Wn)(W1，W2，??????，Wn)構成的n棵二叉樹的集合F = (T1，T2，??????，Tn)F=(T1，T2，······，Tn)F=(T1，T2，??????，T**n)，其中每棵二叉樹Ti中只有一個帶權為WiWiWi的根結點，其左右子樹均為空。

在F中選取兩棵根結點的權值最小的樹作為左右子樹構造一棵新的二叉樹，且置新的二叉樹的根結點的權值為其左、右子樹上根結點的權值之和。

在F中刪除這兩棵樹，同時將新得到的二叉樹加入FFF中。

重復上述2和3，直到FFF只喊一棵樹為止，這棵樹便是哈夫曼樹。

4.3 哈夫曼編碼

對于任意一棵二叉樹來說，把二叉樹上的所有分支都進行編號，將所有左分支都標記為0，所有右分支都標記為1。（左0右1）`那么對于樹上的任何一個結點，都可以根據從根結點到該結點的路徑唯一確定一個編號。對于哈夫曼樹上的葉子結點，根據從根結點到該葉子結點的路徑所確定的一個編號，就是該葉子結點的哈夫曼編碼。

Part5 總結

本節文章到此結束，在數據結構與算法中，樹與二叉樹這一章是比較重要且晦澀難懂的一章，本篇文章知識點較多，有些寫的也不是很全面。希望大家在閱讀的時候能多看看圖，多理解，結合圖像表達來理解理論知識。其重點是二叉樹的所有相關知識，在實際開發中，二叉樹的應用較為廣泛，希望我的文章對大家學習數據結構能有所幫助，希望大家都能有所收獲。