【數據結構】二叉樹、普通樹與森林的定義與應用

2021 年 11 月 4 日
筆記
22考研

普通$m$叉樹的性質（普通二叉樹也滿足）
1. 各層的最大結點個數
\[第i層最多有m^{i-1}個結點，其中1\le i\le h
\]
1. 高度為h的$m$叉樹最多結點個數
\[等比數列求和公式：\frac{m^h-1}{m-1}
\]
1. 具有$n$個結點的$m$叉樹至少有多高
也就是說完全m叉樹的高度是多少？有以下兩種表示方式：
1. 高為$h$的完全二叉樹最多有$\frac{m^h-1}{m-1}$個結點，所以$h=⌈\small{\log_m[n(m-1)+1]}\normalsize⌉$；
2. 高為$h$的完全二叉樹至少有$\frac{m^{h-1}-1}{m-1}+1$個結點，所以$h=⌈\small{\log_m[(n-1)(m-1)+1]}\normalsize⌉+1$；
1. $n$個結點對應$n-1$度，也就有$n-1$條邊；
二叉樹的常考性質（$n$為總結點數，$n_i$為度為$i$的結點數）
1. 二叉樹總結點數與各類型結點數的關係
\[\begin{cases}
n=n_0+n_1+n_2
\\
n=0\times n_0+1\times n_1+2\times n_2+1
\end{cases}
\Longrightarrow
n_0=n_2+1
\]
1. 高度為$h$的霍夫曼樹有$2h-1$個結點
高度為$h$的二叉樹上只有度為0和度為2的結點，則此類二叉樹中所包含的結點數至少為$2h-1$。
1. 計算二叉樹各種類型的節點的個數
1. 雙分支結點
\[f(T)=
\begin{cases}
0，&如果T是空樹；
\\
f(T\rightarrow lchild)+f(T\rightarrow rchild)，&如果T不是雙分支結點；
\\
f(T\rightarrow lchild)+f(T\rightarrow rchild)+1，&如果T是雙分支結點；
\end{cases}
\]
```
int TwoBranchNodes(BiTree T){
       if(T == nullptr){
           return 0;
       }
       else if(T->lchild != nullptr && T->rchild != nullptr){
           return TwoBranchNodes(T->lchild) + TwoBranchNodes(T->rchild) + 1;
       }
       else{
           return TwoBranchNodes(T->lchild) + TwoBranchNodes(T->rchild);
       }
}
```
1. 單分支結點
\[f(T)=
\begin{cases}
0，&如果T是空樹；
\\
f(T\rightarrow lchild)+f(T\rightarrow rchild)，&如果T是雙或者葉子；
\\
f(T\rightarrow lchild)+f(T\rightarrow rchild)+1，&如果T是單分支結點；
\end{cases}
\]
```
int OneBranchNodes(BiTree T){
       if(T == nullptr){
           return 0;
       }
       else if((T->lchild == nullptr) ^ (T->rchild == nullptr)){
           return OneBranchNodes(T->lchild) + OneBranchNodes(T->rchild) + 1;
       }
       else{
           return OneBranchNodes(T->lchild) + OneBranchNodes(T->rchild);
       }
}
```
1. 葉子結點
\[f(T)=
\begin{cases}
0，&如果T是空樹；
\\
f(T\rightarrow lchild)+f(T\rightarrow rchild)，&如果T是分支結點；
\\
1，&如果T是葉子結點；
\end{cases}
\]
```
int NoneBranchNodes(BiTree T){
       if(T == nullptr){
           return 0;
       }
       else if(T->lchild == nullptr && T->rchild == nullptr){
           return 1;
       }
       else{
           return NoneBranchNodes(T->lchild) + NoneBranchNodes(T->rchild);
       }
}
```

完全二叉樹常考性質

完全二叉樹中各類型結點的個數

\[完全二叉樹中根據n可以推出n_i的個數
\begin{cases}
若n=2k&\Longrightarrow n_1=1,n_0=k,n_2=k-1；
\\
若n=2k-1&\Longrightarrow n_1=0,n_0=k,n_2=k-1；
\end{cases}
\]

完全$m$叉樹編號的性質
編號$i$的首個孩子結點（若存在）的編號

\[(i-1)m+1+1
\]

$(i-1)m$表示前$i-1$個結點一共產生的結點數；

第一個1指的是根結點；

第二個1表示這是首個孩子；

編號為$i$的結點的第$k$個孩子結點（若存在）的編號

\[(i-1)m+1+k，其中1指的是根結點，k表示這是第k個孩子
\]

編號為$i$的結點的雙親結點（若存在）的編號

\[\small{⌊\frac{i-2}{m}⌋+1，問題b和c的逆問題。由於k不確定具體指，但k-1\lt m，所以統一減2後向下取整}
\]

編號為$i$的結點有右兄弟的條件，以及該右兄弟結點的編號

結點$i$不是其雙親的第$m$個子女時才有右兄弟。有以下兩種闡述方式：

對於結點$j$，其第$k$個子女結點的編號$i$為$(j-1)m+1+k$，只有當$k=m$時$(i-1)\%{m}=0$才會成立，若想要使得$i$不是第$m$個孩子，只需要滿足$(i-1)%m!=0 $ 即可；

由於第$m$個孩子結點的編號為$jm+1$，所以滿足$i\le jm=(⌊\frac{i-2}{m}⌋+1)\cdot m$也行；

總數為$n$個結點的$m$叉樹中葉子結點的個數

由於最後一個分支結點是最後一個結點的父節點，所以其編號為$⌊\frac{n-2}{m}⌋+1$，所以葉子結點的總數為$n-⌊\frac{n-2}{m}⌋+1$。特別地，當$m=2$時可被化簡為：$⌊\frac{n}{2}⌋$。

已知兩結點的編號求最近的公共祖先
循環不變數：編號大的向上走。循環退出條件：編號相等。
ElemType NearestAncestor(SeqTree T, int i, int j){
       if(T[i]!='#' && T[j]!='#'){
           while(i!=j){
               if(i>j){
                   i = i / 2;
               }
               else{
                   j = j / 2;
               }
           }
           return T[i];
       }
       else{
           cout << "傳入的結點不存在！" << endl;
           exit(0);
       }
}
完全二叉樹的高度

具有$n$個（$n\gt0$）結點的完全二叉樹的高度$h=⌈\log_2(n+1)⌉$或者$⌊\log_2(n)+1⌋$；

完全二叉樹的判定
空結點後不能出現非空結點（層次遍歷納入空結點）
bool IsComplete(BiTree T){
       InitQueue(Q);
       if(!T){
           return true;
       }
       else{
           EnQueue(Q, T);
           while(!IsEmpty(Q)){
               DeQueue(Q, parentNode);
               if(parentNode != nullptr){
                   EnQueue(Q, parentNode->lchild);
                   EnQueue(Q, parentNode->rchild);
               }
               else{
                   // 空結點之後必須全為空結點才能返回TRUE
                   while(!IsEmpty(Q)){
                       DeQueue(Q, parentNode);
                       if(parentNode != nullptr){	
                           // 如果不是空節點，則說明葉子結點後面還存在非葉子結點，這個非葉子節點的孩子節點就是此非空節點
                           return false;
                       }
                   }// End While
               }// End parentNode==nullptr
           }// End While
           return true;
       }// End T!=nullptr
}
滿二叉樹確定二叉鏈表的結構
可以僅通過先序或者後序或者層序（不需要中序）！因為對於一棵滿二叉樹而言，每一個雙分支結點都有相等長度的左右子樹，故而不需要中序序列確定左右子樹的長度。

