樹
- 樹的基本内容
-
- 樹的定義
- 樹的基本術語
- 樹的存儲結構
-
- 順序存儲結構
- 鍊式存儲結構
- 二叉樹
-
- 二叉樹的定義
- 二叉樹的主要性質
- 二叉樹的存儲結構
-
- 順序存儲結構
- 鍊式存儲結構
- 二叉樹的周遊算法
-
- 先序周遊
- 中序周遊
- 後序周遊
- 層次周遊
- 二叉樹周遊算法的改進
-
- 二叉樹深度優先周遊算法的非遞歸實作
-
- 先序周遊非遞歸算法
- 中序周遊非遞歸算法
- 後序周遊非遞歸算法
- 線索二叉樹
- 樹和森林與二叉樹的互相轉換
-
- 樹轉換成二叉樹
- 二叉樹轉化為樹
- 森林轉換為二叉樹
- 二叉樹轉換為森林
- 樹和森林的周遊
-
- 樹的周遊
- 森林的周遊
- 赫夫曼樹和赫夫曼編碼
-
- 與赫夫曼樹有關的概念
- 赫夫曼樹的構造原理
- 赫夫曼編碼
- 擴充：C++文法—引用
樹的基本内容
樹的定義
樹是一種非線性的資料結構，要了解樹的概念及其術語的含義，用一個例子說明最好，下圖是一個樹，它是若幹結點的集合，是由唯一的根（結點A）和若幹棵互不相交的子樹組成的，其中每一棵子樹又是一棵樹，也是由唯一的根結點和若幹棵互不相交的子樹組成的，要注意的是，樹的結點數目可以為0，當為0時，這棵樹稱為空樹，這是一種特殊情況。
樹的基本術語
結點：A、B、C等都是結點，結點不僅包含資料元素，而且包含指向子樹的分支。例如：A結點不僅包含資料元素A，而且還包含3個指向子樹的指針。
結點的度：結點擁有的子樹個數或者分支的個數。例如：A結點有3棵子樹，是以A結點的度為3。
樹的度：書中各結點度的最大值。如例子中的結點度最大為3，最小為0，是以樹的度為3。
葉子結點：又叫作終端結點，指度為0的結點，如F、G、I、J、K、L、M結點都是葉子結點。
非終端結點：又叫作分支結點，指度不為0的結點，如A、B、C、D、E、H結點都是非終端結點。除了根結點之外的非終端結點，也叫做内部結點。
孩子：結點的子樹的根，如A結點的孩子為B、C、D。
雙親：與孩子的定義對應，如B、C、D結點的雙親都是A。
兄弟：同一雙親的孩子之間互為兄弟。如B、C、D互為兄弟。
祖先：從根到某結點的路徑上的所有結點，都是這個結點的祖先。如K的祖先是A、B、E。因為從A到K的路徑為A—B—E—K。
子孫：以某結點為根的子樹中的所有結點，都是該節點的子孫，如D的子孫是H、I、J、M。
層次：從根開始，根為第一層，根的孩子為第二層，根的孩子的孩子為第三層。
樹的高度：樹中結點的最大層次。如上例中樹共4層，是以高度為4。
結點的深度和高度：
- 結點的深度是從根節點到該結點路徑上的結點個數。
- 從某結點往下走可能到達多個葉子結點，對應了多條通往這些葉子結點的路徑，其中最長的那條路徑上的結點個數即為該結點在樹中的高度，如結點D的高度為3，就是從D到M的路徑上的結點個數。
- 根結點的高度為樹的高度，如結點A，其高度為4，是從A到K這條路徑上結點的個數，也是整棵樹的高度。
堂兄弟：雙親在同一層的結點互為堂兄弟。如G和H互為堂兄弟，因為G的雙親是C，H是雙親是D，C和D在同一層上。
有序樹：樹中結點的子樹從左到右是有次序的，不能交換，這樣的樹叫做有序樹。
無序樹：樹中結點的子樹沒有順序，可以任意交換，這樣的樹叫做無序樹。
豐滿樹：豐滿樹即理想平衡樹，要求除了最底層外，其它層都是滿的。
森林：若幹棵互不相交的樹的集合，例子中如果把根A去掉，剩下的3棵互不相交，它們組成一個森林。
樹的存儲結構
順序存儲結構
樹的順序存儲結構最簡單直覺的是雙親存儲結構，用一維數組即可實作。下面用一個例子來說明一個數組如何表示一個樹。
| 結點元素 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| 雙親結點 | -1 | 1 | 1 | 1 | 3 | 3 | 3 |
用數組下标表示樹中的結點，數組元素的内容表示該結點的雙親節點，這樣有了結點（下标）以及結點之間的關系（内容），就可以表示一棵樹。
鍊式存儲結構
- 孩子存儲結構：需要用到圖的鄰接表存儲結構，樹就是一種特殊的圖。把圖中的多對多關系删減為一對多關系即變為樹。
- 孩子兄弟存儲結構
二叉樹
二叉樹的定義
将一般的樹加上如下兩個限制條件就得到了二叉樹。
- 每個結點最多隻有兩個子樹，即二叉樹中結點的度隻能為0、1、2。
- 子樹有左右順序之分，不能颠倒。
根據二叉樹的定義，可以知道二叉樹共有5種基本的形态.
- 空二叉樹
- 隻有根結點
- 隻有左子樹
- 隻有右子樹
- 左右子樹都有
在一棵二叉樹中，如果所有的分支結點都有左孩子和右孩子結點，并且葉子結點都集中在二叉樹的最下一層，則這樣的二叉樹為滿二叉樹。
對滿二叉樹進行編号，約定從1開始，從上到下，自左到右進行，如果對一棵深度為k、有n個結點的二叉樹進行編号後，各結點的編号與深度為k的滿二叉樹中相同位置上的結點的編号均相同，那麼這棵二叉樹就是一個完全二叉樹。
在下圖中，結點F用虛線畫出。如果F存在于下圖的二叉樹結點，則F的編号為6，與上圖的滿二叉樹同一位置上的結點G的編号7不同，此時就不是完全二叉樹，如果F存在下圖的二叉樹中，此時就是完全二叉樹。
空表示沒有該結點，為了将F畫到右邊，才加這個。
二叉樹的主要性質
性質1：非空二叉樹上葉子結點數等于雙分支結點數加1。
性質2：二叉樹的第i層上最多有 2 i − 1 2^{i-1} 2i−1個結點。
性質3：高度為k的二叉樹最多有 2 k − 1 2^k-1 2k−1個結點。
性質4：有n個結點的完全二叉樹，對各結點從上到下，從左到右依次編号，則結點有如下關系，若i為某結點a的編号，則
- 如果 i ≠ 1 i \neq 1 i=1，則a雙親結點的編号為 ⌊ i / 2 ⌋ \lfloor i/2 \rfloor ⌊i/2⌋。
- 如果 2 i ≤ n 2i \leq n 2i≤n，則a左孩子的編号為 2 i 2i 2i；如果 2 i > n 2i>n 2i>n，則a無左孩子。
- 如果 2 i + 1 ≤ n 2i+1 \leq n 2i+1≤n，則a右孩子的編号為 2 i + 1 2i+1 2i+1；如果 2 i + 1 > n 2i+1>n 2i+1>n，則a無右孩子。
性質5：函數
Catalan()
：給定n個結點，能構成
h(n)
種不同的二叉樹。 h ( n ) = C 2 n n n + 1 h(n)=\frac{C_{2n}^{n}}{n+1} h(n)=n+1C2nn。
性質6：具有n個結點的完全二叉樹的高度為 ⌊ l o g 2 n ⌋ + 1 \lfloor log_2n \rfloor +1 ⌊log2n⌋+1。
二叉樹的存儲結構
順序存儲結構
順序存儲結構是用一個數組來存儲一棵二叉樹，這種存儲方式最适合于完全二叉樹，用于存儲一般二叉樹會浪費大量的存儲空間。将完全二叉樹中的結點值按編号依次存入一個一維數組中，即完成了一棵二叉樹的順序存儲。例如：知道了頂點A的下标為1，要得到A的左孩子結點隻需通路數組中
[1*2]
即可。
鍊式存儲結構
typedef struct BTNode{
char data;
struct BTNode* lchild;
struct BTNode* rchild;
}BTNode;
二叉樹的周遊算法
先序周遊
先序周遊的操作過程如下：如果二叉樹為空樹，則什麼都不做，否則：
- 通路根結點
- 先序周遊左子樹
- 先序周遊右子樹
void preprder(BTNode* p){
if(p!= nullptr){
printf("%c",p->data);
preprder(p->lchild);
preprder(p->rchild);
}
}
中序周遊
中序周遊的操作過程如下：如果二叉樹為空樹，則什麼都不做，否則：
- 中序周遊左子樹
- 通路根結點
- 中序周遊右子樹
void inorder(BTNode* p){
if(p!= nullptr){
inorder(p->lchild);
printf("%c",p->data);
inorder(p->rchild);
}
}
後序周遊
後序周遊的操作過程如下：如果二叉樹為空樹，則什麼都不做，否則：
- 後序周遊左子樹
- 後序周遊右子樹
- 通路根結點
void postorder(BTNode* p){
if(p!= nullptr){
postorder(p->lchild);
postorder(p->rchild);
printf("%c",p->data);
}
}
例：表達式 a + ( b + c ) ∗ ( d / e ) a+(b+c)*(d/e) a+(b+c)∗(d/e)存儲在下圖的一棵以二叉連結清單為存儲結構的二叉樹中（二叉樹結點為char類型），編寫程式求出該值。（表達式中的操作數是一位的整數）
左子樹為表達式A，右子樹為表達式B，先求左子樹所表示的表達式的值，然後求右子樹所表示的表達式的值，最後将兩個式子想乘即可。這正好對應先周遊左子樹，再周遊右子樹，最後通路根結點的後序周遊，是以采用後序周遊解決此問題。
int comp(BTNode *p){
int A,B;
if(p!= nullptr){
if(p->lchild!= nullptr && p->rchild!= nullptr){
A = comp(p->lchild);
B = comp(p->rchild);
return op(A,p->data,B);
} else{
return p->data - '0';
}
}else{
return 0;
}
}
int op(int a,char Op,int b){
if(Op == '+'){
return a+b;
}
if(Op == '-'){
return a-b;
}
if(Op == '*'){
return a*b;
}
if(Op == '/'){
if(b == 0){
printf("Error");
return 0;
}else{
return a/b;
}
}
return 0;
}
例：寫一個算法求一棵二叉樹的深度，二叉樹以二叉連結清單為存儲方式。
分析：假如已知一棵二叉樹的左子樹和右子樹的深度，如何計算整棵樹的深度？這是問題的關鍵。如果有一個二叉樹，左子樹深度為LD，右子樹深度為RD，則整棵樹的深度就是
max{LD,RD}+1
，即左子樹和右子樹深度的最大值加1，是以這個求深度的過程實際上就是先求左子樹深度，再求右子樹深度，然後傳回兩者之中的最大值加1就是整棵樹的深度。這正對應于先周遊左子樹（得到左子樹的深度LD），再周遊右子樹（得到右子樹的深度RD），最後通路根結點（得到整棵樹的深度）。
int getDepth(BTNode *p){
int LD,RD;
if(p == nullptr){
return 0; //如果樹是空樹，則傳回0
}else{
LD = getDepth(p->lchild);
RD = getDepth(p->rchild);
return (LD > RD ? LD:RD) + 1;
}
}
例：在一棵以二叉連結清單為存儲結構的二叉樹中，查找data域值等于key的結點是否存在（找到任何一個滿足要求的結點），如果存在，則将q指向該結點，否則q指派為NULL，假設data為char型。
分析：因為題中二叉樹各個結點data域的值沒有任何規律，是以要判斷是否存在data域值等于key的結點，必須按照某種方式把所有結點通路一遍，逐一進行判斷其值是否為key。
void search(BTNode *p,BTNode *&q,char key){
if(p!= nullptr){
if(p->data == key){
q = p;
}else{
search(p->lchild,q,key);
search(p->rchild,q,key);
}
}
}
例：假設二叉樹采用二叉連結清單存儲結構存儲，編寫一個程式，輸出先序周遊序列中第k個結點的值，假設k不大于總的結點數（結點data類型為char）。
分析：題目要求輸出先序周遊序列中的第k個結點的值，隻需要修改先序周遊的模闆即可。
int m = 0; //必須定義為全局變量,記錄數量
void trave(BTNode* p,int k){
if(p!= nullptr){
++m;
if(k==m){
printf("%c",p->data);
return;
}
trave(p->lchild,k);
trave(p->rchild,k);
}
}
層次周遊
按照從左向右的順序，依次對每層的樹結點進行周遊。
要進行層次周遊，需要建立一個循環隊列。先将二叉樹頭結點入隊列，然後出隊列，通路該結點，如果它有左子樹，則将左子樹的根結點入隊，如果它有右子樹，則将右子樹的根結點入隊。然後出隊列，對出隊結點通路，如此反複，直到隊列為止。
void level(BTNode *p){
int front,rear;
BTNode *que[maxSize];
front = rear = 0;
BTNode *q;
if(p!= nullptr){
rear = (rear+1)%maxSize;
que[rear] = p; //根結點入隊
while(front != rear){ //當隊列不空時循環
front = (front+1)%maxSize;
q = que[front]; //隊頭結點出隊
printf("%c",q->data); //通路隊頭結點
if(q->lchild != nullptr){ //如果左子樹不空，則左子樹根結點入隊。
rear = (rear+1)%maxSize;
que[rear] = q->lchild;
}
if(q->rchild != nullptr){ //如果右子樹不空，則右樹根結點入隊。
rear = (rear+1)%maxSize;
que[rear] = q->rchild;
}
}
}
}
例：假設二叉樹采用二叉連結清單存儲結構存儲，設計一個算法，求該二叉樹的寬度（具有結點數最多的那一層結點的個數）
分析：要求含有最多結點數的層上的結點數，可以分别求出每層的結點數，然後求出最多的，要達到這個目的，必須明确兩點。
- 對于非空樹，樹根所在的層為第一層，并且從層次周遊算法的程式中可以發現，有一個由目前結點找到左、右孩子結點的操作。這就提示到如果知道目前結點的層号，就可以推導出左、右孩子的層号，即為目前結點層号加1，進而可以求出所有結點的層号。
- 在層次周遊中，用到了循環隊列（隊列用數組描述），其出隊和入隊操作為
front=(front+1)%maxSize;
rear=(rear+1)%maxSize;
front=(front+1)%maxSize;
++front;
rear=(rear+1)%maxSize
++rear;
typedef struct {
BTNode *p; //結點指針
int lno; //結點所在層次号
}St;
int maxNode(BTNode *b){
St que[maxSize];
int front,rear; //定義順序非循環隊列
int Lno = 1,i,j,n,max = 0;
front = rear = 0; //将隊列置空
BTNode *q;
if(b != nullptr){
++rear;
que[rear].p = b; //樹根入隊
que[rear].lno = 1;//樹根所在層次号設定為1。
while (front != rear){
++front;
q = que[front].p;
Lno = que[front].lno; //Lno用來存取目前結點的層次号
if(q->lchild != nullptr){
++rear;
que[rear].p = q->lchild;
que[rear].lno = Lno + 1; //根據目前結點的層次号推知其孩子結點的層次号
}
if(q->rchild != nullptr){
++rear;
que[rear].p = q->rchild;
que[rear].lno = Lno + 1; //根據目前結點的層次号推知其孩子結點的層次号
}
}
/****根據que數組中的lno計數并求出最大值******/
for (i = 1; i <= Lno; ++i) {
n = 0;
for (j = 0; j < rear; ++j) {
if(que[j].lno == i){
++n;
}
if(max<n){
max = n;
}
}
}
return max;
}else{
return 0; //空樹直接傳回0
}
}
二叉樹周遊算法的改進
二叉樹的原始周遊方式都是用遞歸函數實作的，這是非常低效的。原因在于系統幫助調用一個棧并做了諸如保護現場和恢複現場等複雜的操作，才使得周遊可以非常簡潔的代碼實作。那麼使用二叉樹深度優先周遊的非遞歸實作和線索二叉樹方式實作，第一種算法用使用者定義的棧來接替系統棧，也就是使用非遞歸的方式實作，可以得到不小的效率提升。第二種算法将二叉樹線索化，不需要棧來輔助完成，更進一步提升了效率。
二叉樹深度優先周遊算法的非遞歸實作
用執行個體進行分析，假設二叉樹如下：
先序周遊非遞歸算法
要寫出非遞歸算法，首先要用自己定義的棧來代替棧的功能。棧在周遊過程中主要做的事情。
- 初始棧空。
- 結點1入棧。
- 出棧，輸出棧頂結點1。并且将1的左、右孩子（2和4）入棧，右孩子先入棧，左孩子後入棧，因為對左孩子的通路要先于右孩子，後入棧的會先出棧通路。
- 出棧，輸出棧頂結點2，并将2的左、右孩子結點（3和5）入棧。
- 出棧，輸出棧頂結點3，3為葉子結點，無孩子，本步無結點入棧。
- 出棧，輸出棧頂結點5。
- 出棧，輸出棧頂結點4，此時棧空，進入終态。
是以周遊順序為1,2,3,5,4。
void preorderNonrecursion(BTNode *bt){
if(bt != nullptr){
BTNode *stack[maxSize];
int top = -1;
BTNode *p;
stack[++top] = bt;
while(top != -1){
p = stack[top--]; //出棧并輸出棧頂結點
printf("%c",p->data);
if(p->rchild != nullptr){ //棧頂結點的右孩子存在，則右孩子入棧
stack[++top] = p->rchild;
}
if(p->lchild != nullptr){ //棧頂結點的左孩子存在，則左孩子入棧
stack[++top] = p->lchild;
}
}
}
}
中序周遊非遞歸算法
類似于先序周遊，對二叉樹進行中序周遊。各個結點入棧、出棧過程如下：
- 初始棧空。
- 結點1入棧，1左孩子存在。
- 結點2入棧，2左孩子存在。
- 結點3入棧，3左孩子不存在。
- 出棧，輸出棧頂結點3，3右孩子不存在。
- 出棧，輸出棧頂結點2，2右孩子存在，右孩子5入棧，5左孩子不存在。
- 出棧，輸出棧頂結點5，5右孩子不存在。
- 出棧，輸出棧頂結點1，1右孩子存在，右孩子4入棧，4左孩子不存在。
- 輸出棧頂結點4，此時棧空，進入終态。
周遊結果：3，2，5，1，4。
由此可以看出，中序周遊過程如下：
- 開始根結點入棧。
- 循環執行如下操作：如果棧頂結點左孩子存在，則左孩子入棧；如果棧頂結點左孩子不存在，則出棧并輸出棧頂結點，然後檢查其右孩子是否存在，如果存在，則右孩子入棧。
- 當棧空時算法結束。
void inorderNonrecursion(BTNode *bt){
if(bt != nullptr){
BTNode *stack[maxSize];
int top = -1;
BTNode *p;
p = bt;
while(top != -1 || p != nullptr){
while (p != nullptr){ //左孩子存在，則左孩子入棧
stack[++top] = p;
p = p->lchild;
}
if(top != -1){ //在站不空的情況下出棧并輸出棧結點
p = stack[top--];
printf("%c",p->data); //通路結點
p = p->rchild;
}
}
}
}
後序周遊非遞歸算法
例子中的二叉樹的先序周遊和後序周遊。
先序周遊：1，2，3，5，4
後序周遊：3，5，2，4，1
把後序周遊逆序一次得到：1，4，2，5，3
逆序逆後序周遊：3，5，2，4，1
觀察後發現，逆序周遊和先序周遊具有一定的聯系。逆後序周遊序列隻不過是先序周遊過程對左右子樹周遊順序交換所得到的結果。（先序周遊是先序周遊根結點，先序周遊左子樹，先序周遊右子樹；逆後序周遊是将先序中左右的周遊進行交換）
是以，隻需要将非遞歸先序周遊算法對左右子樹的周遊順序交換就可以得到逆後序周遊序列，然後對逆後序周遊逆序就得到後序周遊。是以需要兩個棧，一個棧stack1用來輔助做逆後序周遊，并将周遊結果序列壓入另一個棧stack2，然後将stack2中的元素全部出棧，所得到的就是後序周遊序列。
void postorderNonrecursion(BTNode *bt){
if(bt != nullptr){
BTNode *stack1[maxSize];
int top1 = -1;
BTNode *stack2[maxSize];
int top2 = -1;
BTNode *p = nullptr;
stack1[++top1] = bt;
while(top1 != -1){
p = stack1[top1--];
stack2[++top2] = p;
/*注意這裡和先序周遊的差別。左右孩子入棧順序相反*/
if(p->lchild != nullptr){
stack1[++top1] = p->lchild;
}
if(p->rchild != nullptr){
stack1[++top1] = p->rchild;
}
}
while (top2 != -1){
p = stack2[top2--]; //出棧後即為後序周遊
printf("%c",p->data);
}
}
}
注意：周遊的空間複雜度很高，但是不需要考慮。因為研究的是資料結構，不需要對算法空間複雜度有特别的要求。
線索二叉樹
二叉樹非遞歸周遊算法避免了系統棧的調用，提高了一定的執行能力。但是降低了空間複雜度，那麼使用線索二叉樹避免了建立使用者棧，将二叉樹的周遊過程線性化，進一步提高效率。（不一定可以降低空間複雜度，但是線性化一定可以提高效率）
對于二叉連結清單存儲結構，n個結點有n+1個空鍊域，是以将這些空鍊域利用起來，可以讓二叉樹的周遊更為高效，在一般的二叉樹中，隻知道某個結點的左孩子、右孩子，并不能知道某個結點在某種周遊方式中的直接前驅和直接後繼，如果能夠知道前驅和後繼，就可以把二叉樹當做一個連結清單的結構，進而可以像周遊連結清單一樣周遊二叉樹，進而提高效率。
線索二叉樹結點的構造：在二叉樹線索化過程會把樹中的空指針利用起來作為尋找目前結點前驅或後繼的線索，這樣就出現了一個問題，即線索和樹中原有指向孩子的結點的指針無法區分，是以必須有2個辨別域，它們的具體的意義如下：
- 如果ltag=0，則表示lchild為指針，指向結點的左孩子；如果ltag=1，則表示lchild為線索，指向結點的直接前驅。
- 如果rtag=0，則表示rchild為指針，指向結點的右孩子；如果rtag=1，則表示rchild為線索，指向結點的直接前驅。
typedef struct TBTNode{
char data;
int ltag,rtag; //線索标記
struct TBTNode *lchild;
struct TBTNode *rchild;
}TBTNode;
線索二叉樹可以分為前序線索二叉樹、中序線索二叉樹和後序線索二叉樹。對一棵二叉樹中所有結點的空指針域按照某種周遊方式加線索的過程叫做線索化，被線索化了的二叉樹稱為線索二叉樹。
說明：中序線索二叉樹用的最多，前序次之，後序最少。是以重點介紹中序線索二叉樹。
二叉樹中序線索化分析：
- 既然要對二叉樹進行中序線索化，首先要有個中序周遊的架構，這裡采用二叉樹中序周遊算法，在周遊過程中連接配接上合适的線索即可。
- 線索化的規則是，左線索指針指向目前結點在中序周遊序列中的前驅結點，右線索指針指向後繼結點，是以需要一個指針p指向目前正在通路的結點，pre指向p的前驅結點，p的左線索如果存在則讓其指向pre，pre的右線索如果存在則讓其指向p，因為p是pre的後繼結點，這樣就完成了一對線索的連接配接。
- 上一步中保持pre始終指向p前驅的具體過程是，當p将要離開一個通路過的結點時，pre指向p；當p來到一個新結點時，pre顯然指向的是此時p所指結點的前驅結點。
空表示沒有該結點，為了畫出完整圖才加這個。
如圖：某一時刻p指向A，pre指向了中序周遊過程中A的前驅結點D，A是D的後繼，D的右線索指向A。
void InThread(TBTNode *p,TBTNode *&pre){
if(p != nullptr){
InThread(p->lchild,pre); //遞歸，左子樹線索化
if(p->lchild == nullptr){ //建立目前結點的前驅線索
p->lchild = pre;
p->ltag = 1;
}
if(pre!= nullptr&&pre->rchild== nullptr){ //建立前驅結點的後繼結點
pre->rchild = p;
pre->rtag = 1;
}
pre = p; //pre指向目前的p，作為p将要指向的下一個結點的前驅結點訓示指針
p = p->rchild; //p指向一個新結點，此時pre和p分别指向的結點形成了一個前驅後繼，為下一次線索化做準備
InThread(p,pre); //遞歸，右子樹線索化
}
}
上一段代碼中的如下3句：
pre = p;
p = p->rchild;
InThread(p,pre);
可以這樣寫：
pre = p;
InThread(p->rchild,pre);
通過中序周遊建立線索二叉樹的主程式如下：
void createInThread(TBTNode *root){
TBTNode *pre = nullptr; //前驅結點指針
if(root != nullptr){
InThread(root,pre);
pre->rchild = nullptr; //非空二叉樹，線索化
pre->rtag = 1; //進行中序最後一個結點
}
}
求以p為跟的中序線索二叉樹中，中序序列下的第一個結點的算法如下：
TBTNode* First(TBTNode *p){
while (p->ltag == 0){
p = p->lchild; //最左下結點（不一定是葉結點）
}
return p;
}
求在中序線索二叉樹中，結點p在中序下的後繼結點的算法如下：
TBTNode* Next(TBTNode *p){
if(p->rtag == 0){
return First(p->rchild);
}else{
return p->rchild; //rtag == -1,直接傳回後繼線索
}
}
如果把程式中
First()
的ltag和lchild換成rtag和rchild，同時把函數名
First()
換成
Last()
，即可得到求中序序列下最後一個節點的函數
Last()
；如果把程式中
Next()
的rtag和rchild換成ltag和rchild，并同時把函數
First()
換成
Last()
，再把函數名
Next()
改成
Prior()
則可得到求中序序列下前驅結點的函數
Prior()
。
周遊中序線索二叉樹：
void InThreadOrder(TBTNode* root){
for(TBTNode *p = First(root) ; p != nullptr ; p = Next(p)){
printf("%c",p->data);
}
}
前序線索二叉樹
void preThread(TBTNode *p,TBTNode *&pre){
if(p != nullptr){
if(p->lchild == nullptr){
p->lchild = pre;
p->ltag = 1;
}
if(pre != nullptr && pre->rchild == nullptr){
pre->rchild = p;
pre->rtag = 1;
}
pre = p;
/* 注意：這裡在遞歸入口處有限制條件，左、右指針不是線索才繼續遞歸 */
if(p->ltag == 0){
preThread(p->lchild,pre);
}
if(p->rtag == 0){
preThread(p->rchild,pre);
}
}
}
後序線索二叉樹
void postThread(TBTNode* p,TBTNode *&pre){
if(p != nullptr){
postThread(p->lchild,pre);
postThread(p->rchild,pre);
if(p->lchild == nullptr){ //建立目前結點的前驅線索
p->lchild = pre;
p->ltag = 1;
}
if(pre != nullptr && pre->rchild == nullptr){ //建立前驅線索的後繼線索
pre->rchild = p;
pre->rtag = 1;
}
pre = p;
}
}
樹和森林與二叉樹的互相轉換
樹轉換成二叉樹
前邊提到的樹的孩子兄弟存儲結構是基于二叉連結清單實作的，即以二叉連結清單作為樹的存儲結構，隻是結點中的指針域表示的意義不同，對比如下：
- 用二叉連結清單存儲二叉樹，結點中一個指針域叫做lchild，指向左孩子，另一個指針域叫做rchild，指向右孩子。
- 用二叉連結清單存儲樹，結點中一個指針（假設為child）指向一個孩子，另一個指針（假設為sibling）指向自己的兄弟結點。
孩子兄弟存儲結構實質上是一個二叉連結清單，用它來存儲二叉樹是最直接友善的，把一棵樹也能友善的轉換為孩子兄弟存儲結構的過程如下：
- 将同一個結點的各孩子用線串起來。
- 将每個結點的分支從左往右除了第一個以外，其餘的都減掉。
- 調整結點使之符合二叉樹的層次結構。
空表示沒有該結點，為了畫出完整圖才加這個。
二叉樹轉化為樹
将樹轉換為二叉樹的步驟逆置，就可以得到二叉樹轉換為樹的步驟：
- 一棵二叉樹，先把它從左上到右下分為若幹層。
- 找到每一層結點在其上一層的父結點。
- 将每一層的結點和其父結點相連，然後删除每一層結點之間的連接配接。即可得到樹。
總結：左孩子是一個子結點，右孩子是其兄弟結點。
森林轉換為二叉樹
将森林轉換為樹可以看作為樹轉化為二叉樹的擴充，隻不過是由原來的一棵樹的轉換擴充為多棵樹的轉換，要注意一點，要求是将森林轉化為一棵二叉樹，是以将森林中的每棵樹分别轉化後得到的多棵二叉樹應該按照一定的規則連接配接成一棵二叉樹，根據孩子兄弟表示的法則，由于樹的根結點一定是沒有右孩子的，是以轉換為二叉樹後，根結點一定是沒有右孩子的，那麼可以将根結點這個空出來的右結點指針利用起來，即将森林中第二課樹轉換為二叉樹，當做第一棵樹根的右子樹即可，将森林中的第三棵樹轉換成的二叉樹，當做第二課二叉樹的右子樹，依次進行，最終森林就轉換成了一棵二叉樹。
下面說明森林轉化二叉樹的過程：
- 先将森林中所有的樹轉換為二叉樹。
- 然後将第2棵二叉樹作為第1棵二叉樹根結點的右子樹，第3棵二叉樹作為第2棵二叉樹根結點的右子樹，以此類推。
二叉樹轉換為森林
掌握了森林如何轉換為二叉樹，那麼将二叉樹轉換為森林，隻需要不停地将根結點有右孩子的二叉樹的右孩子連接配接斷開，直到不存在根結點有右孩子的二叉樹為止，然後将得到的多棵二叉樹按照二叉樹轉換為樹的規則依次轉化即可。
樹和森林的周遊
樹的周遊
樹的周遊有2種方式：先序周遊和後序周遊。先序周遊是先通路根結點，再依次通路根結點的每棵子樹，通路子樹時仍然遵循先根再子樹的規則；後序周遊是先通路根結點的每棵子樹，再通路根結點，通路子樹時仍然遵循先子樹再根的規則。
使用下圖的例子，寫出其中的先序和後序周遊。
先序周遊
- 通路根結點A。
- 通路A的第一棵子樹，通路子樹時先通路根結點B。
- 通路B的第一個孩子E。
- 通路B的第二個孩子F。
- 通路A的第二棵子樹，通路子樹時先通路根結點C。
- 通路C的第一個孩子G。
- 通路A的第三棵子樹，通路子樹時先通路根結點D。
- 通路D的第一個孩子H。
- 通路D的第二個孩子I。
- 通路D的第三個孩子J。
先序周遊的結果為ABEFCGDHIJ。
後序周遊
- 通路根結點A的第一棵子樹，通路子樹時先通路根B的第一個孩子E。
- 通路B的第二個孩子F。
- 通路B。
- 通路A的第二棵子樹，通路子樹時先通路根C第一個孩子G。
- 通路C。
- 通路A的第三棵子樹，通路子樹時先通路D的第一個孩子H。
- 通路D的第二個孩子I。
- 通路D的第三個孩子J。
- 通路D。
- 最後通路根結點A。
後序周遊的結果：EFBGCHIJDA。
森林的周遊
森林的周遊方式有兩種：先序周遊和後序周遊。
先序周遊的過程：先通路森林中的第一棵的根結點，然後先序周遊第一棵樹中根結點的子樹，最後先序周遊森林中除了第一棵樹以外的其他樹。
後序周遊的過程：後序周遊第一棵樹中根結點的子樹，然後通路第一棵樹的根結點，最後後序周遊森林中出去第一棵樹以後的森林。
森林轉換為二叉樹中，森林的先序周遊對應二叉樹的先序周遊，森林的後序周遊對應二叉樹的中序周遊。
赫夫曼樹和赫夫曼編碼
與赫夫曼樹有關的概念
赫夫曼樹又叫作最優二叉樹，它的特點是帶權路徑最短。首先需要說明幾點概念。
- 路徑：路徑是指從樹中一個結點到另一個結點的分支所構成的路線。
- 路徑長度：是指路徑上的分支數目。
- 樹的路徑長度：是指從根到每個結點的路徑長度之和。
- 帶權路徑長度：結點具有權值，從該結點到根之間的路徑長度乘以結點的權值，就是該結點的帶權路徑的長度。
- 樹的帶權路徑長度（WPL）：是指樹中所有葉子結點的帶權路徑長度之和。
空表示沒有該結點，為了畫出完整圖才加這個。
用例子說明上述概念，4個葉子結點分别為a，b，c，d的權值分别為7、5、2、4。因為a到根結點的分支數目為2，是以a的路徑長度為2，a的帶權路徑長度為 7 × 2 = 14 7 \times 2 =14 7×2=14。同樣，b、c、d的帶權路徑長度分别為 5 × 2 = 10 5\times 2=10 5×2=10， 3 × 2 = 6 3 \times 2 = 6 3×2=6， 4 × 2 = 8 4 \times 2 = 8 4×2=8。于是這棵二叉樹的帶權路徑長度為 W P L = 14 + 10 + 6 + 8 = 38 WPL = 14+10+6+8=38 WPL=14+10+6+8=38
赫夫曼樹的構造原理
給定n個權值，用這n個權值來構造赫夫曼樹的算法描述如下：
- 将這n個權值分别看自作隻有根結點的n棵二叉樹，這些二叉樹構成的集合記為F。
- 從F中選出兩棵根結點的權值最小的樹（假設為a、b）作為左、右子樹，構造一棵新的二叉樹（假設為c），新的二叉樹的根結點的權值為左、右子樹根結點權值之和。
- 從F中删除a、b，加入新構造的樹c。
- 重複進行第2、3步，直到F中隻剩下一棵樹為止，這棵樹就是赫夫曼樹。
下面通過一個執行個體說明赫夫曼樹的構造過程。a，b，c，d的權值依次為7，5，2，4。
- 現将a、b、c、d看作隻有4棵二叉樹。
- 選出權值最小的兩個根c和d，即權值為5和6的兩個根結點，将它們作為左、右子樹。構造成一個新的二叉樹，新的二叉樹的根結點權值為 5 + 6 = 11 5+6=11 5+6=11，删除根權值為5和6的兩棵樹，同時将新構造的二叉樹加入集合中。
- 繼續選擇權值最小的兩個根，即權值為7和11的兩個根，将它們作為左、右子樹，構造出一個新的二叉樹。新的二叉樹的根結點權值為 7 + 11 = 18 7+11=18 7+11=18。删除根權值為7和11的兩棵樹，同時将新構造的二叉樹加入集合中。
- 此時，集合中就剩下一棵二叉樹，這棵樹就是赫夫曼樹，計算其 W P L = 7 × 1 + 5 × 2 + 2 × 3 + 4 × 3 = 35 WPL=7 \times 1 + 5 \times 2+ 2\times 3 + 4 \times 3 =35 WPL=7×1+5×2+2×3+4×3=35。在以a、b、c、d這4個結點為葉子結點的所有二叉樹中，赫夫曼樹的WPL是最小的。
赫夫曼樹的特點：
- 權值越大的結點，距離根越近。
- 樹中沒有度為1的結點，這類樹叫作正則二叉樹。
- 樹的帶權路徑長度最短。
赫夫曼編碼
赫夫曼編碼的主要作用是壓縮檔案。是以用字元串壓縮來對赫夫曼編碼進行詳細分析，假設字元串如下：S=AAABBACCCDEEA，選三位長度的二進制為各個字元編碼（二進制數位數随意，隻要能夠編碼所有不同的字元即可），編碼規則如下：
| A | B | C | D | E |
|---|---|---|---|---|
| 000 | 001 | 010 | 011 | 100 |
T(S)=000000000001001000010010010011100100000，并将其存儲在計算機中。
T(S)長度為39，可以使得串變短一些，且能準确的解碼得到字元串。使用哈夫曼編碼進行，首先統計一下各個字元在字元串中出現的次數。
| A | B | C | D | E |
|---|---|---|---|---|
| 5次 | 2次 | 3次 | 1次 | 2次 |
對A~E的赫夫曼編碼規則
| A | B | C | D | E |
|---|---|---|---|---|
| 110 | 10 | 1110 | 1111 |
以字元為根結點，以通路次數作為權值，構造一個赫夫曼樹。
這裡空結點是赫夫曼樹的構造結點。
擴充：C++文法—引用
引用變量是一個别名，也就是說，它是某個已存在變量的另一個名字。一旦把引用初始化為某個變量，就可以使用該引用名稱或變量名稱來指向變量。
C++引用和指針的對比， 引用很容易與指針混淆，它們之間有三個主要的不同：
- 不存在空引用。引用必須連接配接到一塊合法的記憶體。
- 旦引用被初始化為一個對象，就不能被指向到另一個對象。指針可以在任何時候指向到另一個對象。
- 引用必須在建立時被初始化。指針可以在任何時間被初始化。
試想變量名稱是變量附屬在記憶體位置中的标簽，可以把引用當成是變量附屬在記憶體位置中的第二個标簽。是以，您可以通過原始變量名稱或引用來通路變量的内容。例如：
int i = 17;
可以為 i 聲明引用變量，如下所示：
int &r = i;
double &s = d;
在這些聲明中，&是引用。是以，第一個聲明為"r 是一個初始化為 i 的整型引用"，第二個聲明為"s 是一個初始化為 d 的 double 型引用"。
使用引用作為函數參數
void swap(int &a,int &b){
int temp;
temp = a;
a = b;
b = temp;
}
引用作為傳回值： 當函數傳回一個引用時，則傳回一個指向傳回值的隐式指針。這樣，函數就可以放在指派語句的左邊。
![樹的基本概念(定義、基本術語、性質)[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)