速学数据结构 | 树 森林 二叉树 的概念详讲篇

这篇具有很好参考价值的文章主要介绍了速学数据结构 | 树 森林 二叉树 的概念详讲篇。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。


速学数据结构 | 树 森林 二叉树 的概念详讲篇,《数据结构&算法》,数据结构,c++,机器学习,开发语言

🎬 鸽芷咕:个人主页

 🔥 个人专栏:《速学数据结构》 《C语言进阶篇》
⛺️生活的理想,就是为了理想的生活!

📋 前言

  🌈hello! 各位宝子们大家好啊,关于线性表我们已经在前面更新完了!
  ⛳️今天就来看一下复杂一些的数据结构 “树” 他的应用主要在哪些方面呢?以及结构是什么样的
  📚本期文章收录在《数据结构&算法》,大家有兴趣可以看看呐
  ⛺️ 欢迎铁汁们 ✔️ 点赞 👍 收藏 ⭐留言 📝!

一、什么是树?

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

  • 所以他有一个根节点,根结点没有前驱结点。
  • 又因为树的节点除了根节点 外,还有很多子节点而子节点又有很多子节点
  • 所以树是由 递归创建

速学数据结构 | 树 森林 二叉树 的概念详讲篇,《数据结构&算法》,数据结构,c++,机器学习,开发语言
可能大家还不是很了解但大家看上面这张图,左边是一棵树,右边就是我们的 多叉树数据结构了;

  • 由树的根节点,加孩子节点。而孩子节点又有很多孩子节点组成的!
  • 所以我们说树是由递归创建的,他们每个部分都是相同的结构

1.1 树的注意事项

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

  • 大家在做选择题的时候一定要注意了

速学数据结构 | 树 森林 二叉树 的概念详讲篇,《数据结构&算法》,数据结构,c++,机器学习,开发语言

1.2 树的相关概念

前面我们说了树是由 一个根节点加很多 子孙节点 组成的,那么他们相应的叫法是什么呢?


速学数据结构 | 树 森林 二叉树 的概念详讲篇,《数据结构&算法》,数据结构,c++,机器学习,开发语言

  • 结点的度:一个结点含有的子树的个数称为该结点的度; 如上图:A的为6

  • 🔥 叶结点或终端结点:度为0的结点称为叶结点; 如上图:B、C、H、I…等结点为叶结点

  • 🔥 非终端结点或分支结点:度不为0的结点; 如上图:D、E、F、G…等结点为分支结点

  • 🔥 双亲结点或父结点:若一个结点含有子结点,则这个结点称为其子结点的父结点; 如上图:A是B的父结点

  • 🔥 孩子结点或子结点:一个结点含有的子树的根结点称为该结点的子结点; 如上图:B是A的孩子结点

  • 兄弟结点:具有相同父结点的结点互称为兄弟结点; 如上图:B、C是兄弟结点

  • 树的度:一棵树中,最大的结点的度称为树的度; 如上图:树的度为6

  • 🔥 结点的层次:从根开始定义起,根为第1层,根的子结点为第2层,以此类推

  • 🔥 树的高度或深度:树中结点的最大层次; 如上图:树的高度为4

  • 堂兄弟结点:双亲在同一层的结点互为堂兄弟;如上图:H、I互为兄弟结点

  • 🔥 结点的祖先:从根到该结点所经分支上的所有结点;如上图:A是所有结点的祖先

  • 🔥 子孙:以某结点为根的子树中任一结点都称为该结点的子孙。如上图:所有结点都是A的子孙

  • 森林:由m(m>0)棵互不相交的树的集合称为森林;

其中红色标记的是比较重要的概念大家可以重点记一下这些都是选择题经常出现的概念,像树的深度树的层级

  • 计算孩子节点/叶子节点的个数
  • 如果一个树的深度为4 那么他的最大节点个数是多少?

等等这样的题如果不了解这些概念的话是根本做不了的

1.3 树的应用场景有那些

诶不知道大家注意过没有我们的文件夹和树的结构很类似?

  • 由一个根文件组成,里面还有很多子文件夹,和子孙文件夹。

速学数据结构 | 树 森林 二叉树 的概念详讲篇,《数据结构&算法》,数据结构,c++,机器学习,开发语言
这里 Linux 的文件目录就是用多叉树实现的。

二 、二叉树的概念详讲

树的概念我们讲解了,但是其实我们应用最广的还是二叉树比如 八大排序里面的 堆排序快速排序 全都应用了树的思想。

  • 这俩总排序方法都是排序中最快的之一