先序遍歷序列唯一確定
BiTree PreOrder(char order[], int preLow, int preHigh) {
       if (preHigh >= preLow) {
           // 左右子樹的長度為half
           int half = (preHigh - preLow) / 2;
           BiTree root = (BiTree)malloc(sizeof(BiTreeNode));
           // 創建根結點
           root->data = order[preLow];
           // 創建左子樹
           root->lchild = PreOrder(order, preLow+1, preLow+half);
           // 創建左子樹
           root->rchild = PreOrder(order, preLow+half+1, preHigh);
           return root;
       }
       else {
           return nullptr;
       }
}
後序遍歷序列唯一確定
BiTree PostOrder(char order[], int preLow, int preHigh) {
       if (preHigh >= preLow) {
           // 左右子樹的長度為half
           int half = (preHigh - preLow) / 2;
           BiTree root = (BiTree)malloc(sizeof(BiTreeNode));
           // 創建左子樹
           root->lchild = PostOrder(order, preLow, preLow+half-1);
           // 創建左子樹
           root->rchild = PostOrder(order, preLow+half, preHigh-1);
           // 創建根結點
           root->data = order[preHigh];
           return root;
       }
       else {
           return nullptr;
       }
}
層序遍歷序列唯一確定
這個可以用滿二叉樹編號的性質。
BiTree LevelOrder(char order[], int levelRoot){
       if(levelRoot <= N){
           BiNode* root = (BiNode*)malloc(sizeof(BiNode));
           // 創建根結點
           root->data = order[levelRoot];
           // 創建左子樹
           root->lchild = LevelOrder(order, 2*levelRoot);
           // 創建右子樹
           root->rchild = LevelOrder(order, 2*levelRoot+1);
       }
       else{
           return nullptr;
       }
}
其中先序和後序的轉化是最簡單的
只要遞歸地將根結點與子樹的節點換位即可。如下圖所示：
void PreToPost(BiTree pre[], int preLow, int preHigh, BiTree post[], int postLow, int postHigh) {
       int half;
       if (preHigh >= preLow) {
           // 轉換根結點（根結點後置）
           post[postHigh] = pre[preLow];
           half = (preHigh - preLow) / 2;
           // 轉換左子樹（左子樹前移）
           PreToPost(pre, preLow + 1, preLow + half, post, postLow, postLow + half - 1);
           // 轉換右子樹（右子樹前移）
           PreToPost(pre, preLow + half + 1, preHigh, post, postLow + half, postHigh - 1);
       }
}

二叉樹遍歷的應用

求二叉樹樹高

遞歸演算法（後序遍歷）

// 樹高 = 左右子樹的最大值 + 1（根節點）
int BiTreeDepth(BiTree TRoot){
       if(TRoot == nullptr){
           return 0;
       }
       else{
           int leftDepth = BiTreeDepth(TRoot->lchild);
           int rightDepth = BiTreeDepth(TRoot->rchild);
           return Max(leftDepth, rightDepth) + 1;
       }
}

時間複雜度：$O(n)$，空間複雜度：$O(\mathbf{Height}(T))$【平衡時才是：$O(⌈\log_2(n+1)⌉)$】；

非遞歸演算法（層序遍歷+輔助隊列）

int GetBiTreeWidth(BiTree T){
       if(!T){
           return 0;
       }
       else if(T->lchild == nullptr && T->rchild == nullptr){
           return 1;
       }
       else{
           // 創建一個輔助隊列並初始化
           AuxQue auxque;
           InitQueue(auxque);
           auxque->front = auxque->rear = -1;
           // 記錄父層的層號、最右端結點的序號，子層的結點個數（已訪問）
           // 父層：上一層（刪除結點層）；子層：當前層（插入結點層）
           int depth, lastNodeOrder, nodeCount;
           // 將根節點插入隊列中（插入後根節點所在的層變成父層）
           auxque->data[++auxque->rear] = T;
           depth = 0, lastNodeOrder = auxque->rear, nodeCount = 0;
           while(auxque->front < auxque->rear){
               // 將父層的元素取出，移動front指針
               TreeNode parentNode = auxque->data[++auxque->front];
               // 插入孩子結點，並使結點計數器自增1
               if(parentNode->lchild != nullptr){
                   auxque->data[++auxque->rear] = parentNode->lchild;
                   nodeCount++;
               }
               if(parentNode->rchild != nullptr){
                   auxque->data[++auxque->rear] = parentNode->rchild;
                   nodeCount++;
               }
               // front指針指向了父層的最右端元素，父層的最後一個元素被彈出
               if(auxque->front == lastNodeOrder){
                   // 同時子層的最後一個節點也插入完成了，子層變成了新的父層
                   lastNodeOrder = auxque->rear;
                   depth++;
                   nodeCount = 0;
               }
           }// End While
           return depth;
       }
}

時間複雜度：$O(n)$，空間複雜度：$O(n)$；

求二叉樹樹寬

遞歸演算法（先序遍歷+輔助數組）

#define MAX_HEIGHT 100
void PreOrder(BiTree T, int level, int* width){
       if(!T){
           return;
       }
       else{
           width[level]++;
           PreOrder(T->lchild, level + 1, width);
           PreOrder(T->rchild, level + 1, width);
       }
}

int GetBiTreeWidth(BiTree T){
       int* width = (int*)malloc(sizeof(int) * MAX_HEIGHT);
       for(int i=0; i<MAX_HEIGHT; i++){
           width[i] = 0;
       }
       PreOrder(T, 1, width);
       int maxWidth = 0;
       for(int i=0; i<MAX_HEIGHT; i++){
           maxWidth = maxWidth < width[i] ? width[i] : maxWidth;
       }
       return maxWidth;
}

時間複雜度：$O(n)$，空間複雜度：$O(\mathbf{Height}(T))$；【平衡時才是：$O(⌈\log_2(n+1)⌉)$】

非遞歸演算法（層序遍歷+輔助隊列）

int GetBiTreeWidth(BiTree T){
       if(!T){
           return 0;
       }
       else if(T->lchild == nullptr && T->rchild == nullptr){
           return 1;
       }
       else{
           // 創建一個輔助隊列並初始化
           AuxQue auxque;
           InitQueue(auxque);
           auxque->front = auxque->rear = -1;
           // 記錄父層的寬度、最右端結點的序號，子層的結點個數（已訪問）
           // 父層：上一層（刪除結點層）；子層：當前層（插入結點層）
           int width, lastNodeOrder, nodeCount;
           // 將根節點插入隊列中（插入後根節點所在的層變成父層）
           auxque->data[++auxque->rear] = T;
           width = 1, lastNodeOrder = auxque->rear, nodeCount = 0;
           while(auxque->front < auxque->rear){
               // 將父層的元素取出，移動front指針
               TreeNode parentNode = auxque->data[++auxque->front];
               // 插入孩子結點，並使結點計數器自增1
               if(parentNode->lchild != nullptr){
                   auxque->data[++auxque->rear] = parentNode->lchild;
                   nodeCount++;
               }
               if(parentNode->rchild != nullptr){
                   auxque->data[++auxque->rear] = parentNode->rchild;
                   nodeCount++;
               }
               // front指針指向了父層的最右端元素，父層的最後一個元素被彈出
               if(auxque->front == lastNodeOrder){
                   // 同時子層的最後一個節點也插入完成了，子層變成了新的父層
                   lastNodeOrder = auxque->rear;
                   width = Max(width, nodeCount);
                   nodeCount = 0;
               }
           }// End While
           return width;
       }
}

時間複雜度：$O(n)$，空間複雜度：$O(n)$；

遍歷序列確定二叉鏈表（思想是重點）

先中序列

先序遍歷序列確定根結點，中序遍歷中確定左右子樹及各子樹的長度，回到先序遍歷序列通過子樹長度確定子樹所在的範圍，然後再確定左右子樹的根結點。

