查找二叉树、完全二叉树、线索二叉树、最优二叉树

痛定思痛。 2023-10-01 21:38 52阅读 0赞

#### 文章目录 ####

*  前言
 *  一、查找二叉树（二叉排序树）
 *  二、完全二叉树
 *  三、线索二叉树
 *  四、最优二叉树（哈夫曼树）

--------------------

## 前言 ##

2021年上半年 软件设计师 上午试卷中有这样一道题

> 58.当二叉树的结点数目确定时，\_\_\_\_\_\_\_\_的高度一定是最小的。  
> A.二叉排序树 B.完全二叉树 C.线索二叉树 D.最优二叉树

我已此为契机，来了解一下`查找二叉树`、`完全二叉树`、`线索二叉树`、`最优二叉树`的一些相关定义（此题结尾会给出答案详解）

## 一、查找二叉树（二叉排序树） ##

> 二叉排序树的定义：  
> 1、若根结点的左子树非空时，左子树上的所有结点均要小于根节点；  
> 2、若根结点的右子树非空时，右子树上的所有结点均要大于根节点；  
> 3、根结点的左、右子树本身又各是一颗二叉排序树

二叉排序树示例如图所示：  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5Yaw5qONaGZ2_size_20_color_FFFFFF_t_70_g_se_x_16]

**删除与插入**  
**（一）插入结点**  
1、若查找二叉树为空树，则已要插入的新结点作为它的根节点  
2、如果要插入的结点已存在，则不再插入。如上图若想要插入关键字为32的结点，已经存在了，就不进行插入操作。  
3、将要插入的结点键值与插入后的父结点键值比较，如果小于则插入左子树，反之插入右子树中

**（二）删除结点**  
1、若待删除结点是叶子结点（即没有左右孩子），则直接删除。例如上图中的88,，直接删除88元素。  
2、若待删除结点只有左子树而无右子树，直接将其左孩子与待删除结点的父结点直接连接，例如：41  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5Yaw5qONaGZ2_size_20_color_FFFFFF_t_70_g_se_x_16 1]  
3、若待删除结点只有右子树而无左子树，直接将其右孩子与待删除结点的父结点直接连接，例如：66  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5Yaw5qONaGZ2_size_20_color_FFFFFF_t_70_g_se_x_16 2]  
4、若待删除结点p同时存在左、右子树，可以从其左子树选择键值最大的结点s，用结点s的值代替结点p的值，然后删除结点s，例如删除：54  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5Yaw5qONaGZ2_size_20_color_FFFFFF_t_70_g_se_x_16 3]

## 二、完全二叉树 ##

> 定义：若设二叉树的高度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h  
> 层若干结点靠左对齐，就说它是完全二叉树。

如下图所示：  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5Yaw5qONaGZ2_size_20_color_FFFFFF_t_70_g_se_x_16 4]  
上图两种都是完全二叉树，接下来我再给出**不是完全二叉树**的图，好做个对比  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5Yaw5qONaGZ2_size_20_color_FFFFFF_t_70_g_se_x_16 5]  
a和b都不满足完全二叉树的定义，a是因为第h层结点不满足左靠齐；b是因为除了第h层外，其它层结点个数结点未达到最大。

需要补充一点，满二叉树也是一颗完全二叉树，但是完全二叉树不一定是满二叉树

> **满二叉树定义**  
> 一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的深度为K，且结点总数是(2^k) -1，则它就是满二叉树。(一棵满二叉树的每一个结点要么是叶子结点，要么它有两个子结点，但是反过来不成立，因为完全二叉树也满足这个要求，但不是满二叉树)

![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5Yaw5qONaGZ2_size_16_color_FFFFFF_t_70_g_se_x_16]

## 三、线索二叉树 ##

> 定义:在二叉树的结点上加上线索的二叉树称为`线索二叉树`，对二叉树以某种遍历方式（如先序、中序、后序或层次等）进行遍历，使其变为线索二叉树的过程称为对二叉树进行线索化。

