1. 概念
與線性結(jié)構(gòu)的“一對(duì)一”不同俭缓，樹是“一對(duì)多”的數(shù)據(jù)結(jié)構(gòu)锯厢。
樹是有限個(gè)結(jié)點(diǎn)n（n >= 0）的集合。
- n為0時(shí)稱為空樹叭爱；
- 不為0時(shí)撮躁，有且只有一個(gè)結(jié)點(diǎn)作為樹的根結(jié)點(diǎn)。
- n大于1時(shí)买雾，除根結(jié)點(diǎn)外的其他結(jié)點(diǎn)可以分為m（m > 0）個(gè)互不相交的有限集合T1...Tm把曼，每個(gè)子集合又是一棵樹杨帽，稱為子樹祝迂。
下圖即為一棵樹：
1.1 樹的“度”
每個(gè)結(jié)點(diǎn)包含的子結(jié)點(diǎn)的個(gè)數(shù)稱為結(jié)點(diǎn)的“度”（degree）睦尽。
度為0的結(jié)點(diǎn)為“葉子結(jié)點(diǎn)”或“終端結(jié)點(diǎn)”；度不為0的結(jié)點(diǎn)稱為“分支結(jié)點(diǎn)”或“非終端結(jié)點(diǎn)”型雳。
我們將一棵樹中所有子結(jié)點(diǎn)的“度”中的最大值稱作樹的度当凡。
示意圖中樹的度為3（結(jié)點(diǎn)D的度最大，是3）纠俭。
1.2 結(jié)點(diǎn)間的關(guān)系
結(jié)點(diǎn)的子樹中的根結(jié)點(diǎn)叫做該結(jié)點(diǎn)的孩子（Child）結(jié)點(diǎn)沿量；該結(jié)點(diǎn)稱為孩子的雙親（Parent）結(jié)點(diǎn)；同一雙親結(jié)點(diǎn)的子結(jié)點(diǎn)互為兄弟（Sibling）結(jié)點(diǎn)冤荆。
例如朴则，在示意圖中，結(jié)點(diǎn)D是B的孩子結(jié)點(diǎn)钓简，C是B的兄弟結(jié)點(diǎn)乌妒，A是B的雙親結(jié)點(diǎn)。
注：以下將雙親結(jié)點(diǎn)簡(jiǎn)稱為“父結(jié)點(diǎn)”外邓，孩子結(jié)點(diǎn)稱為“子結(jié)點(diǎn)”撤蚊。
1.3 樹的“深度”
從根結(jié)點(diǎn)開始，作為樹的第一層（Level）损话；其子結(jié)點(diǎn)作為第二層侦啸，以此類推。
樹的最大層數(shù)稱為該樹的“深度”（Depth）丧枪。
由于示意圖中的樹分為四層光涂，故其深度為4。其中拧烦，同一層的結(jié)點(diǎn)互為堂兄弟結(jié)點(diǎn)忘闻。如第三層的D、E和F結(jié)點(diǎn)屎篱。
1.4 其他概念
- 若樹從左至右為有序服赎，且各子結(jié)點(diǎn)的順序不可調(diào)換，則此樹可以稱為“有序樹”交播。
- 森林（Forest）是m（m >= 0）棵互不相交的樹的集合重虑。
1.5 結(jié)構(gòu)對(duì)比
與線性結(jié)構(gòu)的對(duì)比如下：
線性結(jié)構(gòu)：
- 頭元素：無前驅(qū)結(jié)點(diǎn)
- 尾元素：無后繼結(jié)點(diǎn)
- 中間元素：一個(gè)前驅(qū)結(jié)點(diǎn)，一個(gè)后繼結(jié)點(diǎn)
樹結(jié)構(gòu)：
- 根結(jié)點(diǎn)：無父結(jié)點(diǎn)秦士，唯一
- 葉子結(jié)點(diǎn)：無子結(jié)點(diǎn)缺厉，自身可以有多個(gè)
- 分支結(jié)點(diǎn)：有父結(jié)點(diǎn)，存在1個(gè)或多個(gè)子結(jié)點(diǎn)
2. 存儲(chǔ)結(jié)構(gòu)
利用順序和鏈?zhǔn)酱鎯?chǔ)方式，我們可以將樹的存儲(chǔ)方式簡(jiǎn)單介紹三種：
- 雙親表示法
- 孩子表示法
- 孩子兄弟表示法（二叉樹）
2.1 雙親表示法
雙親表示法使用順序存儲(chǔ)結(jié)構(gòu)提针，將所有結(jié)點(diǎn)依次存儲(chǔ)在連續(xù)的空間中命爬。
最簡(jiǎn)單的就是使用一個(gè)parent域來標(biāo)明自身的父結(jié)點(diǎn)。其結(jié)構(gòu)如下：
| data | parent |
|---|---|
| 數(shù)據(jù)域 | 父結(jié)點(diǎn)索引（數(shù)組下標(biāo)） |
以示意圖為例辐脖，使用雙親表示法可以表示為：
| 下標(biāo) | data | parent |
|---|---|---|
| 0 | A | -1 |
| 1 | B | 0 |
| 2 | C | 0 |
| 3 | D | 1 |
| 4 | E | 2 |
| 5 | F | 2 |
| 6 | G | 3 |
| 7 | H | 3 |
| 8 | I | 3 |
| 9 | J | 4 |
根據(jù)此存儲(chǔ)方式饲宛，可以直接查詢出每個(gè)子結(jié)點(diǎn)的父結(jié)點(diǎn)，其時(shí)間復(fù)雜度固定為O(1)嗜价。
可以根據(jù)需要艇抠，對(duì)結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)進(jìn)行擴(kuò)展：如添加指向第一個(gè)孩子結(jié)點(diǎn)的索引域firstChild；添加指向兄弟結(jié)點(diǎn)的索引域rightSib等久锥。這種方式可以適時(shí)通過擴(kuò)展并添加存儲(chǔ)空間來提高訪問效率家淤。
2.2 孩子表示法
由于每個(gè)結(jié)點(diǎn)的子結(jié)點(diǎn)個(gè)數(shù)不確定，可以通過鏈表來表示每個(gè)結(jié)點(diǎn)下的子樹瑟由。且由于我們?cè)谛枰獣r(shí)可以方便地遍歷樹中的所有結(jié)點(diǎn)絮重，可以考慮將所有結(jié)點(diǎn)保存在順序存儲(chǔ)結(jié)構(gòu)中。故孩子表示法的具體方法為：把每個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)排列起來歹苦，以單鏈表為存儲(chǔ)結(jié)構(gòu)青伤，則n個(gè)結(jié)點(diǎn)有n個(gè)孩子鏈表，如果該結(jié)點(diǎn)是葉子結(jié)點(diǎn)殴瘦，則此單鏈表為空表潮模。然后，將n個(gè)頭指針又組成一個(gè)線性表痴施，以順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)在一個(gè)一維數(shù)組中。
故示意圖中的樹究流，使用孩子表示法可以表示為：
其中結(jié)點(diǎn)分為兩種：
- 孩子鏈表中的孩子結(jié)點(diǎn)：
| child | next |
|---|---|
| 結(jié)點(diǎn)索引（順序數(shù)組的下標(biāo)） | 兄弟結(jié)點(diǎn)索引 |
- 表頭數(shù)組的表頭結(jié)點(diǎn)
| data | firstChild |
|---|---|
| 數(shù)據(jù)域 | 頭指針域（存儲(chǔ)對(duì)應(yīng)孩子鏈表的頭指針） |
對(duì)于此存儲(chǔ)結(jié)構(gòu)辣吃，要查找某結(jié)點(diǎn)的孩子結(jié)點(diǎn)，或查找某結(jié)點(diǎn)的兄弟結(jié)點(diǎn)芬探，只要查找對(duì)應(yīng)的孩子結(jié)點(diǎn)單鏈表即可神得。
2.3 孩子兄弟表示法
任意一棵樹，它的結(jié)點(diǎn)的第一個(gè)孩子如果存在就是唯一的偷仿，它的右兄弟如果存在也是唯一的哩簿。因此此節(jié)點(diǎn)包括兩個(gè)指針域，分別指向該結(jié)點(diǎn)的第一個(gè)孩子結(jié)點(diǎn)和此結(jié)點(diǎn)的右兄弟結(jié)點(diǎn)酝静。
| data | firstChild | rightSib |
|---|---|---|
| 數(shù)據(jù)域 | 第一個(gè)孩子結(jié)點(diǎn)的存儲(chǔ)地址 | 右兄弟結(jié)點(diǎn)的存儲(chǔ)地址 |
故示意圖中的樹节榜，使用孩子兄弟表示法可以表示為：
使用此方式，可以很方便地查找某結(jié)點(diǎn)的第幾個(gè)子結(jié)點(diǎn)：只要找到該結(jié)點(diǎn)的第一個(gè)孩子結(jié)點(diǎn)后别智，依次查找其兄弟結(jié)點(diǎn)即可宗苍。
通過此種表示方法，我們可以發(fā)現(xiàn)，標(biāo)準(zhǔn)的樹被轉(zhuǎn)換成了二叉樹表示（每個(gè)結(jié)點(diǎn)最多只有兩個(gè)子結(jié)點(diǎn)）讳窟。
3. 二叉樹
3.1 定義
- 每個(gè)結(jié)點(diǎn)最多有兩棵子樹（子結(jié)點(diǎn)）让歼，故二叉樹的度不超過2。
- 左右子樹有序丽啡，不能顛倒谋右。
- 結(jié)點(diǎn)若只有一棵子樹，也要區(qū)分是左還是右子樹补箍。
如下圖改执，二者是兩棵不同的二叉樹：
3.2 存儲(chǔ)結(jié)構(gòu)
3.2.1 順序存儲(chǔ)結(jié)構(gòu)
二叉樹的順序存儲(chǔ)結(jié)構(gòu)一般只適用于完全二叉樹**。
完全二叉樹：
- 葉子結(jié)點(diǎn)只出現(xiàn)在二叉樹的最后兩層
- 最后一層的葉子結(jié)點(diǎn)都是左結(jié)點(diǎn)馏予；倒數(shù)第二層的葉子結(jié)點(diǎn)都是右結(jié)點(diǎn)
- 滿二叉樹（只有最后一層存在天梧，且全都是葉子結(jié)點(diǎn)的二叉樹）屬于完全二叉樹
如圖所示，用一維數(shù)組存儲(chǔ)二叉樹的所有結(jié)點(diǎn)霞丧，通過數(shù)組下標(biāo)來提現(xiàn)二叉樹中結(jié)點(diǎn)間的關(guān)系呢岗。
但是，當(dāng)二叉樹中有過多空余結(jié)點(diǎn)（如圖中的黃色不存在結(jié)點(diǎn)）時(shí)會(huì)導(dǎo)致空間浪費(fèi)蛹尝，故一般只使用順序結(jié)構(gòu)存儲(chǔ)完全二叉樹后豫。
3.2.2 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)--二叉鏈表
二叉鏈表：每個(gè)數(shù)據(jù)節(jié)點(diǎn)包含本身的數(shù)據(jù)域和兩個(gè)指針域，分別指向兩個(gè)可能的孩子結(jié)點(diǎn)突那，這種結(jié)點(diǎn)組成的鏈表稱為二叉鏈表挫酿。
結(jié)點(diǎn)結(jié)構(gòu)如下：
| lchild | data | rchild |
|---|---|---|
| 左孩子結(jié)點(diǎn)的存儲(chǔ)地址 | 數(shù)據(jù)域 | 右孩子結(jié)點(diǎn)的存儲(chǔ)地址 |
/** 二叉鏈表的結(jié)點(diǎn)結(jié)構(gòu)體 */
typedef struct BiTNode {
TElemType data; // 數(shù)據(jù)域
struct BiTNode *lchild; // 左孩子結(jié)點(diǎn)指針
struct BiTNode *rchild; // 右孩子結(jié)點(diǎn)指針
} BiTNode, *BiTree;
下圖為二叉鏈表的表述示意圖：
3.3 二叉樹的遍歷
二叉樹的遍歷（traversing binary tree）是指從根結(jié)點(diǎn)出發(fā)，按照某種次序依次訪問二叉樹中的所有結(jié)點(diǎn)愕难，使得每個(gè)結(jié)點(diǎn)被訪問一次且僅被訪問一次早龟。
若以從左到右方向限定，主要的遍歷方式分為以下四種：
- 前序遍歷
- 中序遍歷
- 后序遍歷
- 層序遍歷
與定義二叉樹的方式一樣猫缭，其遍歷也是以遞歸的方式進(jìn)行葱弟。
3.3.1 前序遍歷
遍歷方式：先訪問根節(jié)點(diǎn)，然后前序遍歷左子樹猜丹，再前序遍歷右子樹芝加。
void PreOrderTraverse(BiTree T) {
if (T == NULL) {
return;
}
// 訪問根節(jié)點(diǎn)
printf("%c", T->data);
// 遍歷左子樹
PreOrderTraverse(T->lchild);
// 遍歷右子樹
PreOrderTraverse(T->rchild);
}
3.3.2 中序遍歷
遍歷方式：先中序遍歷根節(jié)點(diǎn)的左子樹，然后是根節(jié)點(diǎn)射窒，再中序遍歷右子樹藏杖。
void InOrderTraverse(BiTree T) {
if (T == NULL) {
return;
}
// 遍歷左子樹
InOrderTraverse(T->lchild);
// 訪問根節(jié)點(diǎn)
printf("%c", T->data);
// 遍歷右子樹
InOrderTraverse(T->rchild);
}
3.3.3 后續(xù)遍歷
遍歷方式：從左到右，先葉子后結(jié)點(diǎn)脉顿，全部訪問完左右子樹后蝌麸，最后訪問根結(jié)點(diǎn)。
void PostOrderTraverse(BiTree T) {
if (T == NULL) {
return;
}
// 遍歷左子樹
PostOrderTraverse(T->lchild);
// 遍歷右子樹
PostOrderTraverse(T->rchild);
// 訪問根節(jié)點(diǎn)
printf("%c", T->data);
}
3.4 二叉樹的創(chuàng)建
這里以前序方式創(chuàng)建弊予。與前序遍歷相同祥楣，創(chuàng)建時(shí)按照前序遍歷的方式依次遞歸輸入結(jié)點(diǎn)數(shù)據(jù)即可：
/** 創(chuàng)建二叉樹【前序遍歷法創(chuàng)建：根--左--右】 */
void CreateBiTree(BiTree *T) {
TElemType ch;
scanf("%c", &ch);
if (ch == '#') {
*T = NULL; // 代表此結(jié)點(diǎn)位置無數(shù)據(jù)（數(shù)據(jù)為空）
return;
} else {
// 分配空間，創(chuàng)建新結(jié)點(diǎn)
*T = (BiTree)malloc(sizeof(BiTNode));
// 內(nèi)存分配失敗，退出
if (!*T) {
exit(OVERFLOW);
}
// 前序遍歷方式賦值
// 1. 賦值根節(jié)點(diǎn)
(*T)->data = ch;
// 2. 左孩子結(jié)點(diǎn)遞歸
CreateBiTree(&((*T)->lchild));
// 3. 右孩子結(jié)點(diǎn)遞歸
CreateBiTree(&((*T)->rchild));
}
}
如下圖所示误褪，依照代碼责鳍，先將給定的二叉樹轉(zhuǎn)化為擴(kuò)展二叉樹**。
擴(kuò)展二叉樹：
將給定的二叉樹的每個(gè)結(jié)點(diǎn)的空指針設(shè)置一個(gè)虛擬結(jié)點(diǎn)兽间，并指定一個(gè)特殊值（這里定義為“#”）历葛。
二叉樹的創(chuàng)建與三種遍歷方式，可查看此示例：項(xiàng)目地址
3.5 線索二叉樹
3.5.1 線索化過程
此二叉鏈表雖然功能強(qiáng)大嘀略，但弱點(diǎn)顯而易見：就是每次只能通過指定方式的遍歷恤溶，才可以確定每個(gè)結(jié)點(diǎn)的前趨結(jié)點(diǎn)和后綴結(jié)點(diǎn)。而且我們可以發(fā)現(xiàn)帜羊，在下面的二叉鏈表示意圖中咒程，有n+1（即2n個(gè)總lchild和rchild指針個(gè)數(shù) 與 n-1個(gè)連線 的差）個(gè)空余指針域（存儲(chǔ)的是“^”），隨著二叉樹的增長(zhǎng)讼育，浪費(fèi)的空間會(huì)越來越多帐姻。
因此，我們可以使用這些空余空間來保存每個(gè)結(jié)點(diǎn)的前趨和后繼結(jié)點(diǎn)的信息奶段，以解決上述問題饥瓷。而解決此問題的過程，叫做線索化痹籍，線索化后的二叉鏈表叫做線索鏈表呢铆，對(duì)應(yīng)的樹叫做線索二叉樹。
具體做法是：在使用某種順序遍歷每個(gè)結(jié)點(diǎn)時(shí)蹲缠，若沒有左孩子結(jié)點(diǎn)棺克，其lchild保存的是前趨結(jié)點(diǎn)的指針；若沒有右孩子結(jié)點(diǎn)线定，其rchild保存的是后繼結(jié)點(diǎn)的指針逆航。
如上圖中的二叉樹，其中序遍歷后的結(jié)果為HDIBJEAFCG渔肩，根據(jù)遍歷結(jié)果對(duì)該二叉鏈表進(jìn)行線索化的結(jié)果如下：
可以看到，通過線索化拇惋，不僅解決了空間浪費(fèi)問題周偎，還解決了前趨和后繼結(jié)點(diǎn)的記錄問題，提高了訪問效率撑帖。
3.5.2 區(qū)分結(jié)點(diǎn)類型
此時(shí)線索二叉樹還存在一個(gè)問題：我們無法區(qū)分lchild指向的結(jié)點(diǎn)是前趨結(jié)點(diǎn)還是左孩子節(jié)點(diǎn)蓉坎，對(duì)于rchild也是如此。
此時(shí)胡嘿，需要針對(duì)每個(gè)指針域分別設(shè)置一個(gè)布爾類型的數(shù)據(jù)域蛉艾，在線索化的過程中，根據(jù)實(shí)際情況進(jìn)行區(qū)分（是前趨或后繼結(jié)點(diǎn)時(shí)為1，是孩子結(jié)點(diǎn)時(shí)為0）勿侯。
結(jié)點(diǎn)結(jié)構(gòu)如下：
| 左孩子結(jié)點(diǎn)地址 | 左標(biāo)識(shí)符 | 數(shù)據(jù)域 | 右標(biāo)識(shí)符 | 右孩子結(jié)點(diǎn)地址 |
|---|---|---|---|---|
| lchild | ltag | data | rtag | rchild |
對(duì)應(yīng)實(shí)現(xiàn)如下：
/** 枚舉變量拓瞪，用于標(biāo)識(shí)符賦值 */
typedef enum {
/** 是孩子結(jié)點(diǎn) */
Link,
/** 是前趨或后綴結(jié)點(diǎn) */
Thread
} PointerTag;
/** 線索二叉樹結(jié)點(diǎn)結(jié)構(gòu) */
typedef struct BiThrNode {
/** 數(shù)據(jù)域 */
TElemType data;
/** 左結(jié)點(diǎn)指針 */
struct BiThrNode *lchild;
/** 左結(jié)點(diǎn)標(biāo)識(shí)符 */
PointerTag LTag;
/** 右結(jié)點(diǎn)指針 */
struct BiThrNode *rchild;
/** 右結(jié)點(diǎn)標(biāo)識(shí)符 */
PointerTag RTag;
} BiThrNode, *BiThrTree; // 定義為線索二叉樹結(jié)點(diǎn)及線索二叉樹指針
添加結(jié)點(diǎn)類型區(qū)分后的線索二叉樹如下：
這樣在訪問指定節(jié)點(diǎn)時(shí)，根據(jù)ltag和rtag的值即可區(qū)分相鄰結(jié)點(diǎn)是前趨后繼結(jié)點(diǎn)或是孩子結(jié)點(diǎn)了助琐。
線索化過程的代碼如下（這里使用中序遍歷方式）：
/** 當(dāng)前訪問節(jié)點(diǎn) */
BiThrTree currentP = NULL;
/** 中序遍歷線索化 */
void InThreading(BiThrTree p) {
if (!p) {
// 結(jié)點(diǎn)不存在祭埂，返回
return;
}
if (!p->lchild && !p->rchild) {
// 左右子結(jié)點(diǎn)均不存在，即是葉子結(jié)點(diǎn)【防止最后一個(gè)結(jié)點(diǎn)無修改RTag】
p->LTag = Thread;
p->RTag = Thread;
}
// 遞歸線索化左結(jié)點(diǎn)
InThreading(p->lchild);
// 自身數(shù)據(jù)線索化（由于是中序遍歷【左--中--右】兵钮，此時(shí)右結(jié)點(diǎn)還沒有訪問到蛆橡，故只處理當(dāng)前和前一個(gè)結(jié)點(diǎn)即可）
if (!(p->lchild)) {
// 左結(jié)點(diǎn)為空，即沒有左孩子掘譬，故當(dāng)前指向前趨結(jié)點(diǎn)
p->LTag = Thread;
p->lchild = currentP;
} else {
// 包含左孩子
p->LTag = Link;
}
if (currentP) {
if (!(currentP->rchild)) {
// 前一個(gè)結(jié)點(diǎn)的右結(jié)點(diǎn)指針為空泰演，即沒有右孩子，故指向后繼結(jié)點(diǎn)（當(dāng)前結(jié)點(diǎn)）
currentP->RTag = Thread;
currentP->rchild = p;
} else {
// 包含右孩子
currentP->RTag = Link;
}
}
// 記錄當(dāng)前結(jié)點(diǎn)
currentP = p;
// 遞歸線索化右結(jié)點(diǎn)
InThreading(p->rchild);
}
由上圖即可看出葱轩，如果在二叉樹的根結(jié)點(diǎn)之前再插入一個(gè)頭結(jié)點(diǎn)睦焕，此時(shí)的線索二叉樹實(shí)際上就是一個(gè)雙向鏈表結(jié)構(gòu)。其結(jié)構(gòu)示意圖如下：
插入頭結(jié)點(diǎn)的簡(jiǎn)單方法如下：
/** 向線索二叉樹中插入頭結(jié)點(diǎn) */
BiThrTree insertHeadNodeToBiThrTree(BiThrTree biTree) {
if (biTree == NULL) {
return NULL;
}
// 創(chuàng)建頭節(jié)點(diǎn)
BiThrTree headNode = (BiThrTree)malloc(sizeof(BiThrNode));
// 左孩子指向線索二叉樹的根結(jié)點(diǎn)
headNode->lchild = biTree;
headNode->LTag = Link;
// 右孩子指向中序遍歷的最后一個(gè)結(jié)點(diǎn)
BiThrTree inOrderTailNode = biTree;
while (inOrderTailNode->RTag == Link) {
inOrderTailNode = inOrderTailNode->rchild;
}
// 此時(shí)inOrderTailNode即為最后一個(gè)結(jié)點(diǎn)
headNode->rchild = inOrderTailNode;
headNode->RTag = Thread; // 并不是右孩子
// targetNode的后繼結(jié)點(diǎn)指向頭結(jié)點(diǎn)
inOrderTailNode->rchild = headNode;
// 中序遍歷的第一個(gè)結(jié)點(diǎn)的前趨結(jié)點(diǎn)指向頭結(jié)點(diǎn)
BiThrTree inOrderFirstNode = biTree;
while (inOrderFirstNode->LTag == Link) {
inOrderFirstNode = inOrderFirstNode->lchild;
}
// 此時(shí)inOrderFirstNode即為第一個(gè)結(jié)點(diǎn)
inOrderFirstNode->lchild = headNode;
return headNode;
}
最終酿箭，通過訪問雙向鏈表的方式复亏，中序遍歷輸出此二叉樹的方式如下：
/** 中序遍歷【掃描二叉鏈表方式】 */
void InOrderTraverse_Thr(BiThrTree T) {
// 中序遍歷，即從頭結(jié)點(diǎn)開始掃描缭嫡，
// 1. 首先找到最左邊的結(jié)點(diǎn)（沒有左孩子的）缔御，
// 2. 然后找其后繼結(jié)點(diǎn)（子樹的根），
// 3. 最后是其右結(jié)點(diǎn)（右孩子或后繼）
// 直到掃描到的結(jié)點(diǎn)是頭結(jié)點(diǎn)妇蛀，結(jié)束
// 指向根結(jié)點(diǎn)（從根結(jié)點(diǎn)開始）
BiThrTree currentNode = T->lchild;
// 遍歷結(jié)束時(shí)耕突，指向頭結(jié)點(diǎn)
while (currentNode != T) {
// 1. 找到當(dāng)前子樹最左邊的結(jié)點(diǎn)（沒有左孩子的）
while (currentNode->LTag == Link) {
// 有左孩子，繼續(xù)查找
currentNode = currentNode->lchild;
}
// 找到了最左邊的結(jié)點(diǎn)评架，輸出
printf("%hhd ", currentNode->data);
// 2. 一直向后找到所有后繼結(jié)點(diǎn)（即對(duì)應(yīng)子樹的根）
while (currentNode->RTag == Thread && currentNode->rchild != T) {
currentNode = currentNode->rchild;
// 找到了后繼結(jié)點(diǎn)眷茁，輸出
printf("%hhd ", currentNode->data);
}
// 3. 指向右結(jié)點(diǎn)（下一個(gè)結(jié)點(diǎn)，不管結(jié)點(diǎn)類型纵诞，準(zhǔn)備下次循環(huán)）
currentNode = currentNode->rchild;
}
}
線索化及遍歷的完整過程上祈，可查看此示例：項(xiàng)目地址
3.6 樹、森林轉(zhuǎn)換為二叉樹
由于二叉樹的結(jié)構(gòu)穩(wěn)定（每個(gè)結(jié)點(diǎn)只有左右兩個(gè)孩子）浙芙，其性質(zhì)也容易研究登刺，故在某些情況下，將普通的樹甚至森林轉(zhuǎn)換為二叉樹即可對(duì)它們進(jìn)行問題的研究（如遍歷等）嗡呼。
3.6.1 樹 => 二叉樹
轉(zhuǎn)換規(guī)則：
- 在兄弟結(jié)點(diǎn)與其左方的結(jié)點(diǎn)之間添加連接線纸俭。
- 在結(jié)點(diǎn)的所有子孩子中，除了左邊第一個(gè)孩子結(jié)點(diǎn)外南窗，其他所有兄弟孩子結(jié)點(diǎn)與父結(jié)點(diǎn)間的連線去除揍很。
- 調(diào)整層次郎楼，結(jié)點(diǎn)的第一個(gè)子孩子作為二叉的左孩子，兄弟孩子作為“前一個(gè)”結(jié)點(diǎn)的右孩子窒悔。
示例：
轉(zhuǎn)換過程：
3.6.2 森林 => 二叉樹
可以將森林中的每一棵樹看做是兄弟呜袁，利用兄弟結(jié)點(diǎn)的合并方式（作為前一個(gè)結(jié)點(diǎn)的右孩子）進(jìn)行合并，最終合成一棵二叉樹：
- 把每一棵樹轉(zhuǎn)換為二叉樹蛉迹。
- 依次將后一棵樹的根結(jié)點(diǎn)作為前一棵樹的根結(jié)點(diǎn)的右孩子傅寡。連線完成后，即可得到合成的二叉樹北救。
示例：
轉(zhuǎn)換過程：
3.7 赫夫曼樹及霍夫曼編碼
3.7.1 概念介紹
赫夫曼樹是在二叉樹的基礎(chǔ)上設(shè)計(jì)而來荐操。赫夫曼樹的每個(gè)葉子結(jié)點(diǎn)都包含對(duì)應(yīng)的權(quán)值（Weight）。兩個(gè)結(jié)點(diǎn)之間經(jīng)過的所有分支叫做路徑珍策，路徑上分支的個(gè)數(shù)叫做路徑長(zhǎng)度托启。樹的路徑長(zhǎng)度就是從根結(jié)點(diǎn)到每個(gè)葉子結(jié)點(diǎn)的路徑長(zhǎng)度的總和**。
圖中的二叉樹的路徑長(zhǎng)度為（以A-E的順序）：3 + 3 + 2 + 2 + 2 = 12攘宙。
霍夫曼樹需要引入權(quán)的概念屯耸，故我們得到了帶權(quán)路徑的算法：
結(jié)點(diǎn)的帶權(quán)路徑 = 結(jié)點(diǎn)從根到自身的路徑長(zhǎng)度 * 自身權(quán)重
因此樹的帶權(quán)路徑長(zhǎng)度即為所有葉子結(jié)點(diǎn)帶權(quán)路徑的總和，稱作WPL蹭劈。
圖中二叉樹的WPL為：3 * 5 + 3 * 15 + 2 * 40 + 2 * 30 + 2 * 10 = 220疗绣。
在帶有權(quán)重的一組葉子結(jié)點(diǎn)所組成的二叉樹中，WPL最小的可稱作霍夫曼樹铺韧。
3.7.2 生成方法
- 將所有結(jié)點(diǎn)按照權(quán)值升序排列多矮，生成有序樹集合（每棵樹即為單獨(dú)的葉子結(jié)點(diǎn)）。
- 取前兩棵樹（權(quán)值最泄颉）作為左右子樹塔逃，生成新二叉樹，其根結(jié)點(diǎn)的權(quán)值為原兩樹權(quán)值之和料仗。
- 在集合中使用新的二叉樹替換原始的兩棵樹并重新排序湾盗。
- 重復(fù)步驟2和3，直到序列只剩下一棵樹為止立轧，此樹即為霍夫曼樹格粪。
示例：
| 結(jié)點(diǎn) | A | B | C | D | E |
|---|---|---|---|---|---|
| 權(quán)值 | 5 | 15 | 40 | 30 | 10 |
3.7.3 霍夫曼編碼
將霍夫曼樹中所有結(jié)點(diǎn)（包括合成結(jié)點(diǎn)）的權(quán)值改為0和1（左分支權(quán)值為0，右分支權(quán)值為1）氛改，這樣從根結(jié)點(diǎn)到指定葉子結(jié)點(diǎn)所生成的0和1序列即為霍夫曼編碼匀借。
上面的霍夫曼樹轉(zhuǎn)換后的結(jié)果為：
因此，圖中每個(gè)字符所生成的霍夫曼編碼如下：
| 字符 | A | B | C | D | E |
|---|---|---|---|---|---|
| 霍夫曼編碼 | 1000 | 101 | 0 | 11 | 1001 |
霍夫曼編碼可以用來壓縮數(shù)據(jù)平窘，進(jìn)而提高了傳輸效率。
假設(shè)傳輸”BADBEC“這個(gè)字符串凳怨，使用傳統(tǒng)的等長(zhǎng)編碼瑰艘，可能會(huì)使用如下方式：
| 字符 | A | B | C | D | E |
|---|---|---|---|---|---|
| 等長(zhǎng)編碼 | 100 | 101 | 010 | 011 | 110 |
故在此方式下是鬼，編碼后的數(shù)據(jù)為”101100011101110010“，長(zhǎng)度為18位紫新；而使用霍夫曼編碼均蜜，編碼后的數(shù)據(jù)為”1011000101101110“，長(zhǎng)度僅為16位芒率，故數(shù)據(jù)得到了壓縮囤耳。且隨著編碼字符的增多，霍夫曼編碼的數(shù)據(jù)優(yōu)勢(shì)會(huì)越來越大偶芍。
像霍夫曼編碼這樣長(zhǎng)短不一的編碼方式充择，由于容易混淆，故必須設(shè)計(jì)成任一字符的編碼都不是其他字符編碼的前綴（否則解碼時(shí)無法區(qū)分）匪蟀，這種編碼方式叫做前綴編碼椎麦。