BiTree CreateBiTree(ElemType* PreOrder, ElemType* InOrder, int PreLow, int PreHigh, int InLow, int InHigh){
       int parentIndexPre, parentIndexIn;
       // 在InOrder序列中從InLow到InHigh查找根結點PreOrder[parentIndexPre]
       parentIndexPre = PreLow, parentIndexIn = FindIndex(InOrder, PreOrder[parentIndexPre], InLow, InHigh);
       // 創建根結點
       BiNode* parentNode = (BiNode*)malloc(sizeof(BiNode));
       parentNode->data = InOrder[parentIndexIn];
       // 通過中序遍歷中根結點的編號確定左右子樹的長度
       int lchildLength = parentIndexIn - InLow;
       int rchildLength = InHigh - parentIndexIn;
       // 創建左子樹
       if(lchildLength != 0)
       {
           parentNode->lchild = CreateBiTree(PreOrder, InOrder, PreLow+1, PreLow+lchildLength, InLow, InLow+lchildLength-1);
       }
       else
       {
           parentNode->lchild = nullptr;
       }
       // 創建右子樹
       if(rchildLength != 0)
       {
           parentNode->rchild = CreateBiTree(PreOrder, InOrder, PreHigh-rchildLength+1, PreHigh, InHigh-rchildLength+1, InHigh);
       }
       else
       {
           parentNode->rchild = nullptr;
       }
       return parentNode;
}

後中序列

後序遍歷序列確定根結點，中序遍歷中確定左右子樹及各子樹的長度，回到後序遍歷序列通過子樹長度確定子樹所在的範圍，然後再確定左右子樹的根結點。

BiTree CreateBiTree(ElemType* PostOrder, ElemType* InOrder, int PostLow, int PostHigh, int InLow, int InHigh){
       int parentIndexPost, parentIndexIn;
       // 在InOrder序列中從InLow到InHigh查找根結點PostOrder[parentIndexPost]
       parentIndexPost = PostHigh, parentIndexIn = FindIndex(InOrder, PostOrder[parentIndexPost], InLow, InHigh);
       // 創建根結點
       BiNode* parentNode = (BiNode*)malloc(sizeof(BiNode));
       parentNode->data = InOrder[parentIndexIn];
       // 通過中序遍歷中根結點的編號確定左右子樹的長度
       int lchildLength = parentIndexIn - InLow;
       int rchildLength = InHigh - parentIndexIn;
       // 創建左子樹
       if(lchildLength != 0)
       {
           parentNode->lchild = CreateBiTree(PostOrder, InOrder, PostLow, PostLow+lchildLength-1, InLow, InLow+lchildLength-1);
       }
       else
       {
           parentNode->lchild = nullptr;
       }
       // 創建右子樹
       if(rchildLength != 0)
       {
           parentNode->rchild = CreateBiTree(PostOrder, InOrder, PostHigh-rchildLength, PostHigh-1, InHigh-rchildLength+1, InHigh);
       }
       else
       {
           parentNode->rchild = nullptr;
       }
       return parentNode;
}

層中序列

層序遍歷的規則是：遍歷孩子結點之前先把孩子結點的所有祖先結點和其左(堂)兄弟遍歷一遍。所以當我們拿到層序遍歷序列中的某個結點時，我們可以肯定的說：「我們有能力將其所有祖先結點構造好！」，故而只需要在中序序列中確定它與根結點的相對位置就行了。

#include<map>
#define MAX_SIZE 100
// 定義層序序列和先序序列
ElemType levelOrder[MAX_SIZE], inOrder[MAX_SIZE];
// 定義記錄中序序列各個結點位置的字典（映射）：{結點值：結點在中序序列中的編號}
map<ElemType, int> inPos;

// 在指定levelIndex位置創建root結點
void CreateBiTreeNode(BiTreeNode*& root, int levelIndex){
       // 如果走到了現有的樹的底部，則新創建結點（構造祖先結點）
       if(root == nullptr){
           root = (BiTreeNode*)malloc(sizeof(BiTreeNode));
           root->data = levelOrder[levelIndex];
           root->lchild = root->rchild = nullptr;
           return;
       }
       // 如果層序中的結點在中序序列中的位置靠左，
       // 表明該結點在其根結點的左邊，讓根結點移向其左孩子
       else if(inPos[root->data] >= inPos[levelOrder[levelIndex]]){
           CreateBiTreeNode(root->lchild, levelIndex);
       }
       // 否則表明在根結點的右邊，讓根結點移向其右孩子
       else{
           CreateBiTreeNode(root->rchild, levelIndex);
       }
}

// 創建二叉樹
void CreateBiTree(BiTree& BT){
       for(int i=0; i<n; i++){
           CreateBiTreeNode(BT, i);
       }
}

總結（給啥序列就按照啥規則辦事）

給先序序列：（前序規則）從先序數組起始處確定根結點，再在中序中查找根結點的位置，然後確定根結點的左右子樹；

給後序序列：（後序規則）從後序數組末尾處確定根結點，再在中序中查找根結點的位置，然後確定根結點的左右子樹；

給層序序列：（層序規則）從頭到尾遍歷層序數組，再在中序序列中確定該結點與根結點的關係，並一層一層下墜；

先序、中序和後序線索二叉樹的構造

#define THREAD 1
#define LINK 0
// 將二叉鏈表線索化的函數
void Threading(BiTreeNode current, BiTreeNode& previous){
       // 左子樹為空，則建立前驅線索
       if(current != nullptr && current->lchild == nullptr){
           // 判斷cur!=nullptr是因為美觀，cur一直不會為空，因為遞歸遍歷有if保證
           current->lchild = previous;
           current->ltag = THREAD;
       }
       // 右子樹為空，則建立後繼線索
       if(previous != nullptr && previous->rchild == nullptr){
           // 判斷pre!=nullptr是因為pre初始化為nullptr
           previous->rchild = current;
           prevoius->rtag = THREAD;
       }
       // 向前移動
       previous = current;
}

遞歸演算法（樹的遞歸特性）

// 定義函數指針類型指明傳入的是哪一種遍歷方式
typedef void (*OrderThreading)(BiTree current,BiTree& previous);

// 創建線索化二叉鏈表
void CreateThreadTree(BiTree T, OrderThreading OT){
       BiTreeNode previous = nullptr;
       if(T != nullptr){
           OT(T->lchild, prevoius);
           // 為最後一個結點做後繼線索化
           if(previous->rchild == nullptr){
               previous->rtag = THREAD;
           }
       }
}

// 先序遍歷
void PreOrderThreading(BiTree current,BiTree& previous){
       if(current != nullptr){
           Threading(current, previous);
           // 防止先序遍歷時產生「愛滴魔力轉圈圈」的情況
           if(current->ltag == LINK){
               PreOrderThreading(current->lchild, previous);
           }
           PreOrderThreading(current->lchild, previous);
       }
}
// 中序遍歷
void InOrderThreading(BiTree current,BiTree& previous){
       if(current != nullptr){
           PreOrderThreading(current->lchild, previous);
           Threading(current, previous);
           PreOrderThreading(current->lchild, previous);
       }
}
// 後序遍歷
void PostOrderThreading(BiTree current,BiTree& previous){
       if(current != nullptr){
           PreOrderThreading(current->lchild, previous);
           PreOrderThreading(current->lchild, previous);
           Threading(current, previous);
       }
}

【注】出現「愛滴魔力轉圈圈」問題是因為：在訪問後繼結點之前^[1]，後繼結點的前驅線索指針與後繼指針重合^[2]。[1]指明根結點需要先訪問，所以只會發生在先序遍歷中；[2]只能是左孩子指針才能「身兼二職」。

非遞歸演算法（用輔助棧實現非遞歸的遍歷）

先序遍歷和中序遍歷很相似，一個是在壓入棧之前訪問（入棧序列），一個是彈出棧之後訪問（出棧序列）。由於頭插法的性質，輔助棧棧頂元素即是前驅結點。

