引入
在資料結構中，將現實生活中的樹根抽象為根節點（Root）樹叉抽象為結點（Node），將葉子抽象為（Leaf），將樹枝抽象為邊（Edge），且一條邊只用來連接兩個結點，互為父子節點，
二叉樹的性質
二叉樹
-
樹可以沒有結點，這種情況下把樹稱為空樹，
-
樹的層次從根節點開始算，即根節點算第\(1\)層，【也有的教材規定根結點在第\(0\)層，這里全部以\(1\)層為準】
-
把結點的子樹顆數稱為結點的度（degree），樹中所有結點的最大的度稱為樹的度（也叫做樹的寬度），
-
由于一條邊連接兩個結點，且樹中不會存在環，因此對于有\(n\)個結點的樹，邊樹一定是\(n-1\)，
-
結點的深度是指從根節點（深度為\(1\)）開始自頂向下逐層累加至該結點時的深度值；結點的高度是指從最底層葉子結點（高度為\(1\)）開始自底向上逐層累加至該結點時的高度值，樹的深（高）度是結點的最大深（高）度，所以對樹而言，深度和高度一定是相等的，
-
在深度為 \(k\) 的二叉樹上最多有\(2^{k-1}\)個結點\(（k>=1)\)，
-
對于任何一棵非空的二叉樹，如果葉節點個數為\(n_{0}\)，度數為\(2\)的節點個數為\(n_2\)，則有: $n_0 = n_2 + 1 $
? 在一棵二叉樹中，除了葉子結點（度為\(0\)）之外，就剩下度為\(2(n_2)\)和\(1(n_1)\)的結點了，在二叉樹中結點總數為\(T\)，\(T = n_0+n_1+n_2\)；而總度數為\(T-1\)，所以有：\(n_0+n_1+n_2-1 = 2*n_2 +n_1\)；得\(n_0 = n_2+1\);
完全二叉樹
- 除了最下面一層之外，其余的結點數都達到了本層能達到的最大結點數，且最下面一層從左至右連續存在若干結點，
- 本質上還是一顆二叉樹，適用二叉樹的所有不與1矛盾的性質，
滿二叉樹：
- 每一層的節點數都達到了本層能達到的最大結點數，
- 本質上還是一顆完全二叉樹，適用所有完全二叉樹不與1矛盾的性質，
二叉樹的存盤結構
二叉樹
一般來說，二叉樹的資料結構定義為二叉鏈表，兩個指標域分別指向左子樹和右子樹，不存在指向NULL，
typedef struct BTNode
{
char data;
struct BTNode* Left;
struct BTNode* Right;
}*BTree;
完全二叉樹
對于完全二叉樹，它完全可以也采用上面的二叉鏈表存盤，但由于其特性，還可以有更便捷的存盤方法，對于一個完全二叉樹，如果對所有結點按層次、左右順序編號，規定根結點編號為\(1\)，對任一層的節點\(k（1<=k<=n）\)
- 結點\(k\)的左孩子為\(2*k\)
- 右孩子為\(2*k+1\)
- 如果有父節點（\(k>1\)），父節點為 \(k / 2\) 下取整，
也就是說完全二叉樹可以通過建立一個大小為\(n\)的陣列來存放所有節點的資訊，
而且事實上，即便不是完全二叉樹，可以將其視為完全二叉樹，用一個特殊值（比如 \(-1\) ）表示空節點即可，但這樣空間消耗十分巨大，
二叉樹的遍歷
? 二叉樹的遍歷是指通過一定順序訪問二叉樹的所有節點，二叉樹的有四種遍歷方式，先、中、后序遍歷，“先、中、后”表示根結點的遍歷次序，此外，還有一種層次遍歷，其中前三種一般使用DFS實作，層次遍歷一般使用BFS實作，
先序遍歷
先遍歷分支的根結點，再遍歷左子樹，最后遍歷右子樹，
先序序列：\(ABDFECGHI\)
遞回實作
void Preorder(BTree t) {
if (!t)return;
cout << t->data << " ";
Preorder(t->Left);
Preorder(t->Right);
}
非遞回實作
對于任一結點p：
- 訪問該結點p，并將結點p入堆疊；
- 判斷結點p的左孩子是否為空，若為空，則取堆疊頂結點并進行出堆疊操作，并將堆疊頂結點的右孩子置為當前的 結點p，回圈置a；若不為空，則將p的左孩子置為當前結點p；
- 直到p為空，并且堆疊為空，則遍歷結束，
void preorderUnRecur(BTree T) {
stack<BTree>s;
s.push(T);
while (!s.empty()) {
T = s.top();
s.pop();
cout << T->data << " ";
if (T->Right)
s.push(T->Right);
if (T->Left)
s.push(T->Left);
}
cout << endl;
}
先序序列性質
? 由于先序序列優先訪問根結點，因此對于一顆二叉樹的先序序列來說，序列的第一個一定是根結點，對子樹同樣適用，
中序遍歷
先遍歷左子樹，再遍歷根結點，最后遍歷右子樹，
中序序列：\(DBEFAGHCI\)
遞回實作
void Inorder(BTree t) {
if (!t)return;
Inorder(t->Left);
cout << t->data << " ";
Inorder(t->Right);
}
非遞回實作
對于任一結點：
- 若其左孩子不為空，則將p入堆疊，并將p的左孩子設定為當前的p，然后對當前結點再進行相同的操作；
- 若其左孩子為空，則取堆疊頂元素并進行出堆疊操作，訪問該堆疊頂結點，然后將當前的p置為堆疊頂結點的右孩子；
- 直到p為空并且堆疊為空，則遍歷結束，
void inorderUnRecur(BTree T) {
if (!T)return;
stack<BTree>s;
while (!s.empty() || T) {
if (T) {
s.push(T);
T = T->Left;
}
else {
T = s.top(); s.pop();
cout << T->data << " ";
T = T->Right;
}
}
cout << endl;
}
中序序列性質
? 由于中序序列總是把根結點放在左子樹和右子樹中間，所以只要知道根結點在哪個位置，就可以通過根結點在中序序列中的位置區分出左子樹和右子樹，對子樹同樣適用，
? 比如中序序列：\(DBEFAGHCI\)，\(A\)為根結點，則一定可以知道，樹中\(DBEF\)一定是\(A\)的左子樹部分，而\(GHCI\)一定是\(A\)的右子樹部分，
后序遍歷
先遍歷分支的左子樹，再遍歷右子樹，最后遍歷根結點，
后序序列：\(DEFBHGICA\)
遞回實作
void Postorder(BTree t) {
if (!t)return;
Postorder(t->Left);
Postorder(t->Right);
cout << t->data << " ";
}
非遞回實作
? 在后序遍歷中，要保證左孩子和右孩子都已被訪問，并且左孩子在右孩子之前訪問才能訪問根結點，對于任一結點p，先將其入堆疊，再將p的右孩子和左孩子依次入堆疊，這樣就保證了每次取堆疊頂元素的時候，左孩子在右孩子之前別訪 問，左孩子和右孩子都在根結點前面被訪問，
? 借用兩個堆疊A，B，使用A堆疊訪問，壓堆疊順序為中左右（先序遍歷為中右左），把這些結點存到B堆疊里，最后一起出堆疊，
void postorderUnRecur(BTree T) {
if (!T)return;
stack<BTree>s1,s2;
s1.push(T);
while (!s1.empty()) {
T = s1.top(); s1.pop();
s2.push(T);
if (T->Left)s1.push(T->Left);
if (T->Right)s1.push(T->Right);
}
while (!s2.empty()) {
cout << s2.top()->data << " ";
s2.pop();
}
cout << endl;
}
后序序列性質
? 后序序列總是把根結點放在最后訪問，這和先序序列正好相反，因此對于后序遍歷來說，序列的最后一個結點一定是根結點，對子樹同樣適用，
層次遍歷
層次遍歷是指按層次、左右的順序從根結點向下逐層進行遍歷，也就是完全二叉樹的存盤順序，
void LayerOrder(BTree t) {
queue<BTNode*>q;
q.push(t);
while (!q.empty()) {
BTNode *now = q.front();
q.pop();
if (now->Left) q.push(now->Left);
if (now->Right)q.push(now->Right);
}
}
這里佇列中使用的元素是BTNode*，用BTNode也是可以的，只不過沒法再遍歷程序中對原樹做修改，因為此時佇列中存的是副本，
重建二叉樹
給定包含中序序列的兩個序列（也包括層序序列，代碼沒有寫）可以重建出唯一的二叉樹（不包含中序序列的兩個、甚至三個序列創建出的二叉樹不唯一），
BTree BuildTree_pre_in(char* pre, char* in, int length) {
if (length == 0)
return NULL;
BTree BT = new BTNode;
BT->data = https://www.cnblogs.com/czc1999/p/*pre;
int rootIndex = 0;
//當前子樹先序序列的首個結點，是當前子樹的根，
while (in[rootIndex] != *pre)
rootIndex++;
//剛才找到的結點，在中序序列中，它左邊的部分是它的左子樹，右邊的部分是它的右子樹，，
BT->Left = BuildTree_pre_in(pre + 1, in, rootIndex);
BT->Right = BuildTree_pre_in(pre + rootIndex + 1, in + rootIndex + 1, length - (rootIndex + 1));//因為rootIndex是下標，所以這里都要+1
return BT;
}
BTree BuildTree_in_post(char* in, char* post, int length) {
if (length == 0)
return NULL;
BTree BT = new BTNode;
BT->data = *(post + length - 1);
int rootIndex = length - 1;
//當前子樹后序序列的最后一個結點，是當前子樹的根，
while (in[rootIndex] != *(post + length - 1))
rootIndex--;
//剛才找到的結點，在中序序列中，它左邊的部分是它的左子樹，右邊的部分是它的右子樹，
BT->Left = BuildTree_in_post(in, post, rootIndex);
BT->Right = BuildTree_in_post(in + rootIndex + 1, post + rootIndex, length - (rootIndex + 1));
return BT;
}
完整測驗代碼如下：
#include <iostream>
#include <stack>
using namespace std;
typedef struct BTNode
{
char data;
struct BTNode* Left;
struct BTNode* Right;
}*BTree;
BTree BuildTree_pre_in(char* pre, char* in, int length) {
if (length == 0)
return NULL;
BTree BT = new BTNode;
BT->data = https://www.cnblogs.com/czc1999/p/*pre;
int rootIndex = 0;
//當前子樹先序序列的首個結點，是當前子樹的根，
while (in[rootIndex] != *pre)
rootIndex++;
//剛才找到的結點，在中序序列中，它左邊的部分是它的左子樹，右邊的部分是它的右子樹，
BT->Left = BuildTree_pre_in(pre + 1, in, rootIndex);
BT->Right = BuildTree_pre_in(pre + rootIndex + 1, in + rootIndex + 1, length - (rootIndex + 1));//因為rootIndex是下標，所以這里都要+1
return BT;
}
BTree BuildTree_in_post(char* in, char* post, int length) {
if (length == 0)
return NULL;
BTree BT = new BTNode;
BT->data = *(post + length - 1);
int rootIndex = length - 1;
//當前子樹后序序列的最后一個結點，是當前子樹的根，
while (in[rootIndex] != *(post + length - 1))
rootIndex--;
//剛才找到的結點，在中序序列中，它左邊的部分是它的左子樹，右邊的部分是它的右子樹，
BT->Left = BuildTree_in_post(in, post, rootIndex);
BT->Right = BuildTree_in_post(in + rootIndex + 1, post + rootIndex, length - (rootIndex + 1));
return BT;
}
void Inorder(BTree T) {
/*if (!BT)return;
Inorder(BT->Left);
cout << BT->data <<" ";
Inorder(BT->Right);*/
if (!T)return;
stack<BTree>s;
while (!s.empty() || T) {
if (T) {
s.push(T);
T = T->Left;
}
else {
T = s.top(); s.pop();
cout << T->data << " ";
T = T->Right;
}
}
cout << endl;
}
void Preorder(BTree BT) {
/*if (!BT)return;
cout << BT->data << " ";
Preorder(BT->Left);
Preorder(BT->Right);*/
stack<BTree>s;
s.push(BT);
while (!s.empty()) {
BT = s.top();
s.pop();
cout << BT->data << " ";
if (BT->Right)
s.push(BT->Right);
if (BT->Left)
s.push(BT->Left);
}
cout << endl;
}
void Postorder(BTree T) {
/*if (!BT)return;
Postorder(BT->Left);
Postorder(BT->Right);
cout << BT->data << " ";*/
if (!T)return;
stack<BTree>s1, s2;
s1.push(T);
while (!s1.empty()) {
T = s1.top(); s1.pop();
s2.push(T);
if (T->Left)s1.push(T->Left);
if (T->Right)s1.push(T->Right);
}
while (!s2.empty()) {
cout << s2.top()->data << " ";
s2.pop();
}
cout << endl;
}
int main() {
char pre[] = "ABDGHCEIF";
char in[] = "GDHBAEICF";
char post[] = "GHDBIEFCA";
BTree T1 = BuildTree_pre_in(pre, in, strlen(in));
BTree T2 = BuildTree_in_post(in, post, strlen(in));
Postorder(T1);
Postorder(T2);
Preorder(T1);
Preorder(T2);
Inorder(T1);
Inorder(T2);
cout << endl;
return 0;
}
后補
二叉樹的前驅后繼結點，表示中序遍歷時，一個結點的前一個和后一個，
獲取二叉樹的深度
int height(BTree T) {
if (T == NULL)
return 0;
int left = height(T->Left);
int right = height(T->Right);
return left >= right ? left + 1 : right + 1;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/136675.html
標籤：其他
上一篇：圖論篇6——割點（關節點）