单看定义还是有点抽象，我们先来了解一下为什么要有线索二叉树呢？  
看下图中，我们发现在这颗树上存在着很懂指向null的指针（红色线），线索二叉树就是要让这些指针能够很好的运用上。  
![在这里插入图片描述][6b490fe23e104dd28f7d99ed8439163c.png_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5Yaw5qONaGZ2_size_18_color_FFFFFF_t_70_g_se_x_16]  
**在二叉树存储结构中，因为每个结点中只有指向其左、右孩子的指针，所以从任一结点触发只能找到该节点的左、右孩子。在一般情况下靠它无法直接找到该结点在某种遍历序下的前驱和后继结点。但是若想在每个结点中增加指向其前驱和后继结点的指针，将降低存储空间的效率，所以引入线索二叉树。**

**对于n个结点的二叉树，在二叉链存储结构中有n+1个空链域（证明略），利用这些空链域存放在某种遍历次序下该结点的前驱结点和后继结点的指针，这些指针称为线索，加上线索的二叉树称为线索二叉树。**

总结：线索链表解决了无法直接找到该结点在某种遍历序列中的前驱和后继结点的问题，解决了二叉链表找左、右孩子困难的问题。

根据线索性质的不同，线索二叉树可分为`前序线索二叉树`、`中序线索二叉树`和`后序线索二叉树`三种。

接下来介绍其中之一 ----- 前序线索二叉树  
![在这里插入图片描述][2a3058600da749e29188b734269f28db.png_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5Yaw5qONaGZ2_size_16_color_FFFFFF_t_70_g_se_x_16]  
前序二叉树，顾名思义，就是按照前序遍历的方式。。。其中，左子树结点的指针指向当前遍历当中的前序结点。右子树结点的指针指向当前遍历的后序结点。比方说，在前序遍历模式中，遍历的顺序是按照“根–左--右”的方式进行的，好比在上图的BDE中![在这里插入图片描述][314a3a4aeb8549438ada38c0ddcebd65.png]  
以`前序遍历`的方式，依次访问的是B、D、E。所以结点D的左孩子指针指向前序B结点，右孩子指针指向后序E结点，如上图所示。

> 记住前/中/后序遍历的口诀：“前”代表根先遍历，“中”代表根中间时刻遍历，“后”代表根最后遍历。

这样表示可能还不够直观，我们把上面前序线索二叉树的示例转换为前序遍历结果为：ABDEHCFGI  
![在这里插入图片描述][9f3e4b3edd48482499d784cd20979432.png]  
从图中可以就可以验证之前的结论，线索链表很好的解决了在某种遍历方式下查找二叉树结点的前驱和后继结点困难的问题，中序、后序线索二叉树就不展开讲了，原理都是一样的。

## 四、最优二叉树（哈夫曼树） ##

> 定义：给定N个权值作为N个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。

基本概念：  
哈夫曼树又称为最优树.  
**1、路径和路径长度**  
在一棵树中，从一个结点往下可以达到的孩子或孙子结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1。  
**2、结点的权及带权路径长度**  
若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。  
**3、树的带权路径长度**  
树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为WPL。

依旧结合图例来分别演示`树的路径长度`，`权`，`带权路径长度`，`树的带权路径长度（树的代价）`如何计算  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5Yaw5qONaGZ2_size_14_color_FFFFFF_t_70_g_se_x_16]

*  树的路径长度就是图中每一根线（每根线长为1）累加起来的长度。
 *  权就不必多说了，就是每个结点中所标记的值，就是该结点权值。
 *  带权路径长度，就是路径的长度先求出来，再乘以权值。即：带权路径长度=该结点路径长度×该结点权值。比如，结点2的带权路径长度等于=（1+1）×2=4
 *  树的带权路径长度，就是所有所有**叶子结点**的带权路径长度之和。例如上图，WPL=2×2+3×4+3×8+1×1=41。

哈夫曼树的构造  
定义  
假设有n个权值，则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、…、wn，则哈夫曼树的构造规则为：  
(1) 将w1、w2、…，wn看成是有n 棵树的森林(每棵树仅有一个结点)；  
(2) 在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；  
(3)从森林中删除选取的两棵树，并将新树加入森林；  
(4)重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。

