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

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

📋 前言

  🌈hello! 各位宝子们大家好啊,关于线性表我们已经在前面更新完了!

  ⛳️今天就来看一下复杂一些的数据结构 “树” 他的应用主要在哪些方面呢?以及结构是什么样的

  📚本期文章收录在《数据结构&算法》,大家有兴趣可以看看呐

  ⛺️ 欢迎铁汁们 ✔️ 点赞 👍 收藏 ⭐留言 📝!

一、什么是树?

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

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

可能大家还不是很了解但大家看上面这张图,左边是一棵树,右边就是我们的 多叉树数据结构了;

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

1.1 树的注意事项

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

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

1.2 树的相关概念

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


  • 结点的度:一个结点含有的子树的个数称为该结点的度; 如上图: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 树的应用场景有那些

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

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

这里 Linux 的文件目录就是用多叉树实现的。

二 、二叉树的概念详讲

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

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

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

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

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

2.1 特殊的二叉树

满二叉树

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

完全二叉树

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

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

2.2 二叉树的性质

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

  1. 若规定根结点的层数为1,则一棵非空二叉树的第i层上最多有2 ( i − 1 ) 2^{(i-1)}2(i1) 个结点.
  2. 若规定根结点的层数为1,则深度为h的二叉树的最大结点数是2 h − 1 2^h-12h1.
  3. 对任何一棵二叉树, 如果度为0其叶结点个数为 n 0 n_0n0, 度为2的分支结点个数为 n 2 n_2n2,则有n 0 n_0n0n 2 n_2n2+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 顺序存储实现二叉树

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

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

🔥 注:一般使用数组只适合表示完全二叉树,因为不是完全二叉树会有空间的浪费

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

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

📚 代码演示:

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

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

  • 需要了我们就去申请节点,不需要就不申请。
  • 这样就避免了空间的浪费

🔥 注意:上述代码并不是创建二叉树的方式,只是给大家演示一下后面博主会出一篇博文来进行讲解的。

📚 代码演示:

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;
}
目录
相关文章
|
21天前
|
存储 算法
数据结构与算法学习二二:图的学习、图的概念、图的深度和广度优先遍历
这篇文章详细介绍了图的概念、表示方式以及深度优先遍历和广度优先遍历的算法实现。
36 1
数据结构与算法学习二二:图的学习、图的概念、图的深度和广度优先遍历
|
21天前
|
存储 算法 关系型数据库
数据结构与算法学习二一:多路查找树、二叉树与B树、2-3树、B+树、B*树。(本章为了解基本知识即可,不做代码学习)
这篇文章主要介绍了多路查找树的基本概念,包括二叉树的局限性、多叉树的优化、B树及其变体(如2-3树、B+树、B*树)的特点和应用,旨在帮助读者理解这些数据结构在文件系统和数据库系统中的重要性和效率。
14 0
数据结构与算法学习二一:多路查找树、二叉树与B树、2-3树、B+树、B*树。(本章为了解基本知识即可,不做代码学习)
|
21天前
|
存储 算法 搜索推荐
数据结构与算法学习十七:顺序储存二叉树、线索化二叉树
这篇文章主要介绍了顺序存储二叉树和线索化二叉树的概念、特点、实现方式以及应用场景。
15 0
数据结构与算法学习十七:顺序储存二叉树、线索化二叉树
|
18天前
|
Java C++
【数据结构】探索红黑树的奥秘:自平衡原理图解及与二叉查找树的比较
本文深入解析红黑树的自平衡原理,介绍其五大原则,并通过图解和代码示例展示其内部机制。同时,对比红黑树与二叉查找树的性能差异,帮助读者更好地理解这两种数据结构的特点和应用场景。
22 0
|
21天前
|
存储 算法
探索数据结构:分支的世界之二叉树与堆
探索数据结构:分支的世界之二叉树与堆
|
21天前
|
存储 算法
数据结构与算法学习十六:树的知识、二叉树、二叉树的遍历(前序、中序、后序、层次)、二叉树的查找(前序、中序、后序、层次)、二叉树的删除
这篇文章主要介绍了树和二叉树的基础知识,包括树的存储方式、二叉树的定义、遍历方法(前序、中序、后序、层次遍历),以及二叉树的查找和删除操作。
17 0
|
21天前
|
算法 程序员 索引
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
栈的基本概念、应用场景以及如何使用数组和单链表模拟栈,并展示了如何利用栈和中缀表达式实现一个综合计算器。
18 1
数据结构与算法学习七:栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
|
2天前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总(10)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
21天前
初步认识栈和队列
初步认识栈和队列
49 10