// 先序遍歷
void PreOrderThreading(BiTree T){
       InitStack(S);
       BiTreeNode current = T;
       // 當前指針不空或者輔助棧不空就繼續
       while(current != nullptr || !IsEmpty(S)){
           // 防止出現「愛滴魔力轉圈圈」的情況
           if(current != nullptr && current->ltag == LINK){
               BiTreeNode previous = nullptr;
               GetTop(S, previous);
               Threading(current, previous);
               // 將線索化後的根結點壓入棧中，並繼續向左移動
               Push(S, current);
               current = current->lchild;
           }
           else{
               // 將根結點取出並向右移動
               Pop(S, current);
               current = current->rchild;
           }
       }
}

// 中序遍歷
void InOrderThreading(BiTree T){
       InitStack(S);
       BiTreeNode current = T;
       // 當前指針不空或者輔助棧不空就繼續
       while(current != nullptr || !IsEmpty(S)){
           if(current != nullptr){
               // 將根結點壓入棧中，並繼續向左移動
               Push(S, current);
               current = current->lchild;
           }
           else{
               // 將根結點取出，線索化後再向右移動
               Pop(S, current);
               BiTreeNode previous = nullptr;
               GetTop(S, previous);
               Threading(current, previous);
               current = current->rchild;
           }
       }
}

後序遍歷就完全不同了，因為必須保證左右子樹都要訪問完成，所以必須藉助「前驅指針$\mathbf{previous}$證明是否被訪問過」進行流程式控制制，這就大大增加了難度。

// 後序遍歷
void PostOrderThreading(BiTree T){
       // 倘若不想使用棧，則需要使用三叉鏈表的存儲結構（第三叉指向雙親節點）
       InitStack(StackOfParent);
       BiNode* cursor, previous;
       cursor = T, previous = nullptr;
       while(cursor || !IsEmpty(StackOfParent)){
           // 因為我們需要將cursor壓入棧內，所以不能僅僅判斷cursor有無左孩子
           if(cursor){
               // 如果當前位置存在節點，則將其作為「雙親節點」入棧
               Push(StackOfParent, cursor);
               // 並指向自己的左孩子（繼續向左走）
               cursor = cursor->lchild;
           }
           else{
               // 如果當前位置不存在節點，說明向左走走到頭了，需要向右轉後者向上走（如果沒有右孩子或者已經向右轉過則不需要了）
               GetTop(StackOfParent, parent);
               // 如果右兄弟存在且沒有被訪問過，則向右轉
               if(parent->rchild!=nullptr && parent->rchild!=previous){
                   // 不判斷右兄弟是否存在會造成死循環
                   cursor = parent->rchild;
               }
               // 向上走
               else{
                   // 說明該雙親結點的左右子樹都已經訪問完成了（或者沒有孩子），所以彈出雙親節點
                   Pop(StackOfParent, parent);
                   // 訪問「根」（也就是雙親結點）
                   BiTreeNode previous = nullptr;
                   GetTop(StackOfParent, previous);
                   Threading(parent, previous);
                   // 移動前驅指針
                   previous = parent;
                   // 為了後續操作為向右轉向（因為根節點訪問完了就代表這一整棵子樹已經訪問完成，所以需要向上向右走轉向右兄弟樹）
                   cursor = nullptr;
               }
           }
       }
}

先中後序遍歷查找的前驅後繼（手算的方法）

先序遍歷查找前驅後繼（需要三叉鏈表獲取雙親結點）

若p->rtag == THREAD，即結點已被後繼線索化，則next = p->rchild；

若p->ltag == THREAD，即結點已被前驅線索化，則previous = p->lchild；

若p->rtag == LINK，即結點未被後繼線索化（分支結點），則該節點必有右孩子，按照「根[左]右」的規則可以分2種情況：

有左孩子，即p->lchild != nullptr：next = p->lchild；

無左孩子，即p->lchild == nullptr：next = p->rchild；

若p->ltag == LINK，即結點未被前驅線索化（分支結點），但是先序遍歷的前驅是比不會存在於其左右子樹中的，所以需要藉助三叉鏈表獲取其雙親結點。

p是左孩子：則由「根（p左右）[右]」可知，previous = p->parent；

p是右孩子，且沒有左兄弟：則由「根（p左右）」可知，previous = p->parent；

p是右孩子，存在左兄弟：則由「根（根左右）（p左右）」可知，previous = 左兄弟的右優先葉子結點；

中序遍歷查找前驅後繼

若p->rtag == THREAD，即結點已被後繼線索化，則next = p->rchild；

若p->ltag == THREAD，即結點已被前驅線索化，則previous = p->lchild；

若p->rtag == LINK，即結點未被後繼線索化（分支結點），則該節點必有右孩子，所以next = 右子樹最左下結點；

若p->ltag == LINK，即結點未被前驅線索化（分支結點），則該節點必有左孩子，所以previous = 左子樹最右下結點；（出現右子樹向左走，否則向左）

後序遍歷查找前驅後繼（需要三叉鏈表獲取雙親結點）

若p->rtag == THREAD，即結點已被後繼線索化，則next = p->rchild；

若p->ltag == THREAD，即結點已被前驅線索化，則previous = p->lchild；

若p->ltag == LINK，即結點未被前驅線索化（分支結點），則該節點必有左孩子，按照「左[右]根」的規則可以分2種情況：

有右孩子，即p->rchild != nullptr：previous = p->rchild；

無右孩子，即p->rchild == nullptr：previous = p->lchild；

若p->rtag == LINK，即結點未被後繼線索化（分支結點），但是後序遍歷的後繼是比不會存在於其左右子樹中的，所以需要藉助三叉鏈表獲取其雙親結點。

p是右孩子：則由「[左]（左右p）根」可知，next = p->parent；

p是左孩子，且沒有右兄弟：則由「（左右p）根」可知，next = p->parent；

p是左孩子，存在右兄弟：則由「（左右p）（左右根）根」可知，next = 右兄弟的左優先葉子結點；（出現左子樹向左走，否則向右）

先序線索二叉樹中序線索二叉樹後序線索二叉樹

找前驅 × √ √

找後繼 √ √ ×

【注】湖南大學866數據結構是不考察線索化的，所以重點是如何查找沒有線索化的前驅後繼。

	先序線索二叉樹	中序線索二叉樹	後序線索二叉樹
找前驅	×	√	√
找後繼	√	√	×

二叉樹的溯源問題（如何保存遍歷路徑：棧+後序！）

問題：列印出值為$x$的結點的所有祖先結點（假設值為$x$的結點最多有1個）

由於要保存所有祖先結點，所以必須使用後序遍歷，保證根結點最後訪問！

void SearchAncestors(BiTree T, ElemType x){
       // 倘若不想使用棧，則需要使用三叉鏈表的存儲結構（第三叉指向雙親節點）
       InitStack(StackOfAncestor);
       BiTree cursor, previous;
       cursor = T, previous = nullptr;
       while(cursor || !IsEmpty(StackOfAncestor)){
           // 因為我們需要將cursor壓入棧內，所以不能僅僅判斷cursor有無左孩子
           if(cursor){
               // 如果當前位置存在節點，則將其作為「雙親節點」入棧
               Push(StackOfAncestor, cursor);
               // 並指向自己的左孩子（繼續向左走）
               cursor = cursor->lchild;
           }
           else{
               // 如果當前位置不存在節點，說明向左走走到頭了，需要向右轉後者向上走（如果沒有右孩子或者已經向右轉過則不需要了）
               BiTree parent = nullptr;
               GetTop(StackOfAncestor, previous);
               // 如果右兄弟存在且沒有被訪問過，則向右轉
               if(parent->rchild!=nullptr && parent->rchild!=previous){
                   // 不判斷右兄弟是否存在會造成死循環
                   cursor = parent->rchild;
               }
               // 向上走
               else{
                   // 說明該雙親結點的左右子樹都已經訪問完成了（或者沒有孩子），所以彈出雙親節點
                   Pop(StackOfAncestor, parent);
                   // 訪問「根」（也就是雙親結點）
                   if(parent->data == x){
                       printf("所查結點的所有祖先的值為：");
                       while(!IsEmpty(StackOfAncestor)){
                           BiTree ancestor = nullptr;
                           Pop(StackOfAncestor, ancestor);
                           printf(&(ancestor->data));
                           printf(" ");
                       }
                       // 直接退出函數體
                       exit(1);
                   }
                   // 將previous指針指向最近訪問過的雙親結點（前驅）
                   previous = parent;
                   // 為了後續操作為向右轉向（因為根節點訪問完了就代表這一整棵子樹已經訪問完成，所以需要向上向右走轉向右兄弟樹）
                   cursor = nullptr;
               }
           }
       }
}

