【数据结构与算法】详解二叉树 上：理论篇——二叉树的基本概念与性质

​

 目录

 一、树的概念

🍃树的定义

🍃树的特点

🍃树的相关术语

二、二叉树的概念

🍃二叉树的定义

🍃二叉树的特点

🍃二叉树的分类

🍃二叉树的性质（重要）

三、二叉树的存储结构

🍃顺序结构

🍃链式结构

四、二叉树的应用场景

 一、树的概念

🍃树的定义

1. 基本定义：树是一种抽象数据类型或数据结构，用于模拟具有树状结构性质的数据集合。它由n(n>0)个有限节点组成，这些节点之间具有层次关系。
2. 结构特点：树的结构通常表现为根朝上、叶朝下，类似于一棵倒挂的树。每个节点可以有零个或多个子节点，但除了根节点外，每个节点都有且仅有一个父节点。

例如下图就是一棵树 

​编辑​

 注意：树形结构中，子树之间不能有交集，否则就不是树形结构

​编辑​

🍃树的特点

1. 根节点：树中唯一没有父节点的节点，是整个树的起点。
2. 子节点与父节点：每个节点可以有零个或多个子节点，而每个子节点都有一个父节点（除了根节点）。
3. 叶节点：没有子节点的节点，也称为终端节点。
4. 路径：两个节点之间通过边相连的序列，表示从一个节点到另一个节点的路线。
5. 深度与高度：节点的深度是从根节点到该节点的边数；节点的高度是从该节点到最远叶节点的边数；树的高度是根节点的高度。
6. 子树：一个节点及其所有后代节点构成的树。

🍃树的相关术语

• 度：一个节点拥有的子树数。
• 叶子节点：度为0的节点。
• 根节点：树的起点，没有父节点。
• 父节点与子节点：节点与其直接子节点之间的关系。
• 兄弟节点：具有相同父节点的节点。
• 树的度：树中节点度的最大值。

二、二叉树的概念

🍃二叉树的定义

二叉树（Binary Tree）是一种特殊的树形数据结构，其中每个节点最多有两个子节点，通常称为左子节点和右子节点。

🍃二叉树的特点

1. 度：二叉树中每个节点的度最大为2（即最多有两个子节点）。
2. 有序性：二叉树是有序的树，若将其左、右子树颠倒，则称为另一棵不同的二叉树。

任意的二叉树都是由以下五种情况构成的 

​编辑

🍃二叉树的分类

1. 空二叉树：没有节点的二叉树称为空二叉树。
2. 满二叉树：一棵深度为k的，且有2^k - 1个节点的二叉树称为满二叉树。
3. 完全二叉树：深度为k的，有n个节点的二叉树，当且仅当其每一个节点都与深度为k的满二叉树中编号从1至n的节点一一对应时称之为完全二叉树。 

🍃二叉树的性质（重要）

1. 若规定根结点的层数为1，则一棵非空二叉树的第i层上最多有 2^(i-1)个结点.
2.  若规定根结点的层数为1，则深度为h的二叉树的最大结点数是 2^h-1
3.  对任何一棵二叉树, 如果度为0的叶结点个数为n0 , 度为2的分支结点个数为n2 ,则有 n0＝ n2＋1

三、二叉树的存储结构

🍃顺序结构

二叉树的顺序存储结构，又称为数组表示法，是用一组地址连续的存储单元依次存储二叉树中的节点元素。在顺序存储结构中，通常按照二叉树节点自上向下、自左向右的顺序存储。以下是关于二叉树顺序存储结构的详细解释：

1. 存储方式：
   • 使用一维数组来存储二叉树的节点。对于完全二叉树或满二叉树，节点的编号（或称为索引）与数组中的下标存在直接的对应关系。
2. 完全二叉树与满二叉树的存储：
   • 对于完全二叉树和满二叉树，节点的编号（从1开始）与数组中的下标（从0开始）之间的关系为：如果节点编号为i，则其在数组中的下标为i-1。
   • 例如，第一个节点的编号为1，其在数组中的下标为0；第二个节点的编号为2，其在数组中的下标为1，依此类推。
3. 父子节点关系：
   • 如果节点在数组中的下标为n（n从0开始），则其左子节点在数组中的下标为2n+1（如果存在的话）；右子节点在数组中的下标为2n+2（如果存在的话）。
   • 父节点的下标可以由子节点的下标通过(n-1)/2计算得出（其中n为子节点在数组中的下标，结果向上取整）。
