【软考】数据结构与算法基础 - 非线性结构（树与二叉树）

- 日理万妓 2024-03-22 06:08 53阅读 0赞

## 一、树的基本概念 ##

![在这里插入图片描述][c0b2be1d0e1e42ce9d2ed89aed928010.png]

结点：图中的1、2、3…数字圆形都表示结点，  
结点的度：指一个结点所有的孩子结点数(如结点1的度就是2,结点3的结点度即为1)，  
树的度：即一个树当中，结点的度最高的那个结点的度数；  
叶子结点：如7、8等没有孩子结点的结点都称之为叶子结点；  
分支结点：即有分支的结点  
内部结点：非叶子结点又非根节点(最上面的那个结点)  
父节点和子节点：这是一个相对概念，如2就是4的父节点，4就是2的子节点  
兄弟结点：同属于一个父节点的子节点间称之为兄弟结点  
层次：行数即为层次，该图中的层次即为4

## 二、满二叉树与完全二叉树(特殊的二叉树) ##

### 2.1 满二叉树的概念 ###

整个树可以构成一个完成的三角形即为满二叉树

### 2.2 完全二叉树的概念 ###

最后一行的叶子结点的父节点必须要有兄弟结点且它要么也是叶子结点要么只有一个结点且该结点和最后一行的叶子结点紧挨着

### 2.3 二叉树的重要特性 ###

![在这里插入图片描述][57d452e548334d949470fe0f7ff3c549.png]

## 三、二叉树遍历 ##

参考文章：待提供

## 四、反向构造二叉树(重点考察) ##

### 4.1 概念 ###

知道二叉树的遍历序列，然后反向推出二叉树的构造

### 4.2 例题 ###

![在这里插入图片描述][02239e1b40cc4761a98f5cf7b9941865.png]  
图注：解题方法-是标注根节点，然后推左右结点  
![在这里插入图片描述][fef90aed4c1e494e9da4702da31c1157.png]

## 五、树转二叉树 ##

由于树的应用主要是二叉树的应用，所以我们需要将树转化为二叉树  
1.树转二叉树的基本原则：某个结点的孩子结点都会成为它的左子树结点，某个结点的兄弟结点都会成为它的右孩子结点  
2.树转二叉树的例题  
![在这里插入图片描述][f9b2d96da65e471d86fe958895d29e71.png]

## 六、查找二叉树(一类特殊的二叉树) ##

### 6.1 概念 ###

(每一个)根节点的左子树结点的键值都小于根节点，根节点的右子树结点都大于根节点的一类二叉树即被称之为查找二叉树(或排序二叉树)

### 6.2 价值 ###

这种二叉树能极大的提高查询的效率和速度  
![在这里插入图片描述][6face5c5de78480e89cb1353518c5882.png]

### 6.3 插入运算 ###

(1)若该键值已存在，则不再插入  
(2)若查找二叉树为空树，则以欲插入的新结点为查找二叉树  
(3)将要插入结点键值与插入后父结点键值比较，就能确定新结点的位置是父结点的左子结点，还是右子结点  
4.删除结点：  
(1)若待删除结点是叶子结点，则直接删除  
(2)若待删除结点只有一个子结点，则将这个子结点与待删除结点的父结点直接连接  
(3)若待删除结点p有两个子结点，则在其左子树上，用中序遍历寻找键值最大的结点s，用结点s的值代替结点p的值，然后删除原结点s，结点s必属于上述(1)或(2)

## 七、最优二叉树(哈夫曼树) ##

> 考察哈夫曼树的构造

这种二叉树是一种工具，用于哈夫曼编码  
哈夫曼编码是一种无损压缩的方式,哈夫曼树中每一个父结点的键值都等于其子结点之和(不是子树结点);  
1.树的路径长度：即在树中指定一条路径，将路径的段数相加  
2.权：在最优二叉树中即某个叶子结点的键值(该键值将代表某个字符出现的频度)  
3.带权路径长度：分为结点和二叉树的带权路径长度，结点的带权路径长度等于路径长度乘以权，二叉树的带权路径长度即为所有结点的带权路径长度之和  
4.哈夫曼树设计的基本思想：让二叉树的带权路径长度尽可能小

## 八、线索二叉树 ##

由于二叉树中有许多结点处于空闲的状态，有许多指针并未被利用，而将其空闲资源利用起来方便遍历则是线索二叉树的由来，线索二叉树根据遍历的分类可以被分成三种线索二叉树：前序二叉树、中序二叉树、后序二叉树  
![在这里插入图片描述][7687a76b7e5144988c17a8f29bad1532.png]

图注：红线代表推出，绿线代表由来；如图一中二叉树的前序遍历为：ABDEHCFGI；

## 九、平衡二叉树 ##

> 即更为平衡、更为饱满的二叉树

### 9.1 概念 ###

任意结点的左右子树深度不能相差超过1，即每结点的平衡度(该结点的左右子树结点的深度之差)只能为-1、0或1  
![在这里插入图片描述][a01355655d0e4886960c1faefb4901f9.png]  
![在这里插入图片描述][b6077a783aa14da0b13b5710a1ae1d9b.png]

图注：图一和图二都属于排序二叉树，但图一的查询效率远低于图二，因为图一不属于平衡二叉树。而图二属于平衡二叉树

[c0b2be1d0e1e42ce9d2ed89aed928010.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/499d720d64c24078a0d7cc4e52934df5.png
[57d452e548334d949470fe0f7ff3c549.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/ce89d608676342eebc3845c92492b6d7.png
[02239e1b40cc4761a98f5cf7b9941865.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/a6840af875824fcebbd3fad79ba60093.png
[fef90aed4c1e494e9da4702da31c1157.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/c267e221baa749f49bbfcbe895fb289b.png
[f9b2d96da65e471d86fe958895d29e71.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/a1246800b4f547569682bf2b9f7dfd31.png
[6face5c5de78480e89cb1353518c5882.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/553bb48477d24cdb8738d3a4859bff36.png
[7687a76b7e5144988c17a8f29bad1532.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/d14c365da35a4553a79675d61dcc0fd8.png
[a01355655d0e4886960c1faefb4901f9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/b40de8a877f546c9b70facd548e82c73.png
[b6077a783aa14da0b13b5710a1ae1d9b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/22/4834c8a3a090477ba2aa6dcb391c7e9c.png