王道給出的更簡潔的方法，但是與之前所學的後序遍歷非遞歸實現不同，換了一種棧的數據結構，並且換了一種遍歷方式：首先遍歷左子樹，與此同時訪問根結點（可以理解為利用先序遍歷節省時間，因為如果在遍歷左子樹時就找到了x，我們就能直接跳出循環了）；如果左子樹中沒有找到，就去最近的沒有被訪問過的右子樹中搜索（由於棧中保存了$\mathbf{tag}$作為對左右子樹訪問完成的標識，所以不需要用$\mathbf{previous}$指針了）。所以這很難說是嚴格的後序遍歷，不過要說是「打了小抄」或者「樂於劇透」的後序遍歷我倒是不否認。

typedef struct{
       BiTree bt;
       int tag; // 值為0表示左孩子已經被訪問，值為1表示右孩子已經被訪問
}Stack;

void Search(BiTree bt, char x) {
       Stack s[10]; //棧容量足夠大 
       int top = 0;
       while (bt != nullptrptr || top > 0) {
           // 首先遍歷左子樹，這裡訪問根結點：bt->data != x（打個小抄，劇透一下）
           if (bt != nullptrptr && bt->data != x) {
               // 如果恰好x出現在左子樹中我們就能跳過之後的遍歷了
               s[++top].bt = bt;
               s[top].tag = 0;
               bt = bt->lchild;
           }
           else
           {
               // 如果在左子樹中找到了x結點（並不是在訪問「根結點」）
               if (bt && bt->data == x) {
                   printf("所查結點的所有祖先結點的值為∶\n");
                   for (i = 1; i <= top; i++)
                       printf("%c", s[i].bt->data);
                   exit(1);
               }
               // 繼續在右子樹中搜索x結點
               else
               {
                   // 如果右孩子被訪問了則返回到：最近的、沒有訪問右孩子的結點處
                   while(top != 0 && s[top].tag == 1)
                       top--;
                   // 如果沒有退到根結點，表示還可以繼續向右執行
                   if(top != 0) {
                       s[top].tag = 1;
                       bt = s[top].bt->rchild;
                   }
               }
           }
       }
}

尋找指定兩個結點的最近公共祖先結點

問題：設一棵二叉樹的結點結構為$(\mathbf{lchild}，\mathbf{info}，\mathbf{rchild})$，$\mathbf{root}$為指向該二叉樹根結點的指針，$p$和$q$分別為指向該二叉樹中任意兩個結點的指針，試編寫演算法$\mathbf{Ancestor}(\mathbf{root},p,g,r)$，找到$p$和$q$的最近公共祖先結點$r$。

由（g）可知此問題可以被轉化為求兩個棧的第一個公共元素。故核心思想為：採用後序遍歷的方式在棧中保存所有「根結點」。找到$p$結點後將當前棧中所有元素複製到另一輔助棧中，然後繼續尋找$q$結點。最後比較兩個棧中的元素，第一個匹配（相等）的即是$p$、$q$結點的最近公共祖先結點$r$。

typedef struct{
       BiTree bt;
       int tag; // 值為0表示左孩子已經被訪問，值為1表示右孩子已經被訪問
}Stack;
// 棧的深拷貝
void StackCopy(Stack s1[], int tops1, Stack s2[], int& tops2){
       for(int i=0; i<=tops1; i++){
           s2[i] = s1[i];
       }
       tops2 = tops1;
}
// 尋找兩個棧的第一個公共元素
BiTree SearchFirstPublicElem(Stack s1[], int tops1, Stack s2[], int tops2){
       for (int i1 = tops1; i1 > 0; i1--) {
           for (int i2 = tops2; i2 > 0; i2--) {
               if (s1[i1].bt == s2[i2].bt) {
                   return s1[i1].bt;
               }
           }
       }
       return nullptr;
}
Stack s[10], auxs[10] // 定義棧和輔助棧

BiTreeNode* SearchNearestPublicAncestor(BiTree root, BiTreeNode* p, BiTreeNode* q){
       // 定義流程式控制制變數：控制棧的拷貝
       bool isTwiceFind = false;
       // 定義兩個棧的棧頂游標
       int tops, topauxs;
       // 將根結點入棧
       BiTreeNode* cursor = root;
       // 索引為0的位置不用（與數據結構吻合）
       tops = topauxs = 0, s[++tops] = cursor;
       // 如果沒到盡頭，或者棧非空，則繼續循環
       while(cursor != nullptr || tops > 0){
           // 首先在左子樹中尋找p結點和q結點，並「劇透一下」
           if(cursor != nullptr && cursor != p && cursor != q){
               s[++tops].bt = cursor;
               s[tops].tag = 0;
               cursor = cursor->lchild;
           }
           else{
               // 如果在左子樹中找到了p結點或者q結點
               if(cursor != nullptr){
                   // 第一次找到p或者q，則拷貝棧中元素
                   if(!isTwiceFind){
                       StackCopy(s,tops,auxs,topauxs);
                       isTwiceFind = true;
                       // 回到開始的if繼續在左子樹中搜索
                   }
                   // 第二次找到p或者q，則尋找兩個棧中的最近公共祖先結點
                   else{
                       return SearchFirstPublicElem(s,tops,auxs,topauxs);
                   }
               }
               // 如果兩個結點都沒有在左子樹中找到，則去右子樹中搜索
               else{
                   // 退回至最近的、沒有被訪問右子樹的「根結點」
                   while(tops != 0 && s[tops].tag == 1){
                       tops--;
                   }
                   // 如果沒有退回到根結點，則繼續向右子樹中尋找
                   if(tops != 0){
                       BiTreeNode* parent = s[tops].bt;
                       cursor = parent->rchild;
                   }
               }
           }
       }
}

求先、中和後序遍歷序列中的第$k(1\le k\le n)$個結點的值

先序遍歷

先序遍歷的思想是「根左右」，當根結點不是$\mathbf{KNode}$時，我們在左右子樹中搜索。先在左子樹中搜索$\mathbf{KNode}$，如果存在則返回k，不再繼續搜索右子樹；否則返回其左子樹最後一個被先序遍歷的結點的編號，然後轉向其右子樹進行搜索，如果搜索到了則返回k。否則表明左右子樹中也沒有搜索到，則返回至雙親結點並在下一棵樹中搜索$\mathbf{KNode}$。

// cursor表示當前節點在先序遍歷中的序號（初始值為0）
int FindKNode_Pre1(BiTree T, int cursor, int k, BiTree& KNode){
       if(T != nullptr){
           // 在根結點處搜索
           if(++cursor == k){
               KNode = T;
               // 趕緊return，不再進入子樹中搜索（節約時間）
               return cursor;
           }

           // 繼續向左走並記錄左子樹最後一個被遍歷的結點的編號
           cursor = FindKNode_Pre(T->lchild, cursor, k, KNode);
           // 在左子樹中找到了，則向上一直返回k，不再遍歷其右子樹；
           if(cursor == k){
               return k;
           }

           // 左子樹全部走完之後都沒有找到，則向右走在右子樹中搜索；
           else{
               return FindKNode_Pre(T->rchild, cursor, k, KNode);
           }
           // 如果k>n則會將樹完全遍歷，不會產生無限遞歸
       }
       else{
           // 返回到其雙親結點
           return cursor;
       }
}

