【数据结构】树和二叉树的概念及结构

本文涉及的产品
公共DNS(含HTTPDNS解析),每月1000万次HTTP解析
云解析 DNS,旗舰版 1个月
全局流量管理 GTM,标准版 1个月
简介: 数据结构——树和二叉树的概念及结构

1. 树概念及结构

1.1 树的概念

树是一种非线性的数据结构,它是由n(n>=0)个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的

(1)有一个特殊的结点,称为根结点,根结点没有前驱结点

(2)除根结点外,其余结点被分成M(M>0)个互不相交的集合T1、T2、……、Tm,其中每一个集合Ti(1<= i <= m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱,可以有0个或多个后继。

(3)因此,树是递归定义的。(一棵树可以拆成根和子树,子树又能拆成根和子树,直到拆到叶子。就是可以将“大问题”分解为“小问题”,“小问题”再分解成“更小的问题”,具有“大事化小”的特性)
image.png

关于子树
image.png

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

1.2 树的相关概念

和人类的亲缘关系类比
image.png

结点的度:一个结点含有的子树的个数称为该结点的度; 如上图:A的为6 (数这个结点的分支
叶结点或终端结点:度为0的结点称为叶结点; 如上图:B、C、H、I、P、Q、K、L、M、N结点为叶结点(最外面那一圈的所有结点
非终端结点或分支结点:度不为0的结点; 如上图:D、E、F、G...等节点为分支结点(有分支的结点
双亲结点或父结点:若一个结点含有子结点,则这个结点称为其子结点的父结点; 如上图:A是B的父结点(根结点是没有父亲的
孩子结点或子结点:一个结点含有的子树的根结点称为该结点的子结点; 如上图:B是A的孩子结点
兄弟结点(亲兄弟):具有相同父结点的结点互称为兄弟结点; 如上图:B、C是兄弟结点
树的度:一棵树中,最大的结点的度称为树的度; 如上图:树的度为6
结点的层次:从根开始定义起,根为第1层,根的子结点为第2层,以此类推
树的高度或深度:树中结点的最大层次; 如上图:树的高度为4
堂兄弟结点:双亲在同一层的结点互为堂兄弟;如上图:H、I互为堂兄弟结点;H、N互为堂兄弟结点(同一层不为亲兄弟的两个结点
结点的祖先:从根到该结点所经分支上的所有结点;如上图:A是所有结点的祖先
子孙:以某结点为根的子树中任一结点都称为该结点的子孙。如上图:所有结点都是A的子孙
森林:由m(m>0)棵互不相交的树的集合称为森林

关于结点的层次,有如下说明:
image.png

结点可以从第0层开始算,也可以从第1层开始算,推荐从第1层开始算。
image.png

我们看上图:

如果从第0层开始算(即最上面那层为第0层),空树(NULL)的深度为-1;一个结点的情况,树的深度就为0;如果有4个结点,树的深度就为3。

如果从第1层开始算(即最上面那层为第1层),空树(NULL)的深度为0;一个结点的情况,树的深度就为1;如果有4个结点,树的深度就为4。

我们可以看出,从第1层开始算,比较直观,也比较合理。因此推荐从第1层开始算。

1.3 树的表示

树结构相对线性表就比较复杂了,要存储表示起来就比较麻烦了,既要保存值域,也要保存结点和结点之间的关系,实际中树有很多种表示方式如:双亲表示法,孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。我们这里就简单的了解其中最常用的孩子兄弟表示法(左孩子右兄弟)

typedef int DataType;
struct Node
{
   
   
    DataType _data;  //结点中的数据域
    struct Node* _firstChild1;  //第一个孩子结点
    struct Node* _pNextBrother;  //指向其下一个兄弟结点
};

image.png
image.png

双亲表示法:
image.png

用结构数组,每个数组元素只存储双亲的下标,如果一个结点没有父亲(也就是根结点),就标记为-1。如上图森林的情况,A、B均为根结点,A、B就均标为-1。

1. 如何检查森林有几棵树?

看有几个-1,有几个-1就有几个根,有几个根就有几棵树。

2. 怎么判断两个结点在不在同一棵树?

找根,根相同就在同一棵树。

1.4 树在实际中的运用

文件系统就是一个树形结构
image.png

                                               表示文件系统的目录树结构

2. 二叉树的概念及结构

2.1 概念

一棵二叉树是结点的一个有限集合,该集合:

  1. 或者为

  2. 由一个根结点加上两棵别称为左子树右子树的二叉树组成
    image.png

从上图可以看出:

  1. 二叉树不存在度大于2的结点(即最多两个孩子,也可以是1个或0个孩子。如果有两个孩子,我们就把左边的孩子左孩子右边的孩子右孩子

  2. 二叉树的子树有左右之分,次序不能颠倒,因此二叉树是有序树

注意:对于任意的二叉树都是由以下几种情况复合而成的:

image.png

2.2 现实中的二叉树

image.png

2.3 特殊的二叉树

  1. 满二叉树:一个二叉树,如果每一个层的结点数都达到最大值,则这个二叉树就是满二叉树。也就是说,如果一个二叉树的层数为K,且结点总数是2^K-1 ,则它就是满二叉树。

  2. 完全二叉树:完全二叉树是效率很高的数据结构,完全二叉树是由满二叉树而引出来的。对于深度为K的,有n个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树
    image.png

2.3.1 满二叉树

image.png
image.png

高度为h的满二叉树有2^h-1个结点

如果一棵满二叉树有N个结点,根据上面推出的结论,

我们可以知道这棵满二叉树的高度h为 log2 (N+1)
image.png

一棵满二叉树有n个结点,那么它的高度h为log2(N+1)

如果N是10亿(10亿有9个0,2^10=1024,所以10亿可以估计成(2^10)(2^10)(2^10)=2^30),根据h=log2(N+1),所以可算出高度h约为30。

也就是说如果将我国14亿人口的信息存到满二叉树中,极限情况也只要31层就可以(2^30=10亿,2^31=2^302=10亿2=20亿)。

二叉树每往下一层走,能存的信息量是非常巨大的!

2.3.2 完全二叉树

image.png

高度为h的完全二叉树的结点个数范围是[2^(h-1),2^h-1]

最后一层从左到右必须连续,否则就不是完全二叉树,如下图就不是完全二叉树:
image.png

对于一棵完全二叉树而言,如果存在度为1的结点,那么这个结点只能有0个或者1个。
image.png

这是因为完全二叉树的定义是除了最后一层外,其他层的结点都是满的,并且最后一层的结点依次从左到右排列。在这样的排列中,度为1的结点只能出现在最后一层的末尾结点,其余的结点都应该有两个子结点。因此,除了最后一层的末尾结点,度为1的结点是不允许存在的。

2.4 二叉树的性质

  1. 若规定根结点的层数为1,则一棵非空二叉树的第i层上最多有2^(i-1)个结点。

  2. 若规定根结点的层数为1,则深度为h的二叉树的最大结点数是2^h-1

  3. 对任何一棵二叉树, 如果度为0其叶结点个数为n0, 度为2的分支结点个数为n2 ,则有n0 = n2 + 1

  4. 若规定根结点的层数为1,具有n个结点的满二叉树的深度h=log2(n+1) 。 (注:log2(n+1)是log以2为底,n+1为对数)

  5. 对于具有n个结点的完全二叉树,如果按照从上至下从左至右的数组顺序对所有结点从0开始编号,则对于序号为i的结点有:

  6. 若i>0,i位置节点的双亲序号:(i-1)/2;i=0,i为根结点编号,无双亲结点

  7. 若2i+1=n否则无左孩子

  8. 若2i+2=n否则无右孩子

二叉树性质练习题

  1. 某二叉树共有 399 个结点,其中有 199 个度为 2 的结点,则该二叉树中的叶子结点数为( )
    A 不存在这样的二叉树
    B 200
    C 198
    D 199
    解析:根据上面二叉树性质第3条“对任何一棵二叉树, 如果度为0其叶结点个数为n0, 度为2的分支结点个数为n2 ,则有n0 = n2 + 1”。

度为2的结点n2有199个,叶结点(度为0的结点)就有n0=n2+1=200个。故选B

  1. 下列数据结构中,不适合采用顺序存储结构的是( )
    A 非完全二叉树
    B 堆
    C 队列
    D 栈

解析:选A(可以看下面2.5.1.2 非完全二叉树的顺序存储)

  1. 在具有2n个结点的完全二叉树中,叶子结点个数为( )
    A n
    B n+1
    C n-1
    D n/2

解析:选A,具体分析过程如下图
image.png

  1. 一棵完全二叉树的结点数为531个,那么这棵树的高度为( )
    A 11
    B 10
    C 8
    D 12

解析:高度为h的完全二叉树的结点个数范围是[2^(h-1),2^h-1]

当h=10时候,结点个数是[512,1023],而531就在这个范围内。所以这棵树的高度为10,故选B

  1. 一个具有767个结点的完全二叉树,其叶子结点个数为()
    A 383
    B 384
    C 385
    D 386

解析:选B,具体分析过程如下图
image.png

2.5 二叉树的存储结构

二叉树一般可以使用两种结构存储,一种顺序结构,一种链式结构

2.5.1 顺序存储

顺序结构存储就是使用数组来存储,一般使用数组只适合表示完全二叉树,因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储,关于堆我们后面的章节会专门讲解。二叉树顺序存储在物理上是一个数组,在逻辑上是一颗二叉树。

2.5.1.1 完全二叉树的顺序存储

image.png

2.5.1.2 非完全二叉树的顺序存储

image.png

2.5.2 链式存储

二叉树的链式存储结构是指,用链表来表示一棵二叉树,即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成,数据域左右指针域,左右指针分别用来给出该结点左孩子右孩子所在的链结点的存储地址 。链式结构又分为二叉链三叉链,当前我们学习中一般都是二叉链,到高阶数据结构如红黑树等会用到三叉链。
image.png

3. 总结

到这里,我们就用学习完了数据结构中树和二叉树的概念及结构。有什么问题欢迎在评论区讨论。如果觉得文章有什么不足之处,可以在评论区留言。如果喜欢我的文章,可以点赞收藏哦!

相关文章
|
13天前
|
存储 搜索推荐 算法
【数据结构】树型结构详解 + 堆的实现(c语言)(附源码)
本文介绍了树和二叉树的基本概念及结构,重点讲解了堆这一重要的数据结构。堆是一种特殊的完全二叉树,常用于实现优先队列和高效的排序算法(如堆排序)。文章详细描述了堆的性质、存储方式及其实现方法,包括插入、删除和取堆顶数据等操作的具体实现。通过这些内容,读者可以全面了解堆的原理和应用。
56 16
|
13天前
|
C语言
【数据结构】二叉树(c语言)(附源码)
本文介绍了如何使用链式结构实现二叉树的基本功能,包括前序、中序、后序和层序遍历,统计节点个数和树的高度,查找节点,判断是否为完全二叉树,以及销毁二叉树。通过手动创建一棵二叉树,详细讲解了每个功能的实现方法和代码示例,帮助读者深入理解递归和数据结构的应用。
62 8
|
1月前
|
Java C++
【数据结构】探索红黑树的奥秘:自平衡原理图解及与二叉查找树的比较
本文深入解析红黑树的自平衡原理,介绍其五大原则,并通过图解和代码示例展示其内部机制。同时,对比红黑树与二叉查找树的性能差异,帮助读者更好地理解这两种数据结构的特点和应用场景。
28 0
|
1月前
|
存储 算法
探索数据结构:分支的世界之二叉树与堆
探索数据结构:分支的世界之二叉树与堆
|
1月前
探索顺序结构:栈的实现方式
探索顺序结构:栈的实现方式
|
14天前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
90 9
|
5天前
|
存储 算法
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
14 1
|
8天前
|
存储 算法 Java
数据结构的栈
栈作为一种简单而高效的数据结构,在计算机科学和软件开发中有着广泛的应用。通过合理地使用栈,可以有效地解决许多与数据存储和操作相关的问题。
|
11天前
|
存储 JavaScript 前端开发
执行上下文和执行栈
执行上下文是JavaScript运行代码时的环境,每个执行上下文都有自己的变量对象、作用域链和this值。执行栈用于管理函数调用,每当调用一个函数,就会在栈中添加一个新的执行上下文。
|
13天前
|
存储
系统调用处理程序在内核栈中保存了哪些上下文信息?
【10月更文挑战第29天】系统调用处理程序在内核栈中保存的这些上下文信息对于保证系统调用的正确执行和用户程序的正常恢复至关重要。通过准确地保存和恢复这些信息,操作系统能够实现用户模式和内核模式之间的无缝切换,为用户程序提供稳定、可靠的系统服务。
40 4