4. 特点：
   • 顺序存储结构通常只适用于完全二叉树和满二叉树，因为这样可以最大化地利用数组的空间，避免浪费。
   • 顺序存储结构可以快速地通过下标找到节点的父节点或子节点（如果存在的话）。
   • 对于非完全二叉树，使用顺序存储结构可能会导致空间浪费，因为数组中可能有很多位置是空的。
5. 存储转换：
   • 如果需要将一个普通的二叉树转换为顺序存储结构，通常需要先将其转换为完全二叉树或满二叉树。这可以通过给二叉树添加一些空的子节点来实现。

二叉树的顺序存储结构示意图如下

​编辑

二叉树顺序存储在物理上是一个数组，在逻辑上是一颗二叉树。

图中可以明显看到，对于非完全二叉树来说，顺序存储可能存在大量浪费空间的问题

顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储，

🍃链式结构

二叉树的链式结构，即用链表来表示一棵二叉树，通过链表来指示元素之间的逻辑关系。二叉树的链式结构是一种灵活且高效的存储方式，它支持动态地插入和删除节点，适用于各种需要动态操作二叉树的场景。

一般我们所使用的二叉树都是用链式结构来实现的，这也是接下里要讲解的重点内容，不过篇幅所限，将会放在下一篇文章单独讲解

四、二叉树的应用场景

二叉树的应用场景非常广泛，在计算机科学中扮演着重要的角色。以下是二叉树的主要应用场景，按领域进行分点表示和归纳：

1. 数据库：
   • 索引：在数据库中，二叉树（特别是其变种如B树和B+树）被广泛应用于实现索引。索引是一种用于加速数据库查询的数据结构。通过二叉树索引，每个节点都包含一个键值和指向左、右子树的指针，从而可以快速定位所需的数据。
2. 编程语言：
   • 语法树：在编程语言中，二叉树被用于解析和生成语法树。语法树是一种表示程序语法结构的树状结构，其中每个节点表示一个语法元素（如变量、运算符或函数调用）。通过构建语法树，编译器可以将源代码转换为可执行代码。
3. 图形学：
   • 几何图形表示：在图形学中，二叉树被用于构建几何图形的数据结构。例如，二叉树可以用于实现三角网格的分割和细分，其中每个节点表示一个三角形，而左、右子树分别表示三角形的左、右子三角形。
4. 人工智能：
   • 决策树：在人工智能中，二叉树被用于实现决策树。决策树是一种用于分类和预测的数据结构，其中每个节点表示一个属性（如年龄、性别或收入水平），通过比较属性值可以将数据集分成更小的子集。
   • 搜索树：搜索树（如二叉搜索树）是一种用于搜索最优解的数据结构。在搜索树中，每个节点表示一个状态（如一个棋盘上的局面），通过不断扩展搜索树可以找到最优的解决方案。
5. 系统设计：
   • 数据结构和算法：在系统设计中，二叉树被广泛应用于实现各种数据结构和算法。例如，二叉搜索树是一种用于快速查找和插入数据的数据结构，其时间复杂度为O(log n)。
6. 搜索、排序和查找：
   • 二叉搜索树：二叉搜索树是一种特殊的二叉树，其中每个节点的值大于左子树的所有节点的值，小于右子树的所有节点的值。通过二分查找算法，在二叉搜索树中可以快速定位目标值。
7. 堆：
   • 二叉堆：二叉堆是一种用于实现优先队列的数据结构。它具有以下特点：任意节点的关键字值都小于（或大于）或等于其子节点的关键字值，根节点的关键字值最小（或最大）。二叉堆的插入和删除操作的时间复杂度为O(log n)，适用于一些需要高效的优先级操作的场景，如任务调度。
8. 表达式树：
   • 数学表达式：二叉树可以用于存储和计算数学表达式。表达式树是一种二叉树，其叶节点是操作数，内部节点是操作符。通过遍历表达式树，可以递归地计算整个表达式的值。
9. 文件系统：
   • 文件和文件夹管理：二叉树可以用于组织和管理文件系统中的文件和文件夹。每个节点代表一个文件或文件夹，左子节点代表文件夹下的子文件夹，右子节点代表同一层级下的其他文件或文件夹。通过遍历二叉树，可以实现文件的查找、创建、删除等操作。
10. 数据压缩：
    • 哈夫曼树：哈夫曼树是一种常用的数据压缩算法，通过构建二叉树来实现。在哈夫曼树中，出现频率较高的字符对应的节点位于树的较低层，而出现频率较低的字符对应的节点位于树的较高层。通过对字符进行编码并使用相对较短的编码表示高频字符，可以实现对数据的高效压缩和解压缩。

这些只是二叉树应用场景的一部分示例，实际上二叉树在计算机科学和工程中的应用远不止这些

​