【愚公系列】软考中级-软件设计师 018-数据结构（二叉树的分类）

🏆 作者简介，愚公搬代码
🏆《头衔》：华为云特约编辑，华为云云享专家，华为开发者专家，华为产品云测专家，CSDN博客专家，CSDN商业化专家，阿里云专家博主，阿里云签约作者，腾讯云优秀博主，腾讯云内容共创官，掘金优秀博主，51CTO博客专家等。
🏆《近期荣誉》：2023年华为云十佳博主，2022年CSDN博客之星TOP2，2022年华为云十佳博主等。
🏆《博客内容》：.NET、Java、Python、Go、Node、前端、IOS、Android、鸿蒙、Linux、物联网、网络安全、大数据、人工智能、U3D游戏、小程序等相关领域知识。
🏆🎉欢迎 👍点赞✍评论⭐收藏

文章目录

• 🚀前言
• 🚀一、二叉树的分类
• • 🔎1.线索二叉树
  • • 🦋1.1 案例
  • 🔎2.最优二叉树
  • • 🦋2.1 案例
  • 🔎3.查找二叉树
  • 🔎4.平衡二叉树
• 🚀感谢：给读者的一封信

🚀前言

二叉树可以根据特定的属性进行分类，以下是常见的二叉树分类：

1. 满二叉树（Full Binary Tree）：除了叶子节点，每个节点都有两个子节点。

2. 完全二叉树（Complete Binary Tree）：除了最后一层外，其它层的节点都是满的，最后一层的节点都靠左对齐。

3. 二叉搜索树（Binary Search Tree，BST）：对于每个节点，左子树上的所有节点的值都小于等于该节点的值，右子树上的所有节点的值都大于等于该节点的值。

4. 平衡二叉树（Balanced Binary Tree）：对于任意节点，它的左子树和右子树的高度差不大于1。

5. 线索二叉树（Threaded Binary Tree）：在二叉树节点中设置了指向前驱节点和后继节点的线索，可以方便地进行遍历。

6. 哈夫曼树（Huffman Tree）：用于数据压缩，根据数据出现的频率构建的二叉树，频率越高的节点离根节点越近。

7. Trie树（前缀树）：用于字符串的存储和搜索，每个节点代表一个字符串的字符，从根节点到叶子节点的路径表示一个完整的字符串。

8. B树（B-Tree）：一种平衡多路查找树，用于大规模数据的存储和检索，每个节点可以有多个子节点。

🚀一、二叉树的分类

🔎1.线索二叉树

线索二叉树是对二叉树进行加工，使其能够快速遍历所有节点。

在线索二叉树中，除了左右孩子指针，还添加了两个额外的指针：前驱指针和后继指针。这两个指针分别指向当前节点的前驱节点和后继节点。

对于一个二叉树来说，存在多种线索化方式。以下是两种常见的线索化方式：

1. 前序线索二叉树：在前序遍历过程中进行线索化。对于每个节点，先处理其前驱指针，然后处理左子树，再处理右子树，最后处理后继指针。对于树中的第一个节点，其前驱指针为空，对于树中的最后一个节点，其后继指针为空。

2. 中序线索二叉树：在中序遍历过程中进行线索化。对于每个节点，先处理其左子树，然后处理前驱指针，然后处理右子树，最后处理后继指针。对于树中的第一个节点，其前驱指针为空，对于树中的最后一个节点，其后继指针为空。

在线索二叉树中，通过前驱和后继指针，可以快速地找到节点的前驱节点和后继节点，从而实现快速遍历。

🦋1.1 案例

假设有以下二叉树：

      1
    /   \
   2     3
  / \   / \
 4   5 6   7

对这棵二叉树进行中序线索化，得到的线索二叉树如下所示：

   4 - 2 - 5 - 1 - 6 - 3 - 7

在线索二叉树中，每个节点的左右孩子指针被替换为前驱和后继指针。

在这个例子中，节点1的左前驱指针指向节点5，右后继指针指向节点6；节点2的左前驱指针指向节点4，右后继指针指向节点1；节点3的左前驱指针指向节点6，右后继指针指向节点7；节点4的左前驱指针指向节点2，右后继指针指向节点5；节点5的左前驱指针指向节点4，右后继指针指向节点1；节点6的左前驱指针指向节点1，右后继指针指向节点3；节点7的左前驱指针指向节点3，右后继指针为空。

通过线索化后的二叉树，可以快速地找到每个节点的前驱和后继节点，从而实现快速的中序遍历。

🔎2.最优二叉树

最优二叉树，也称为哈夫曼树，是一种特殊的二叉树结构，常用于编码和解码的应用中。

最优二叉树的特点是，频率高的节点离根节点较近，频率低的节点离根节点较远。通过这种方式，可以实现最小化编码的平均长度，从而达到最优的压缩效果。

构建最优二叉树的基本思路是，首先根据每个节点的权重（即出现频率）进行排序，然后选择权重最小的两个节点作为左右子节点，生成一个新的父节点，并将父节点的权重设置为左右子节点的权重之和。重复这个过程，直到所有节点构建成一棵树。

