5-树、森林的性质总结
几种常考的二叉树
满二叉树
就是常见的二叉树，除了叶节点外，每个结点都是有两个分支的，这种二叉树也是最好计算的。
& 1.已知树高求结点总数：sum = 2^h-1\\
& 2.已知编号i求双亲：(i/2)向下取整\\
& 3.已知编号i求两个儿子：左孩子2i，右孩子2i+1\\
\end{aligned}$$
### 完全二叉树
> 这种二叉树是少了一些结点的满二叉树，每个几点的编号都都跟1~n一一对应，也就是说，只允许在右屁股部分缺少一些叶子节点，注意，少也是少叶子节点。
.969t9t3wv9.webp)
上述就是一个完全二叉树的例子，需要注意，因为是1~n，所以要缺少也只能是缺少右边屁股的叶子结点，如果一颗完全二叉树有度为1的节点，那么有且只有一个，如上上述的3号结点。
### 二叉排序树
> 以根节点为比较标准，左边的全部结点均小于根节点，右边的全部结点均大于根节点，左右子树又各自为二叉排序树。
可以从性质发现，要找最小的结点，只需去找左子树的最左叶结点即可。同理最大结点在右子树的最右叶结点。
### 平衡二叉树
> 树中任意一个结点的左子树和右子树的深度之差不超过1
### 二叉树数据结构代码实现
**1）顺序存储**
```cpp
typedef struct Node{
int data;
int isEmpty;
}TreeNode;
void Init(TreeNode T[],int len){
for(int i = 0;i<len;i++){
t[i].isEmpty = 1;
}
}
```
```cpp
bool isEmpty(T[],int x){
if(x>=len || x<1){return ture};
else{
return fasle;
}
}
//找到父节点
int findparent(T[],int x){
if(isEmpty(x) || x = 1)return 0;
else{
index = x/2;
if(isEmpty(index))return 0;
esle return index;
}
}
//找右孩子
int findright(T[],int x){
if(isEmpty(x) || x = 1)return 0;
else{
right = 2x + 1;
if(isEmpty(right))return 0;
esle return right;
}
}
//找左孩子
int findleft(T[],int x){
if(isEmpty(x) || x = 1)return 0;
else{
left = 2x;
if(isEmpty(left))return 0;
esle return left;
}
}
//这里的代码都是按照其实结点从1开始的，如果是0开始的还要进行改变
```
```cpp
void PreSearch(T[],int index){
if(isEmpty(index))return ;
esle{
visit(T[index]);
PreSearch(T[],2*index);
PreSearch(T[],2*index + 1);
}
}
//后序跟中序只需要调换顺序即可
```
## 二叉树性质
1、非空二叉树的叶结点等于度为2的结点数加1，即n0= n2 + 1
2、二叉树第k层上最多有2k-1 个结点
3、高度为k的二叉树最多有2k -1个结点
4、对于结点i(i>1)的编码：
$$\begin{aligned}
& 1.若i为偶数则双亲为i/2向下取整 \\
& 2.若i为奇数则双亲为(i-1)/2 \\
& 3.2i \le n时，i的左孩子是2i \\
& 4.2i+1 \le n时，i的右孩子是2i+1 \\
\end{aligned}$$
5、求树高
$log_2(n+1)向上取整，或者是log_2(n)向上取整+1$
## 树和森林
### 树和二叉树的转换
**“左指针串糖葫芦法”**
每个结点左指针指向他的第一个孩子，右指针指向它在树中的相邻右兄弟，左孩子右兄弟规则，构造后的整体看起来就是根节点出发将孩子串了起来，由于这个规则，这是一颗没有右子树的二叉树。
.83a3yx8fu3.webp)
### 森林转二叉树
**”孩子兄弟表示“**
将森林里面的树都变成二叉树，每个根节点都是兄弟，将第一个根节点作为二叉树的根节点，剩下的二叉树都依次接到右子树中。
.7pd1kn253.webp)
**森林转二叉树**
摘下第一个右子树，根节点跟左子树就是第一颗树的二叉树，其剩下的右子树又可以依次进行拆解，直到没有右子树为止。
### 二叉树遍历的对应关系
| **树** | **森林** | **二叉树** |
| --- | --- | --- |
| 先根 | 先序 | 先序 |
| 后根 | 中序 | 中序 |
### 代码实现树、森林
如下是三种实现的数据结构：双亲表示法、孩子表示法、孩子兄弟表示法
.2oblghufvq.webp)
**1）双亲表示法（顺序存储）**
每个结点都设计一个伪指针指向自己的父亲
```cpp
typedef struct Node{
int data;
int parent;
}Node*;
Node n[maxsize]；
for(int i = 0;i < maxsize;i++)
n[i].parent = -1;
```
**2)孩子表示法**
如上图所示，每个结点后都会串着一串孩子链表
```cpp
typdef struct Node{
int data;
struct Node * next
}Child; //对应的是左边的结构，也是一个头的开始
typedef struct Tree{
ElmentType data;
Child *firstChild;
}*TreeList;
//树节点
```
**3）孩子兄弟表示法**
```cpp
typedef struct Node{
int data;
struct Node* leftchild,nextsibling; //分别指向左边第一个孩子，和右边的兄弟
}*Tree;
```
## 考试选择盲猜
### 完全二叉树求结点
给出完全二叉树的总结点数，求解叶结点数。对于这种问题可以如下求解：
> 估计倒数第二层，根据估算求出最后一层有多少个叶结点，反过来求解用了上一层多少个结点，再计算上一层剩下的叶结点数，加上最后一层的结点数即可，数目大设x求解
给完全二叉树的叶结点个数，求解结点数最多的情况，求解：
:::success
对于这种问题求解，就要考虑完全二叉树的性质，其缺少，只能是缺少右边屁股的叶结点。估计出合适的层次范围(倒数第二层)，然后裂解到最后一层，根据叶结点个数进行分布，计算。**注意看看能不能多分裂出来一些，但是叶子结点数仍然不变的情况，这里不要直接死算第一步就结束了，要记得画图观察观察。**
:::
### 树高问题
给定结点数求树高最大最小的问题：
:::warning
满二叉树的情况下树就是最矮的，反之每一层都有一个度为1的结点时，树最高
:::
.1lbw5lyxum.webp)
### 右节点（右指针域）为空问题
1.题目给定树的总节点数目n，和转换后的二叉树叶节点数目m，求解
:::warning
首先要搞清楚谁的右节点(右指针域为空)，对于树来说，转换后的二叉树根节点的右指针域肯定是空的，然后是根节点下来每一个分支都会到最右边的指针域为空。所以右节点的右指针域为空的总数为：非终端结点数+1，二叉树的非终端结点数为：n-m，所以总数为n-m+1
:::
2.对于森林的也是如此，森林先转二叉树然后合并，过程是一样的，求解方法一样。