樹和二叉樹的周遊
一、樹的定義與存儲
1、
樹的定義
在計算機科學中，樹是一種非線性結構，存儲的是具有“一對多”關系的資料元素的集合；（是不是像一個家族關系表）
2、
樹的基本術語
3、
樹形結構
用連結清單表示樹的結點
二、二叉樹的定義和性質
N個節點的有限集，每個節點至多有兩顆子樹，二叉樹的子樹有左右之分，不能任意颠倒。
二叉樹有五種基本形态：
特殊二叉樹：
性質：
l 在二叉樹的第i層上至多有2i-1個結點（i>=1）.
l
深度為k的二叉樹至多有2k-1個結點
l
對任意一顆二叉樹T，如果其終端結點為N0，度為2的結點數為N2，則N0=N2+1；
l
具有N個結點的完全二叉樹的深度為[log2N]+1；
三、二叉樹的存儲結構
完全二叉樹可以用數組表示（滿二叉樹是一種特殊的完全二叉樹）
用數組存的特點：
（1）、非根節點i的父親結點的序号為[i/2];
（2）、結點i的左孩子序号為2*i；
（3）、結點i的右孩子序号為2*i+1；
二叉連結清單：
四、二叉樹的周遊
本質：按某種路徑通路樹中的每個節點，使每個節點均被通路一次，且僅被通路一次；
二叉樹有三種常見周遊：先序周遊（有時候稱為前序周遊）、中序周遊、後序周遊；
1、
先序周遊（根左右）
//二叉樹的先序周遊
void PreTree(bTree T) {
if (T) {
printf("%c ", T->data);
PreTree(T->Lchild);
PreTree(T->Rchild);
}
}
2、
中序周遊（左根右）
//二叉樹的中序周遊
void InTree(bTree T) {
if (T) {
InTree(T->Lchild);
printf("%c ", T->data);
InTree(T->Rchild);
}
}
3、
後序周遊（左右根）
//二叉樹的後序周遊
void PostTree(bTree T) {
if (T) {
PostTree(T->Lchild);
PostTree(T->Rchild);
printf("%c ", T->data);
}
}
三種常見周遊一定要記住，（其實也非常容易記，注意根的位置就行了）
4、
非遞歸算法（也就是循環，用到棧）（*）
//非遞歸周遊
void StackTree(bTree T) {
stack<bTree> s;//定義一個結構體類型的棧
if (T == NULL) {
printf("the tree is null.\n");
return ;
}
while (T || !s.empty()) {//中序周遊為例,樹不空或棧不空時循環
if (T) {//判斷樹是否為空
s.push(T);//根指針進棧，周遊左子樹
T = T->Lchild;
}
else {//根指針退棧，通路根節點，周遊右子樹
T = s.top();
printf("%c ", T->data);
s.pop();
T = T->Rchild;
}
}
}
5、層次周遊（*）
按照從上到下、從左至右的循序通路（用隊列實作）
//層次周遊
void QueueTree(bTree T) {
queue<bTree> Q;//定義BTree類型的隊列
if (!T) return;//若是空樹直接傳回
while (!Q.empty())//隊列不為空則清除最前面的元素，直到隊列為空
Q.pop();
Q.push(T);//根節點入隊
while (!Q.empty()) {//隊列不為空則繼續循環
T = Q.front();//讀取隊頭元素
printf("%c ", T->data);
Q.pop();//隊頭出隊
if (T->Lchild)Q.push(T->Lchild);//左孩子入隊尾
if (T->Rchild)Q.push(T->Rchild);//右孩子入隊尾
}
}
五、樹和森林
簡單來講，森林就是樹的集合。
數、森林、二叉樹的轉換：
https://jingyan.baidu.com/article/19020a0a743851529d28421a.html
六、哈夫曼樹與哈夫曼編碼（*）
Huffman樹（最優二叉樹）：帶權路徑長度最小的樹
在這裡插入圖檔描述
哈夫曼樹的構造：
假設有n個權值，則構造出的哈夫曼樹有n個葉子結點。 n個權值分别設為 w1、w2、…、wn，則哈夫曼樹的構造規則為：
(1) 将w1、w2、…，wn看成是有n 棵樹的森林(每棵樹僅有一個結點)；
(2) 在森林中選出兩個根結點的權值最小的樹合并，作為一棵新樹的左、右子樹，且新樹的根結點權值為其左、右子樹根結點權值之和；
(3)從森林中删除選取的兩棵樹，并将新樹加入森林；
(4)重複(2)、(3)步，直到森林中隻剩一棵樹為止，該樹即為所求得的哈夫曼樹。
哈夫曼編碼：左分支0，右分支1（主要用于網絡封包傳輸）