那么什么是二叉树呢? 其实二叉树就是结点的一个有限集合

  • 该集合,要不为空
  • 要不就是由一个根结点加上两棵别称为左子树和右子树的二叉树组成

速学数据结构 | 树 森林 二叉树 的概念详讲篇,《数据结构&算法》,数据结构,c++,机器学习,开发语言

  1. 📌 二叉树不存在度大于2的结点
  2. 📌 二叉树的子树有左右之分,次序不能颠倒,因此二叉树是有序树

2.1 特殊的二叉树

满二叉树

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

速学数据结构 | 树 森林 二叉树 的概念详讲篇,《数据结构&算法》,数据结构,c++,机器学习,开发语言

完全二叉树

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

  • 要注意的是满二叉树是一种特殊的完全二叉树。

速学数据结构 | 树 森林 二叉树 的概念详讲篇,《数据结构&算法》,数据结构,c++,机器学习,开发语言

2.2 二叉树的性质

二叉树是什么我们前面了解过了那么二叉树有那些性质是需要我们来了解一下的呢?

  1. 若规定根结点的层数为1,则一棵非空二叉树的第i层上最多有 2 ( i − 1 ) 2^{(i-1)} 2(i1) 个结点.
  2. 若规定根结点的层数为1,则深度为h的二叉树的最大结点数是 2 h − 1 2^h-1 2h1.
  3. 对任何一棵二叉树, 如果度为0其叶结点个数为 n 0 n_0 n0, 度为2的分支结点个数为 n 2 n_2 n2,则有 n 0 n_0 n0 n 2 n_2 n2+1
  4. 若规定根结点的层数为1,具有n个结点的满二叉树的深度h= l o g 2 ( n + 1 ) log_2(n+1) log2(n+1). (ps: l o g 2 ( n + 1 ) log_2(n+1) log2(n+1)是log以2为底,n+1为对数)
  5. 对于具有n个结点的完全二叉树,如果按照从上至下从左至右的数组顺序对所有结点从0开始编号,则对于序号为i的结点有:
    1. 若i>0,i位置结点的双亲序号:(i-1)/2;i=0,i为根结点编号,无双亲结点
    2. 若2i+1<n,左孩子序号:2i+1,2i+1>=n否则无左孩子
    3. 若2i+2<n,右孩子序号:2i+2,2i+2>=n否则无右孩子

三、二叉树的两种实现方法

3.1 顺序存储实现二叉树

好了讲了这么多大家估计也听的很迷糊,不要慌接下来我们就来看一下二叉树的实现来带大家吃下肉:

  • 二叉树的实现有俩总方式:其中顺序存储就是使用数据来进行存储
  • 利用其下标来进行控制左右子树。

🔥 注:一般使用数组只适合表示完全二叉树,因为不是完全二叉树会有空间的浪费
速学数据结构 | 树 森林 二叉树 的概念详讲篇,《数据结构&amp;算法》,数据结构,c++,机器学习,开发语言

大家看这个图片一但使用数组来存储普通的二叉树就会造成很大的空间浪费,顺序存储是由数组进行控制的。

  • 左子树就算不使用存储数据也要把空间给空出来

📚 代码演示:

typedef int HPDataType;
typedef struct Heap
{
	HPDataType* a;  //存储数据的数组
	int size;		//存储的数据个数
	int capacity;	//二叉树的容量
}HP;

3.2 .链式结构的二叉树实现

二叉树的链式结构就很简单了,我们前面说了利用顺序存储会造成空间的浪费而链式存储的就避免了这种情况和链表一样。

  • 需要了我们就去申请节点,不需要就不申请。
  • 这样就避免了空间的浪费
    速学数据结构 | 树 森林 二叉树 的概念详讲篇,《数据结构&amp;算法》,数据结构,c++,机器学习,开发语言

🔥 注意:上述代码并不是创建二叉树的方式,只是给大家演示一下后面博主会出一篇博文来进行讲解的。
📚 代码演示:文章来源地址https://www.toymoban.com/news/detail-761788.html

typedef int BTDataType;
typedef struct BinaryTreeNode
{
	BTDataType _data;
	struct BinaryTreeNode* _left;
	struct BinaryTreeNode* _right;
}BTNode;

BTNode* CreatBinaryTree()
{
 BTNode* node1 = BuyNode(1);
 BTNode* node2 = BuyNode(2);
 BTNode* node3 = BuyNode(3);
 BTNode* node4 = BuyNode(4);
 BTNode* node5 = BuyNode(5);
 BTNode* node6 = BuyNode(6);

 node1->_left = node2;
 node1->_right = node4;
 node2->_left = node3;
 node4->_left = node5;
 node4->_right = node6;
 return node1;
}