// 方法二：王道的解法。思想是差不多的，只不過我是將left==k作為標記，而王道則是重新創造了一個#作為標記，這樣更加簡潔
int i = 1;
char FindKNode_Pre2(BiTree T, int k){
       if (!T)
           return '#';
       if (i == k)	// 如果是第k個，則返回該節點的值
           return T->data;
       i++;
       char ch = FindKNode_2(T->lchild, k);
       // 如果不是空結點表示在左子樹中找到了KNode，否則在右子樹中繼續搜索
       return ch != '#' ? ch : FindKNode_2(T->rchild, k);
}

中序遍歷（二叉查找樹的第k個結點）

// cursor表示當前節點在中序遍歷中的序號（初始值為0）
int FindKNode_In1(BiTree T, int cursor, int k, BiTree& KNode) {
       if (T != nullptrptr) {
           // 先在左子樹中搜索，並記錄左子樹在中序遍歷中的最後一個結點編號
           cursor = FindKNode_In(T->lchild, cursor, k, KNode);
           // 如果在左子樹中搜索到了則向上返回k，
           if (cursor == k) {
               return k;
           }

           // 左子樹中沒有找到，搜索根結點和右子樹
           else {
               // 搜索根結點，如果根結點是KNode則返回
               if (++cursor == k) {
                   KNode = T;
                   return cursor;
               }

               // 否則繼續向右子樹中搜索KNode
               else {
                   return FindKNode_In(T->rchild, cursor, k, KNode);
               }
           }
       }
       else {
           return cursor;
       }
}

// 方法二：王道的Style
int i = 1;
char FindKNode_In2(BiTree T, int k) {
       if(!T)
           return '#';
       // 首先搜索左子樹，如果搜索到了ch!='#'
       char ch = FindKNode_In(T->lchild, k);
       if(ch != '#')
           return ch;
       // 左子樹沒有搜索到則搜索根結點
       if(++i == k)
           return T->data;
       // 根結點沒有則繼續在右子樹中搜索
       else
           return FindKNode_In(T->rchild, k);
}

後序遍歷

// cursor表示當前節點在後序遍歷中的序號（初始值為0）
int FindKNode_Post1(BiTree T, int cursor, int k, BiTree& KNode) {
       if (T != nullptrptr) {
           // 先在左子樹中搜索，並記錄左子樹在中序遍歷中的最後一個結點編號
           cursor = FindKNode_Post(T->lchild, cursor, k, KNode);
           // 如果在左子樹中搜索到了則向上返回k，否則
           if (cursor == k) {
               return k;
           }

           // 左子樹中沒有找到，搜索右子樹和根結點
           else {
               // 繼續向右子樹中搜索KNode
               cursor = FindKNode_Post(T->rchild, cursor, k, KNode);
               if(cursor == k){
                   return k;
               }

               // 左右子樹中都沒有找到
               else {
                   // 搜索根結點，如果根結點是KNode則返回
                   if (++cursor == k) {
                       KNode = T;
                       return cursor;
                   }
                   // 如果都沒有搜到則返回該根結點的序號
                   else {
                       return cursor;
                   }
               }
           }
       }
       else {
           return cursor;
       }
}

// 方法二：王道的Style
int i = 1;
char FindKNode_Post2(BiTree T, int k) {
       if(!T)
           return '#';
       // 首先搜索左子樹，如果搜索到了ch!='#'
       char ch = FindKNode_Post(T->lchild, k);
       if(ch != '#')
           return ch;
       // 左子樹沒有則繼續在右子樹中搜索
       ch = FindKNode_Post(T->rchild, k);
       if(ch != '#')
           return ch;
       // 左右子樹都沒有搜索到則搜索根結點
       if(++i == k)
           return T->data;
       // 如果都沒有找到則返回ch（其實就是'#'）
       else
           return ch;
}

【注】後序遍歷由於沒有T的非空保護，所以必須在訪問完根結點後加上：如果以該結點為根的整棵樹沒有搜索到$\mathbf{KNode}$時的返回語句。

二叉樹利用後序遍歷和層次遍歷，刪除所有以值為$x$作為根結點的子樹

使用後序遍歷遞歸地刪除結點（先刪除子樹，最後刪除根結點）

void DeleteX_PostOrder(BiTree TreeRoot){
       if(TreeRoot != nullptr){
           DeleteX_PostOrder(TreeRoot->lchild);
           DeleteX_PostOrder(TreeRoot->rchild);
           free(TreeRoot);
       }
}

使用層序遍歷確定被刪除結點以及其父節點

void DeleteX(BiTree T, ElemType x){
       // 空樹和刪除根結點，特殊處理
       if(T == nullptr){
           exit(-1);
       }
       else if(T->data == x){
           DeleteX(x);
       }
       else{
           // 創建一個輔助隊列並初始化
           Queue auxque;
           InitQueue(auxque);
           EnQueue(auxque, T);
           while(!IsEmpty(auxque)){
               BiTree rootNode = nullptr;
               DeQueue(auxque, rootNode);
               // 如果有左孩子，則將其篩查後加入輔助隊列中
               if(rootNode->lchild != nullptr){
                   // 如果左孩子是被刪除元素，則刪除整個左子樹，並將左孩子指針置空
                   if(rootNode->lchild->data == x){
                       DeleteX(rootNode->lchild);
                       rootNode->lchild = nullptr;
                   }
                   // 如果不需要被刪除，則加入輔助隊列中
                   else{
                       EnQueue(auxque, rootNode->lchild);
                   }
               }
               // 如果有右孩子，則將其篩查後加入輔助隊列中
               if(rootNode->rchild != nullptr){
                   // 如果右孩子是被刪除元素，則刪除整個右子樹，並將右孩子指針置空
                   if(rootNode->rchild->data == x){
                       DeleteX(rootNode->rchild);
                       rootNode->rchild = nullptr;
                   }
                   // 如果不需要被刪除，則加入輔助隊列中
                   else{
                       EnQueue(auxque, rootNode->rchild);
                   }
               }
           }
       }
}

二叉樹葉子結點的線性化（B+樹）

問題：設計一個演算法將二叉樹的葉結點按從左到右的順序連成一個單鏈表，表頭指針為$\mathbf{head}$。二叉樹按二叉鏈表方式存儲，鏈接時用葉結點的右指針城來存放單鏈表指針。

先序、中序和後序遍歷都是從左至右的遍歷方式，所以選哪一種都可以實現，這裡我們選擇中序遍歷。利用$\mathbf{previous}$指針指向（保存）根結點，在訪問根結點時進行線性化操作：左孩子指向根結點，根結點的右孩子不變。
// 中序遍歷
void InOrder(BiTree T, BiTreeNode*& previous, LinkList& head){
       if(T != nullptr){
           InOrder(T->lchild, previous, head);
           LinearizationLeaves(T, previous, head);
           InOrder(T->rchild, previous, head);
           // 按理來說我們需要在每一次根結點+左右子樹完成後，需要將pre.r置空，保證最後一個葉子結點的右孩子指向空（設置尾鏈），但是由於初始化就是空所以沒這個必要。
       }
}
// 線性化葉子結點
void LinearizationLeaves(BiTreeNode* node, BiTreeNode*& previous, LinkList& head){
       // 判斷是否是葉子結點，如果是則線性化
       if(node->lchild == nullptr && node->rchild == nullptr){
           // 第一個節點特殊處理
           if(previous == nullptr){
               head->data = node;
               previous = node;
           }
           else{
               previous->rchild = node;
               previous = node;
           }
       }
}
// 列印所有的葉子結點
void PrintLeaves(LinkList head) {
       ElemType cursor = head->data;
       while (cursor)
       {
           cout << cursor->data << " → ";
           cursor = cursor->rchild;
       }
       cout << "nullptr" << endl;
}
【注】連接B+樹的葉子結點的原因：當我們在使用範圍查找的時候，只要找到那個邊界值就可以通過指針去查找其他所需要的數據，就不用再從根結點開始遍歷，減少了所消耗的時間，增加了效率。