先来一个简单一点的例子，将给定权值W=（1，3，5，7）来构造一颗哈夫曼树，按照上述的算  
首先要找到两个权值最小的节点，来构造一颗新的二叉树，如下  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5Yaw5qONaGZ2_size_11_color_FFFFFF_t_70_g_se_x_16]  
现在还剩下的权值是：4，5，7  
继续上面的操作  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5Yaw5qONaGZ2_size_11_color_FFFFFF_t_70_g_se_x_16 1]  
最终这颗树就构造完了  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5Yaw5qONaGZ2_size_15_color_FFFFFF_t_70_g_se_x_16]  
这棵树的带权路径长度为WPL=3×1+3×3+2×5+1×7=29

哈夫曼编码  
定义：哈夫曼编码(Huffman Coding)，又称霍夫曼编码，是一种编码方式，哈夫曼编码是可变字长编码(VLC)的一种。Huffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就叫做Huffman编码（有时也称为霍夫曼编码）。

使用场景：在数据通信中，经常需要将传送的文字转换为二进制字符0和1组成的二进制字符串，称这个过程为编码。显然，我们希望电文编码的代码长度最短。哈夫曼树可用于构造使电文编码的代码长度最短的编码方案。

**！！！做题时，只需要记住的一点：哈夫曼树中的左分支为0、右分支为1。则从根结点到每个叶子结点所经过的分值对应的0和1组成的序列便是该结点对应的字符的编码。这样的编码成为哈夫曼编码**

直接上题!!

> 【2021年下半年 软件设计师 上午试卷】已知一个文件中出现的各字符及其对应的频率如下表所示。采用Huffman编码，则该文件中字符a和c的码长分别为\_\_(64)A\_\_。若采用Huffman编码，则编码序列110001001101对应的字符应为\_\_(65)A\_\_。  
> ![在这里插入图片描述][19003cc313354624a950c328ff9aa725.png]  
> （64）A. 1和3 B. 1和4 C. 3和3 D. 3和4  
> （65）A. face B. bace C. acde D. fade

解题过程：  
1、先构造一颗哈夫曼树  
根据题干所给出的权值（频率）=\{45，13，12，16，9，5\}进行构造  
每次选取权值最小的两个结点构造一颗二叉树，并将根结点放入权值序列中，一直重复这个步骤即可。  
下面是最终构造出来的树↓  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5Yaw5qONaGZ2_size_16_color_FFFFFF_t_70_g_se_x_16 1]  
然后以“哈夫曼树中的左分支为0、右分支为1”规则，进行编码。  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5Yaw5qONaGZ2_size_16_color_FFFFFF_t_70_g_se_x_16 2]  
这样就可以求得每个字符的编码：a(0)，b(101)，c(100)，d(111)，e(1101)，f(1100)，从而可知编码序列“110001001101”代表的是字符“face”

在这颗树的构造上有一个容易出错的地方，一定要记得在每次构造树的时候选出两个权值最小的来构造一颗二叉树。比方说在5、9和14这颗树构造完后，还剩下的权值则为\{12，13，14，16，45\}，那么有些人会只选取12继续和14一起组成一颗二叉树，接下来的树就会变为大致这样。  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5Yaw5qONaGZ2_size_14_color_FFFFFF_t_70_g_se_x_16 1]  
一定要记得每轮选取的是最小两个，所以我们在这轮选取的应该是12和13，构造一颗12、13、25的树，在进行下一轮最小两权值的构造，以此类推，最终就能构造一颗真正的哈夫曼树！

--------------------

文章大致内容就这么多，回到开头题目，就变得很清晰了。（虽然内容已经偏题~）

> 当二叉树的结点数目确定时，\_\_完全二叉树\_\_\_的高度一定是最小的。  
> 因为，完全二叉树每层都尽量排满，因此树的高度相对其他来说一定是最小的。查找二叉树跟要插入的值大小相关，和树的高度不直接相关。线索二叉树是通过增设指针去保存结点的前驱后继关系，无法保证树的高度最小。最优二叉树是带权路径长度最短的一种二叉树，和树的高度没有必然的联系。

参考视频：https://www.bilibili.com/video/BV1xA411T7UM?p=15