最优二叉树可以应用在哈夫曼编码中，通过树的路径来表示字符的编码，使得频率高的字符编码较短，频率低的字符编码较长，从而实现压缩数据的效果。

相关概念如下：

• 路径：树中一个结点到另一个结点之间的通路。
• 结点的路径长度：路径上的分支数目。
• 树的路径长度：根节点到达每一个叶子节点之间的路径长度之和。
• 权：节点代表的值。
• 结点的带权路径长度：该结点到根结点之间的路径长度乘以该节点的权值。
• 树的带权路径长度（树的代价）：树的所有叶子节点的带权路径长度之和。

哈夫曼树的求法：给出一组权值，将其中两个最小的权值作为叶子节点，其和作为父节点，组成二叉树，而后删除这两个叶子节点权值，并将父节点的值添加到该组权值中。重复进行上述步骤，直至所有权值都被使用完。

构造出的哈夫曼树中，所有初始给出的权值都作为了叶子节点，此时，求出每个叶子节点的带权路径长度，而后相加，就是树的带权路径长度，这个长度是最小的。

🦋2.1 案例

假设有以下节点集合：

节点A，出现的频率为5
节点B，出现的频率为3
节点C，出现的频率为2
节点D，出现的频率为1

为了构建最优二叉树，我们可以按照以下步骤进行：

1. 将节点集合按照频率从小到大进行排序，得到排序后的节点集合：D，C，B，A。
2. 从集合中选择频率最小的两个节点作为叶子节点，并创建一个新的节点作为它们的父节点，父节点的频率为子节点的频率之和。在我们的例子中，D和C被选择为叶子节点，它们的频率之和为3。
3. 将新的父节点加入到集合中，并将集合重新排序。新的节点集合为：B，A，新的父节点。
4. 重复步骤2和步骤3，直到集合中只剩下一个节点。
5. 最后剩下的节点就是构建的最优二叉树的根节点。

根据上述步骤，我们可以得到如下的最优二叉树：

    B
   / \
  C   A
 /
D

🔎3.查找二叉树

查找二叉树，也称为二叉搜索树（Binary Search Tree，BST），是一种特殊的二叉树结构，它具有以下性质：

1. 左子树上所有节点的值都小于根节点的值。
2. 右子树上所有节点的值都大于根节点的值。
3. 每个子树也必须满足上述两个性质。

由于这种特殊的性质，查找二叉树的结构非常便于查找和插入操作。当我们需要查找一个特定的元素时，可以通过比较当前节点的值与目标值的大小关系，根据二叉树的有序性质，可以在左子树或右子树中继续查找，直到找到目标元素或者遍历到叶子节点。

插入操作也非常简单，只需要在合适的位置创建一个新的节点，并调整树的结构以保持其有序性。

对于查找二叉树的时间复杂度，最好的情况下是O(logn)，最坏的情况下是O(n)，其中n是树中节点的个数。这取决于树的形状，如果树是高度平衡的，则查找的时间复杂度会相对较低，否则会退化为链表，导致查找时间复杂度上升。

需要注意的是，查找二叉树并不保证是平衡的，因此在某些情况下可能会导致树的不平衡，从而影响查找的效率。为了解决这个问题，可以使用平衡二叉树的变种，如红黑树或AVL树，来保持树的平衡性。

🔎4.平衡二叉树

平衡二叉树（Balanced Binary Tree），也称为AVL树，是一种特殊的二叉搜索树（Binary Search Tree），它的左子树和右子树的高度差不超过1，并且左子树和右子树都是平衡二叉树。

平衡二叉树的一个重要性质是它的高度是O(log n)，其中n是二叉树中节点的数量。

平衡二叉树的结构使得在插入、删除、查找等操作时，可以保持树的平衡性，从而保证了操作的时间复杂度为O(log n)。

平衡二叉树的结构可以通过多种方式实现，比如AVL树、红黑树等。

在平衡二叉树中，每个节点都保存了左子树和右子树的高度差，当插入或删除节点导致不平衡时，需要进行相应的旋转操作来恢复平衡。

平衡二叉树的常见操作包括插入节点、删除节点、查找节点等。

平衡二叉树的应用非常广泛，常用于需要高效的插入、删除和查找操作的场景，比如字典、数据库索引等。

🚀感谢：给读者的一封信

亲爱的读者，

我在这篇文章中投入了大量的心血和时间，希望为您提供有价值的内容。这篇文章包含了深入的研究和个人经验，我相信这些信息对您非常有帮助。

如果您觉得这篇文章对您有所帮助，我诚恳地请求您考虑赞赏1元钱的支持。这个金额不会对您的财务状况造成负担，但它会对我继续创作高质量的内容产生积极的影响。

我之所以写这篇文章，是因为我热爱分享有用的知识和见解。您的支持将帮助我继续这个使命，也鼓励我花更多的时间和精力创作更多有价值的内容。

如果您愿意支持我的创作，请扫描下面二维码，您的支持将不胜感激。同时，如果您有任何反馈或建议，也欢迎与我分享。

再次感谢您的阅读和支持！

最诚挚的问候， “愚公搬代码”