到了这里,关于速学数据结构 | 树 森林 二叉树 的概念详讲篇的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 《数据结构C语言版》——树、森林与二叉树的转换(超详图解)

    哈喽!这里是一只派大鑫,不是派大星。本着基础不牢,地动山摇的学习态度,从基础的C语言语法讲到算法再到更高级的语法及框架的学习。更好地让同样热爱编程(或是应付期末考试 狗头.jpg)的大家能够在学习阶段找到好的方法、路线,让天下没有难学的程序(只有秃头的程

    2024年02月10日
    浏览(39)
  • 【数据结构】 二叉树理论概念!一文了解二叉树!

    🎥 屿小夏 : 个人主页 🔥个人专栏 : 数据结构解析 🌄 莫道桑榆晚,为霞尚满天! 什么是二叉树?二叉树的组成构造是什么样的?我们将由浅入深,循序渐进的方式把二叉树给搞明白,让你彻底了解二叉树! 树是一种非线性的数据结构,它是由n(n=0)个有限结点组成一

    2024年02月05日
    浏览(48)
  • 数据结构--树4.2.4(树、森林即二叉树的相互转换(仅供参考))

    目录 一、树转换成二叉树步骤 二、森林转换成二叉树  三、二叉树到树、森林的转换 分两个步骤:         1、在树中所有的兄弟结点之间加一连线。         2、对每个结点,除了保留与其长子(最左边)的连线外,去掉该结点与其他孩子的连线。         1、先将森林中

    2024年02月11日
    浏览(33)
  • 【数据结构】树、二叉树的概念和二叉树的顺序结构及实现

    之前我们学习了顺序表、链表以及栈和队列这些数据结构,但这些数据结构都是线性的(一对一)。接下来要学习 非线性的数据结构——树(二叉树) ,相比前面的,树的结构更加复杂,话不多说,直接进入正题吧。 树是一种 非线性的数据结构 ,它是 一对多(也有可能是

    2024年02月07日
    浏览(42)
  • 数据结构——树的概念、二叉树的概念

    现在是北京时间的2023年6月7号15点28分,刚考完了一课期末考试,回到宿舍就立马准备发布这篇博客。距离完成本周复习指标还差两篇博客。加油! 树是一种非线性的数据结构,它是由n(n=0)个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的

    2024年02月08日
    浏览(47)
  • 【数据结构】树和二叉树概念

    树是一种 非线性 的数据结构,它是由n(n=0)个有限结点组成一个具有层次关系的集合。 把它叫做树是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。 有一个 特殊的结点,称为根结点 ,根节点没有前驱结点 除根节点外, 其余结点被分成M(M0)个互不相交

    2024年02月09日
    浏览(40)
  • 【数据结构】二叉树的基本概念

    树是一种非线性的数据结构,它是由n(n=0)个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的 子树不能有交集,就是不能有闭环.N个节点两个一条边,所以是N-1个边,父节点的概念在下面讲. 节点的度

    2024年02月08日
    浏览(45)
  • 数据结构入门 — 二叉树的概念、性质及结构

    本文属于数据结构专栏文章,适合数据结构入门者学习,涵盖数据结构基础的知识和内容体系,文章在介绍数据结构时会配合上 动图演示 ,方便初学者在学习数据结构时理解和学习,了解数据结构系列专栏点击下方链接。 博客主页:Duck Bro 博客主页 系列专栏:数据结构专栏

    2024年02月07日
    浏览(36)
  • 爱上数据结构:二叉树的基本概念

    ​ ​ 🔥个人主页 : guoguoqiang. 🔥 专栏 : 数据结构 ​ 树是一种非线性的数据结构,它是由n(n=0)个有限结点组成一个具有层次关系的集合。把它叫做树是因 为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。 没有前驱节点的结点叫做根结点 在树中,子树不

    2024年04月14日
    浏览(48)
  • 数据结构--线索二叉树的概念

    中序遍历序列:D G B E A F C ①如何找到指定结点p在中序遍历序列中的前驱? ②如何找到p的中序后继? 思路: 从根节点出发,重新进行一次中序遍历,指针q记录当前访问的结点,指针pre记录上一个被访问的结点 ①当q p时,pre为前驱 ②当pre p时,q为后继 缺点 : 找前驱、后继很不方便

    2024年02月13日
    浏览(49)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包