二叉樹的帶權路徑長度（WPL）

二叉樹的帶權路徑長度（WPL）是二叉樹中所有葉結點的帶權路徑長度之和。如下是數據結構：

typedef struct BiWeightNode{
       int weight;
       struct BiWeightNode* lchild, * rchild;
}BiWeightNode, BiWeightTreeNode, * BiWeightTree;

先序遍歷遞歸求解

如果是葉子結點就直接返回WPL，否則進入左右子樹分別計算其權值，每次進入子樹，$\mathbf{depth}$都需要加一層。

int WPL_PreOrder(BiWeightTree BWT, int depth = 0) {
       // 如果是葉子結點則結算WPL（葉子結點有返回處理，所以不需要BWT的非空保證）
       if (BWT->lchild == nullptr && BWT->rchild == nullptr) {
           int leaveWeight = BWT->weight * depth;
           return leaveWeight;
       }
       else {
           int childTreeWeight = 0;
           // 如果存在左子樹，則計算左子樹的WPL
           if (BWT->lchild != nullptr) {
               childTreeWeight+=WPL_PreOrder(BWT->lchild, depth+1);
           }
           // 如果存在右子樹，則計算右子樹的WPL
           if (BWT->rchild != nullptr) {
               childTreeWeight+=WPL_PreOrder(BWT->rchild, depth+1);
           }
           return childTreeWeight;
       }
}

層次遍歷非遞歸求解

就是利用輔助隊里實現層次遍歷。

int WPL_LevelOrder(BiWeightTree BWT) {
       // 父層結點的深度，帶權路徑長度，父層最右端結點的編號，子層已入隊的數量
       int depth, wpl, lastNodeOrder, count;
       depth = 0, wpl = 0, lastNodeOrder = 0, count = 0;
       SeqQueue auxque;
       auxque.front = auxque.rear = -1;
       auxque.que[++auxque.rear] = BWT;
       while (auxque.front < auxque.rear) {
           BiWeightTreeNode* parent = auxque.que[++auxque.front];
           // 如果是葉子結點則結算WPL
           if (parent->lchild == nullptr && parent->rchild == nullptr) {
               wpl += parent->weight * depth;
           }
           else {
               // 如果存在左孩子，將左孩子入隊
               if (parent->lchild != nullptr) {
                   auxque.que[++auxque.rear] = parent->lchild;
                   count++;
               }
               // 如果存在右孩子，將右孩子入隊
               if (parent->rchild != nullptr) {
                   auxque.que[++auxque.rear] = parent->rchild;
                   count++;
               }
           }
           // 父層訪問完成
           if (auxque.front == lastNodeOrder) {
               lastNodeOrder = count;
               depth++;
           }
       }
       return wpl;
}

二叉樹的中綴表達式輸出

中綴表達式當然需要藉助中序遍歷了。很顯然，需要在非根結點的分支節點兩邊加上「（）」，故而需要多傳入一個表示高度的參數。

void BiTree2Exp(BiTree T, int depth){
       if(T != nullptr){
           // 如果是葉子結點則直接輸出操作數
           if(T->lchild == nullptr && T->rchild == nullptr){
               printf("%s", T->data);
           }
           else{
               // 如果是非根結點，則需套上「()」
               if(depth > 1){
                   printf("(");
               }
               // 輸出左子樹（左操作數）
               BiTree2Exp(T->lchild, depth + 1);
               // 輸出根結點（操作符）
               printf("%s", T->data);
               // 輸出右子樹（右操作數）
               BiTree2Exp(T->rchild, depth + 1);
               // 如果是非根結點，則需套上「()」
               if(depth > 1){
                   printf(")");
               }
           }
       }
}

樹和森林的(左)孩子(右)兄弟表示法
1. 分支結點數
問題：已知一棵有$n$個結點的樹，其葉結點個數是$n_0$，該樹對應的二叉樹中無右孩子的結點個數？

顯然該問題是問樹中沒有右兄弟的結點數，而當前層沒有右兄弟的結點就是同父結點的最右端結點（一個父節點對應一個無右兄弟結點），這也就是說父層有多少個分支結點就會造成子層有多少個無右兄弟結點。逐層累加後，考慮到根結點由於沒有右兄弟，所以需要額外加1。最後的表達式為：

\[樹和森林中無右兄弟結點數=分支結點數+1=總結點數-葉結點數+1=n-n_0+1
\]
1. 葉子結點數
左孩子右兄弟，表明只要有孩子就一定有左指針，沒有孩子就沒有左指針。故得出結論：

\[樹和森林中的葉子結點數=二叉樹中左孩子指針為空的結點個數=子樹空左+兄弟空左
\]
```
int CountOfLeaves(CNTree CNT){
       if(CNT == nullptr){
           return 0;
       }
       else if(CNT->fch == null){
           return 1 + CountOfLeaves(CNT->nsib);
       }
       else{
           return CountOfLeaves(CNT->fch) + CountOfLeaves(CNT->nsib);
       }
}
```
1. 樹的深度
\[樹的深度=\max{(子樹深度+1，右兄弟樹深度)}
\]
```
int Depth(CNTree CNT){
       if(CNT == nullptr){
           return 0;
       }
       else{
           int fchDepth, nsibDepth;
           fchDepth = Depth(CNT->fch);
           nsibDepth = Depth(CNT->nsib);
           return Max(fchDepth+1, nsibDepth);
       }
}
```
1. $樹的XX=孩子兄弟二叉樹的YY=F(左子樹的YY，右子樹的YY)$
1. 二叉樹的各類型結點個數；
2. 二叉樹的深度（高度）；
3. 樹的分支結點和葉子結點個數；
4. 樹的深度（高度）；
1. 樹、森林和二叉樹的遍歷關係
樹森林二叉樹

先根遍歷先序遍歷先序遍歷

後根遍歷中序遍歷中序遍歷

樹的後序遍歷：長子→次子→……→最右孩子→根結點→右兄弟→……→最右兄弟→父節點；

二叉樹中序遍歷：左子樹（孩子）→根結點→右子樹（兄弟）；
1. 如何通過樹的層序序列和結點度數構造孩子兄弟鏈表
任一結點的第一個孩子被其左指針指向，其他從2開始知道度數為止的孩子用右指針串起來。
```
#define MAX_SIZE 100
void CreateCNBiTree(CNBiTree& CNBT, ElemType levelOrder[], int degree[]){
       // 數據的層序序列轉化為結點的層序序列
       CNBiTree cnbts[MAX_SIZE];
       for(int i=0; i<n; i++){
           // 初始化數據和指針
           cnbts[i]->data = levelOrder[i];
           cnbts[i]->fch = cnbts[i]->nsib = nullptr;
       }
       // 長子的序號為k
       int k = 1;
       // 按照規則構建孩子兄弟鏈表
       for(int i=0; i<n; i++){
           d = degree[i];
           if(d != 0){
               // 連接長子結點
               cnbts[i]->fch = cnbts[k];
               // 循環將長子的所有的右兄弟串起來
               for(int j=1; j<d; j++){
                   // [k] ~ [k+d-1]
                   cnbts[k+j-1]->nsib = cnbts[k+j];
               }
               // k指向下一個根結點的長子
               k += d;
           }
       }
       CNBT = cnbts[0];
}
```

樹	森林	二叉樹
先根遍歷	先序遍歷	先序遍歷
後根遍歷	中序遍歷	中序遍歷

二叉排序樹

如何判斷一棵樹是二叉排序樹

利用中序遍歷二叉排序樹可以得到一條完美的遞增序列，也就是每一個前驅都必須小於後繼。可以參考如何中序線索化一個二叉樹。

