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

举报
倔强的石头 发表于 2024/10/23 23:29:39 2024/10/23
【摘要】 二叉树是一种重要的树形数据结构,每个节点最多有两个子节点,通常称为左子节点和右子节点。二叉树具有广泛的应用场景和多种特殊的类型,如满二叉树、完全二叉树、二叉搜索树和平衡二叉树等。二叉树的结构简单清晰,操作灵活,因此在计算机科学和软件工程领域有着广泛的应用。通过遍历二叉树,我们可以高效地执行各种操作,如搜索、排序、插入和删除等。

 目录

 一、树的概念

🍃树的定义

🍃树的特点

🍃树的相关术语

二、二叉树的概念

🍃二叉树的定义

🍃二叉树的特点

🍃二叉树的分类

🍃二叉树的性质(重要)

三、二叉树的存储结构

🍃顺序结构

🍃链式结构

四、二叉树的应用场景



 一、树的概念

🍃树的定义

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

例如下图就是一棵树 

59a4265aa5524ee8b73c5f33c56bda25.png编辑

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

f23839f67dc0486d9df7f870a5a07ed4.png编辑


🍃树的特点

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


🍃树的相关术语

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


二、二叉树的概念


🍃二叉树的定义

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


🍃二叉树的特点

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


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

31568dc411d845a5b3e015a86b2b8803.png编辑


🍃二叉树的分类

  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. 存储转换
    • 如果需要将一个普通的二叉树转换为顺序存储结构,通常需要先将其转换为完全二叉树或满二叉树。这可以通过给二叉树添加一些空的子节点来实现。

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

c899defd985f4dbaa4f46ac51dfa508f.png编辑

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

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


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




🍃链式结构

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


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





四、二叉树的应用场景

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


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

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

【版权声明】本文为华为云社区用户原创内容,未经允许不得转载,如需转载请自行联系原作者进行授权。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。