【愚公系列】软考中级-软件设计师 017-数据结构（树和二叉树概念）

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

---

🚀前言

数据结构中的树是一种非线性的数据结构，它由一组节点和连接这些节点的边组成。树的节点之间的关系是一种层次关系，其中一个节点称为根节点，其他节点可以是它的子节点或后代节点。树的结构使得在树中进行快速的搜索、插入、删除操作成为可能。

树的节点有一个或多个子节点，每个子节点又可以有自己的子节点，形成了一个递归的结构。每个节点可以有零个或多个子节点，而没有子节点的节点称为叶节点。

树的常见特点包括：

• 树的节点之间不存在环路。
• 从根节点到任意节点都存在唯一的路径。
• 每个节点可以有任意多个子节点，但每个子节点只能有一个父节点。

树有许多种类，常见的树结构包括二叉树、二叉搜索树、平衡二叉树（如AVL树和红黑树）、B树、堆等。每种树结构都适用于不同的应用场景，具有不同的性能特点和操作复杂度。

树的应用非常广泛，如在数据库中用于索引、在操作系统中用于文件系统的组织、在图形学中用于表示层次结构等。了解不同类型的树结构以及它们的性质和操作，有助于解决各种实际问题，并提高算法和数据结构的设计能力。

🚀一、树

🔎1.树和二叉树的定义

🦋1.1 树

在数据结构中，树是一种非线性的数据结构，它由一组节点和一组连接节点的边组成。树的定义如下：

1. 树由节点组成，每个节点包含一个值和指向零个或多个子节点的指针。
2. 有一个节点被指定为根节点，它没有父节点。根节点是树的起始点。
3. 除了根节点外，每个节点都有一个父节点。
4. 除了叶节点外，每个节点都可以有一个或多个子节点。
5. 每个节点之间的连接称为边。

树的形状类似于现实生活中的树，根节点对应树的顶部，叶节点对应树的底部。每个节点可以有任意数量的子节点，但每个节点只能有一个父节点。

树可以有不同的类型，如二叉树、二叉搜索树、红黑树等。这些类型的树有各自的特点和应用场景。树结构在计算机科学中有广泛的应用，例如文件系统的目录结构、数据库索引、编译器语法分析等。

概念	定义
双亲、孩子和兄弟	结点的子树的根称为该结点的孩子；相应地，该结点称为其子结点的双亲。具有相同双亲的结点互为兄弟。
结点的度	一个结点的子树的个数，记为该结点的度。
叶子结点	叶子结点也称为终端结点。指度为0的结点。
内部结点	度不为0的结点，也称为分支结点或非终端结点。除根结点以外，分支结点也称为内部结点。
结点的层次	根为第一层，根的孩子为第二层，以此类推，若某结点在第 i 层，则其孩子结点在第 i+1 层。
树的高度（深度）	一棵树的最大层数，记为树的高度（或深度）。
有序（无序）树	若将树中结点的各子树看成是从左到右具有次序的，即不能交换，则称该树为有序树，否则称为无序树。

🦋1.2 二叉树

二叉树是一种常见的数据结构，它由节点组成，每个节点最多有两个子节点：左子节点和右子节点。每个节点都包含一个值或者数据，值可以是任何类型的数据。

二叉树的特点是每个节点最多有两个子节点，而且子节点的位置是有序的，即左子节点在父节点的左边，右子节点在父节点的右边。

对于二叉树，每一个节点都可以看作是一个子二叉树的根节点。如果一个节点没有子节点，我们称其为叶子节点。另外，如果某个节点不是叶子节点，则它至少有一个子节点。

二叉树可以有不同的特殊类型，比如满二叉树、完全二叉树等。在满二叉树中，除了叶子节点外的每个节点都有两个子节点，并且所有的叶子节点都在同一层上。在完全二叉树中，除了最后一层，其他层都是满的，并且最后一层的叶子节点都尽可能地靠左排列。

二叉树可以用来表示各种各样的数据，比如二叉查找树（Binary Search Tree，简称BST），用来实现快速的查找和插入操作。二叉树还可以用来表示表达式，构建语法树，以及图的遍历等。

二叉树的重要特性如下：

设一棵二叉树上叶结点数为n0，单分支结点数为n1，双分支结点数为n2，则总结点数=n0+n1+n2。在一棵二叉
树中，所有结点的分支数（即度数）应等于单分支结点数加上双分支结点数的2倍，即总的分支数=n1+2n2。由
于二叉树中除根结点以外，每个结点都有唯一的一个分支指向它，因此二叉树中：总的分支数=总结点数-1。

🦋1.3 完全二叉树和满二叉树

完全二叉树是一种特殊的二叉树，除了最后一层外，每一层的节点都是从左到右连续排列的，最后一层的节点从左到右填充。满二叉树是一种特殊的完全二叉树，除了叶子节点外，每个节点都有两个子节点。满二叉树通常是一棵深度为h，拥有2^h-1个节点的二叉树。

🦋1.4 二叉树的存储结构

二叉树的存储结构有三种常见的形式：

1、顺序存储：就是用一组连续的存储单元存储二叉树中的节点，按照从上到下，从左到右的顺序依次存储每个节点。对于深度为k的完全二叉树，除第k层外，其余每层中节点数都是上一层的两倍，由此，从一个节点的编号可推知其双亲、左孩子、右孩子结点的编号。假设有编号为i的节点，则有：

（1）若i=1，该结点为根结点，无双亲
（2）若i＞1，该阶段的双亲为（i+1）/2（取整数）。
（3）若2i≤n，则该结点的左孩子编号为2i，否则无左孩子
（4）若2i+1≤n，则该结点的右孩子编号为2i+1，否则无右孩子。
（5）若i奇数且不为1，则该结点左兄弟的编号为i-1，否则无左兄弟。
（6）若i为偶数且小于n，则该结点右兄弟的编号为i+1，否则无右兄弟。

2、链式存储：一般用二叉链表来存储二叉树节点，二叉链表中除了该节点本身的数据外，还存储有左孩子结点的指针、右孩子结点的指针，即一个数据+两个指针。每个二叉链表节点存储一个二叉树节点，头指针则指向根节点。

🦋1.5 二叉树的遍历

二叉树的遍历是指按照某种顺序访问二叉树的所有节点。常用的二叉树遍历方式有三种：前序遍历、中序遍历和后序遍历。

1. 前序遍历（preorder traversal）：先访问根节点，再遍历左子树，最后遍历右子树。具体步骤是：先访问当前节点，然后递归地前序遍历左子树，最后递归地前序遍历右子树。

2. 中序遍历（inorder traversal）：先遍历左子树，再访问根节点，最后遍历右子树。具体步骤是：先递归地中序遍历左子树，然后访问当前节点，最后递归地中序遍历右子树。

3. 后序遍历（postorder traversal）：先遍历左子树，再遍历右子树，最后访问根节点。具体步骤是：先递归地后序遍历左子树，然后递归地后序遍历右子树，最后访问当前节点。

此外，还有两种特殊的遍历方式：层序遍历和逆序遍历。

4. 层序遍历（level order traversal）：按层级从上到下、从左到右的顺序遍历二叉树。具体步骤是：使用队列，首先将根节点入队，然后循环执行以下操作：出队当前节点，访问当前节点，将当前节点的左子节点和右子节点分别入队。直到队列为空。

5. 逆序遍历：将前序、中序和后序遍历的访问顺序反转。例如，逆序前序遍历即为后序遍历。

示例：前序：12457836中序：42785136后序：48752631

---

🚀感谢：给读者的一封信

亲爱的读者，

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

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

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

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

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

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