【数据结构】二叉树、普通树、森林的定义与应用,数据结构完全二叉树的定义

摘要：

有两种表示：高度为（h）的完整二叉树最多有节点，因此；高度为（h）的完整二叉树至少有节点，因此\（n）每个节点对应于度，这意味着边；二叉树的和点与每种类型的节点数之间的关系[开始{情况}n＝n_0+n_1+n2 n＝0时间n_0+1时间n_1+2时间n_2+1结束{情况｝长右箭头n_0=n2+1]高度为（h）的霍夫曼树具有节点高度为（h）的节点，并且只有度为0和度为2的节点，那么这种二叉树至少包含节点。“˂˂endl；exit；}}完整的二叉树的高度等于具有（n）个节点的完整二叉树或；完整的二元树不能具有非空节点boolIsComplete（B

<body>

普通$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）如果从始至终没有创建结点，则说明该结点是某个其他编码的前缀；

</body>

【数据结构】二叉树、普通树与森林的定义与应用

普通\(m\)叉树的性质（普通二叉树也满足）

各层的最大结点个数

高度为h的\(m\)叉树最多结点个数

具有\(n\)个结点的\(m\)叉树至少有多高

\(n\)个结点对应\(n-1\)度，也就有\(n-1\)条边；

二叉树的常考性质（\(n\)为总结点数，\(n_i\)为度为\(i\)的结点数）

二叉树总结点数与各类型结点数的关系

高度为\(h\)的霍夫曼树有\(2h-1\)个结点

计算二叉树各种类型的节点的个数

双分支结点

单分支结点

叶子结点

完全二叉树常考性质

完全二叉树中各类型结点的个数

完全\(m\)叉树编号的性质

编号\(i\)的首个孩子结点（若存在）的编号

编号为\(i\)的结点的第\(k\)个孩子结点（若存在）的编号

编号为\(i\)的结点的双亲结点（若存在）的编号

编号为\(i\)的结点有右兄弟的条件，以及该右兄弟结点的编号

总数为\(n\)个结点的\(m\)叉树中叶子结点的个数

已知两结点的编号求最近的公共祖先

完全二叉树的高度

完全二叉树的判定

满二叉树确定二叉链表的结构

先序遍历序列唯一确定

后序遍历序列唯一确定

层序遍历序列唯一确定

其中先序和后序的转化是最简单的

二叉树遍历的应用

求二叉树树高

递归算法（后序遍历）

非递归算法（层序遍历+辅助队列）

求二叉树树宽

递归算法（先序遍历+辅助数组）

非递归算法（层序遍历+辅助队列）

遍历序列确定二叉链表（思想是重点）

先中序列

后中序列

层中序列

总结（给啥序列就按照啥规则办事）

先序、中序和后序线索二叉树的构造

递归算法（树的递归特性）

非递归算法（用辅助栈实现非递归的遍历）

先中后序遍历查找的前驱后继（手算的方法）

先序遍历查找前驱后继（需要三叉链表获取双亲结点）

中序遍历查找前驱后继

后序遍历查找前驱后继（需要三叉链表获取双亲结点）

二叉树的溯源问题（如何保存遍历路径：栈+后序！）

寻找指定两个结点的最近公共祖先结点

求先、中和后序遍历序列中的第\(k(1\le k\le n)\)个结点的值

先序遍历

中序遍历（二叉查找树的第k个结点）

后序遍历

二叉树利用后序遍历和层次遍历，删除所有以值为\(x\)作为根结点的子树

二叉树叶子结点的线性化（B+树）

二叉树的带权路径长度（WPL）

先序遍历递归求解

层次遍历非递归求解

二叉树的中缀表达式输出

树和森林的(左)孩子(右)兄弟表示法

分支结点数

叶子结点数

树的深度

\(树的XX=孩子兄弟二叉树的YY=F(左子树的YY，右子树的YY)\)

二叉树的各类型结点个数；

二叉树的深度（高度）；

树的分支结点和叶子结点个数；

树的深度（高度）；

树、森林和二叉树的遍历关系

如何通过树的层序序列和结点度数构造孩子兄弟链表

二叉排序树

如何判断一棵树是二叉排序树

利用二叉排序树查找所有\(\ge k\)的结点，并从大到小排列

平衡二叉树

四种失衡类型以及解决方法（自底向上）

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

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

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

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