bool IsBST(BiTree root, BiTree& previous){
       if(root == nullptr){
           return true;
       }
       else{
           // 判斷左子樹是否是BST
           bool lchild = IsBST(root->lchild, previous);
           if(!lchild){
               return lchild;
           }
           // 訪問第一個中序結點時，移動前驅指針
           if(previous == nullptr){
               previous = root;
               return true;
           }
           else{
               // 如果前驅 > 後繼，則不是BST
               if(previous->data > root->data){
                   return false;
               }
               // 否則繼續移動前驅指針，並判斷右子樹是否為BST
               else{
                   previous = root;
                   return IsBST(root->lchild, previous);
               }
           }
       }
}

利用二叉排序樹查找所有$\ge k$的結點，並從大到小排列

如果該節點$\ge k$，則輸出該節點和其右子樹，並向左孩子移動，遞歸進行上述判斷直到有結點$\lt k$。

// 由於是從大到小輸出，所以我們先遍歷右子樹（右根左）
void Output(BiTree root, ElemType k){
       if(root == nullptr){
           return;
       }
       else{
           Output(root->rchild, k);
           if(root->data >= k){
               printf(&root->data);
           }
           Output(root->lchild, k);
       }
}

平衡二叉樹

四種失衡類型以及解決方法（自底向上）

LL型失衡（左孩子的左子樹+1）

失衡結點的L孩子作為新的祖先結點；

L孩子的R子樹作為失衡結點的L子樹；（右旋）

RR型失衡（右孩子的右子樹+1）

失衡結點的R孩子作為新的祖先結點；

R孩子的L子樹作為失衡結點的R子樹；（左旋）

LR型失衡（左孩子的右子樹+1）

失衡結點的LR孩子作為新的祖先結點；

LR孩子的L子樹作為L孩子的R子樹；（左旋）

LR孩子的R子樹作為失衡結點的L子樹；（右旋）

RL型失衡（右孩子的左子樹+1）

失衡結點的RL孩子作為新的祖先結點；

RL孩子的R子樹作為R孩子的L子樹；（右旋）

RL孩子的L子樹作為失衡結點的R子樹；（左旋）

總結刪除結點後再插入後AVL樹的變化

不管刪除再插入的結點是葉子結點還是分支結點，AVL樹都可能不變或者改變。

最少結點個數$N_h$與高度$h$的關係

假設高度為$h$的平衡二叉樹最少需要$N_h$個節點（左+右+根），則有遞歸公式：

\[N_h=N_{h-1}+N_{h-2}+1，其中N_0=0, N_1=1
\]

由三項遞推公式（特徵方程$x^2=x+1$）可得：

\[N_h=(1+\frac{2}{\sqrt{5}})\cdot(\frac{1+\sqrt{5}}{2})^h+(1-\frac{2}{\sqrt{5}})\cdot(\frac{1-\sqrt{5}}{2})^h-1
\]

所以可以解得$N_h$與$h$的關係為：

\[h\lt \log_{\frac{1+\sqrt{5}}{2}}{(N_h+1)}\lt \frac{3}{2}\log_2{(N+1)}
\]

所以我們又可以推出平衡二叉樹的平均查找長度為：$O(H)=O(\log_2N)$；

如何判斷一棵樹是否是平衡二叉樹
自底向上地判斷左右子樹是否是平衡二叉樹，如果有一顆不是則整棵樹就不是平衡的；如果兩棵樹都是平衡二叉樹，則計算左右子樹的樹高差，判斷該棵樹是否平衡。
bool IsBalanced(BiTree root, int& height){
       // 如果是空結點，則高度為0，平衡
       if(root == nullptr){
           height = 0;
           return true;
       }
       // 如果只有根結點，則高度為1，平衡
       else if(root->lchild == nullptr && root->rchild == nullptr){
           height = 1;
           return true;
       }
       else{
           bool isBalanced = true;
           // 判斷左子樹是否平衡，並記錄左子樹的高度
           bool lchildBalanced = IsBalanced(root->lchild, height);
           isBalanced &&= lchildBalanced;
           int lchildHeight = height;
           // 判斷右子樹是否平衡，並記錄右子樹的高度
           bool rchildBalanced = IsBalanced(root->rchild, height);
           isBalanced &&= rchildBalanced;
           int rchildHeight = height;
           // 左右子樹最高者+1為該棵樹的高度，並判斷該棵樹是否平衡
           height = Max(lchildHeight, rchildHeight) + 1;
           isBalanced &&= Abs(lchildHeight-rchildHeight)<=1;
           return isBalanced;
       }
}
求出指定結點的所在的層次
前序遍歷（找結點 + 二叉排序樹特性）。
// 遞歸演算法
int AtLevel(BiTree root, ElemType x, int level){
       // 如果遇到了空結點，表明這個分支中不存在x結點
       if(root == nullptr){
           return 0;
       }
       else{
           // 在根結點中搜索
           if(root->data == x){
               return level;
           }
           // 在左子樹中搜索
           else if(root->data > x){
               return AtLevel(root->lchild, x, level+1);
           }
           // 在右子樹中搜索
           else{
               return AtLevel(root->rchild, x, level+1);
           }
       }
}
// 非遞歸演算法
int AtLevel(BiTree root, ElemType x){
       int level = 1;
       while(root != nullptr){
           if(root->data == x){
               return level;
           }
           else if(root->data > x){
               root = root->lchild;
           }
           else{
               root = root->rchild;
           }
           level++;
       }
       return 0;
}

霍夫曼樹（2路歸併）
1. 帶權路徑長度
與「平均查找效率（時間）(ASL)」相區別。ASL指的是「查找結點的平均對比次數」，所以是結點的深度；而「帶權路徑長度(WPL)」指的是「從根結點出發到該結點的帶權長度」，所以是經過的邊數。
1. 是否為前綴編碼，就看能不能構造霍夫曼樹
2. 霍夫曼樹（k路歸併的度為k）中有結點個數之間的關係
\[\begin{cases}
n_0+n_k=n；
\\
n_0=n_k+1；
\end{cases}
\Longrightarrow
\begin{cases}
n_0=\frac{n+1}{2}；
\\
n_2=\frac{n-1}{2}；
\end{cases}
\]

假設有m個結點需要k路歸併h次，形成一棵度為k的霍夫曼樹，則有如下等式成立：

\[\begin{cases}
非葉子結點數=k路歸併次數=樹高-1；
\\
k路歸併次數=⌈\frac{m-1}{k-1}⌉；
\\
葉子結點數=原始結點個數=m；
\end{cases}
\]

求k路歸併次數就像我們小學時候求「青蛙跳井」一樣（一隻青蛙逃出高為m米的井，每次向上跳k米，但是會下滑1米），每一次歸都會將k個葉子結點歸併為一個非葉子節點，相當於青蛙先跳k米然後下滑1米，最後將不到k個的剩餘結點($m_{剩}$)一起合併完^[1]，故得：

\[\begin{aligned}
\small{m=「井的高度」=(h-1)\times(k-1)+m_{剩}(\le k)=(h-1)\times(k-1)+m^′_{剩}(\le k-1)+1}
\end{aligned}
\]

即有$k$路歸併次數$h$的計算公式：

\[h=\frac{m-1-m^′_剩}{k-1}+1\ge\frac{m-1}{k-1}\Longrightarrow 即有：h=⌈\frac{m-1}{k-1}⌉
\]

【注^[1]】其中有$m^′_剩$個葉子結點和1個非葉子結點。
1. 如何判斷編碼集有無前綴編碼的特性
構建一棵樹，然後從左自右遍歷編碼集的各位，遇到0則樹中的游標向左指針移動，遇到1則向右指針移動，（1）遇到空結點則創建新結點；（2）如果遇到葉子結點，則說明有其他編碼作為該編碼的前綴；（3）如果從始至終沒有創建結點，則說明該結點是某個其他編碼的前綴；

Tags: 22考研