参考资料：《数据结构教程（第版）》

[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5Yaw5qONaGZ2_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/f33680bbf3d44a079d1edc95f1be22f9.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5Yaw5qONaGZ2,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5Yaw5qONaGZ2_size_20_color_FFFFFF_t_70_g_se_x_16 1]: https://img-blog.csdnimg.cn/727f978623724016a9775c261744000a.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5Yaw5qONaGZ2,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5Yaw5qONaGZ2_size_20_color_FFFFFF_t_70_g_se_x_16 2]: https://img-blog.csdnimg.cn/cf4475a8353e4be9bcac47169bf014c7.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5Yaw5qONaGZ2,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5Yaw5qONaGZ2_size_20_color_FFFFFF_t_70_g_se_x_16 3]: https://img-blog.csdnimg.cn/570d3fcb9bf943149b0554072ab7513f.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5Yaw5qONaGZ2,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5Yaw5qONaGZ2_size_20_color_FFFFFF_t_70_g_se_x_16 4]: https://img-blog.csdnimg.cn/711f630e8b6a49f4baca9e4de6c88fe1.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5Yaw5qONaGZ2,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5Yaw5qONaGZ2_size_20_color_FFFFFF_t_70_g_se_x_16 5]: https://img-blog.csdnimg.cn/ed4b4d9cfdc54c1aa4324873faecd583.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5Yaw5qONaGZ2,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5Yaw5qONaGZ2_size_16_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/74c500cba2eb489b861b0c02002d846f.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5Yaw5qONaGZ2,size_16,color_FFFFFF,t_70,g_se,x_16
[6b490fe23e104dd28f7d99ed8439163c.png_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5Yaw5qONaGZ2_size_18_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/6b490fe23e104dd28f7d99ed8439163c.png?=,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5Yaw5qONaGZ2,size_18,color_FFFFFF,t_70,g_se,x_16
[2a3058600da749e29188b734269f28db.png_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5Yaw5qONaGZ2_size_16_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/2a3058600da749e29188b734269f28db.png?,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5Yaw5qONaGZ2,size_16,color_FFFFFF,t_70,g_se,x_16
[314a3a4aeb8549438ada38c0ddcebd65.png]: https://img-blog.csdnimg.cn/314a3a4aeb8549438ada38c0ddcebd65.png
[9f3e4b3edd48482499d784cd20979432.png]: https://img-blog.csdnimg.cn/9f3e4b3edd48482499d784cd20979432.png
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5Yaw5qONaGZ2_size_14_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/44bb85b8c5e14e4a944e48f0dd16de16.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5Yaw5qONaGZ2,size_14,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5Yaw5qONaGZ2_size_11_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/eca9a05afd754d7eb426f5069a572844.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5Yaw5qONaGZ2,size_11,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5Yaw5qONaGZ2_size_11_color_FFFFFF_t_70_g_se_x_16 1]: https://img-blog.csdnimg.cn/22991ff9177f4ded99af580a62344b16.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5Yaw5qONaGZ2,size_11,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5Yaw5qONaGZ2_size_15_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/f585394fe59c4af8b199c1881de73660.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5Yaw5qONaGZ2,size_15,color_FFFFFF,t_70,g_se,x_16
[19003cc313354624a950c328ff9aa725.png]: https://img-blog.csdnimg.cn/19003cc313354624a950c328ff9aa725.png
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5Yaw5qONaGZ2_size_16_color_FFFFFF_t_70_g_se_x_16 1]: https://img-blog.csdnimg.cn/ae230605be2c48348677e67dd58d7a5f.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5Yaw5qONaGZ2,size_16,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5Yaw5qONaGZ2_size_16_color_FFFFFF_t_70_g_se_x_16 2]: https://img-blog.csdnimg.cn/9898f9f75cd84358978bbb186f026501.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5Yaw5qONaGZ2,size_16,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA5Yaw5qONaGZ2_size_14_color_FFFFFF_t_70_g_se_x_16 1]: https://img-blog.csdnimg.cn/e3d4027e121542e4a198ae5d97786b2b.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA5Yaw5qONaGZ2,size_14,color_FFFFFF,t_70,g_se,x_16