【初阶数据结构和算法】初识树与二叉树的概念以及堆和完全二叉树之间的关系
文章目录
一、树的概念与结构
1.树的概念
树是⼀种⾮线性的数据结构，它是由n(n>=0)个有限结点组成⼀个具有层次关系的集合,把它叫做树是因为它看起来像⼀棵倒挂的树，也就是说它是根朝上，⽽叶朝下的，如图：
树的特点：
- 有⼀个特殊的结点，称为根结点，根结点没有前驱结点
- 除根结点外，其余结点被分成M(M>0) 个互不相交的集合T1、T2、……、Tm ，其中每⼀个集合Ti(1 <= i <= m) ⼜是⼀棵结构与树类似的⼦树。每棵⼦树的根结点有且只有⼀个前驱，可以有0个或多个后继。因此，树是递归定义的
- 树形结构中，⼦树之间不能有交集，否则就不是树形结构（如果存在相交就是图了，C++部分会讲解）
- 除了根结点外，每个结点有且仅有⼀个⽗结点
- ⼀棵N个结点的树有N-1条边
我们接下来演示几个非树形结构的样例，让我们更好得明白树这样一个结构：
在上面的三个示例图中，它们的根节点都是A，然后BCD三个节点分别构成了三课子树，BCD可以认为是三颗子树的“根节点”，但是它们并非是真正的树形结构，因为子树之间有了交集，不满足刚刚讲的树的最后一个特点，所以不构成真正的树形结构
2.树的相关术语
- ⽗结点/双亲结点：若⼀个结点含有⼦结点，则这个结点称为其⼦结点的⽗结点；如上图：A是B的父结点/双亲节点
- ⼦结点/孩⼦结点：⼀个结点含有的⼦树的根结点称为该结点的⼦结点；如上图：B是A的孩⼦结点
- 结点的度：⼀个结点有⼏个孩⼦，他的度就是多少；⽐如A的度为3，B的度为2，K的度为0
- 树的度：⼀棵树中，度最⼤的结点的度称为树的度；如上图：树的度为3
- 叶⼦结点/终端结点：度为0的结点称为叶结点；如上图：J,F,G,K,I等结点为叶结点
- 分⽀结点/⾮终端结点：度不为0的结点；如上图：A,B,C,D…等节点为分支节点
- 兄弟结点：具有相同⽗结点的结点互称为兄弟结点(亲兄弟)；如上图B和C是兄弟节点
- 结点的层次：从根开始定义起，根为第1 层，根的⼦结点为第2层，以此类推
- 树的⾼度或深度：树中结点的最⼤层次；如上图：树的⾼度为4
- 结点的祖先：从根到该结点所经分⽀上的所有结点，比如父节点，父节点的父节点，依次类推；如上图：A是所有结点的祖先
- 路径：⼀条从树中任意节点出发，沿⽗节点-⼦节点连接，达到任意节点的序列；⽐如A到Q的路径为：A-E-J-Q；H到Q的路径H-D-A-E-J-Q
- ⼦孙：以某结点为根的⼦树中任⼀结点都称为该结点的⼦孙。如上图：所有结点都是A的⼦孙
- 森林：由m(m>0) 棵互不相交的树的集合称为森林；
3.树的表示
树结构相对线性表就⽐较复杂了，要存储表⽰起来就⽐较⿇烦了，既然保存值域，也要保存结点和结点之间的关系
实际中树有很多种表⽰⽅式如：双亲表⽰法，孩⼦表⽰法、孩⼦双亲表⽰法以及孩⼦兄弟表⽰法等。我们这⾥就简单的了解其中最常⽤的孩⼦兄弟表⽰法，如下：
structTreeNode{//左边开始的第⼀个孩⼦结点 structNode* child;//指向其右边的下⼀个兄弟结点structNode* brother;//结点中的数据int data;};我们可以举一个例子来说明为什么孩子兄弟法可以轻松地表示出来整颗树，如下图的二叉树：
我们使用孩子兄弟法来表示这颗树的大致示意如下：
4.树形结构实际运用举例
⽂件系统是计算机存储和管理⽂件的⼀种⽅式，它利⽤树形结构来组织和管理⽂件和⽂件夹。在⽂件系统中，树结构被⼴泛应⽤，它通过⽗结点和⼦结点之间的关系来表⽰不同层级的⽂件和⽂件夹之间的关联，如图：
二、二叉树的概念及特殊二叉树
1.二叉树的概念
我们先来看看现实中的二叉树：
可以看到这棵树的每个分支都只有两个节点，将它倒过来就是我们树形结构中的二叉树了，我们简单画一个二叉树，如图：
在树形结构中，我们最常⽤的就是⼆叉树，二叉树就是最大度为2的树，一个节点最多有两个孩子，它的结点的⼀个有限集合，该集合由⼀个根结点加上两棵别称为左⼦树和右⼦树的⼆叉树组成或者为空
二叉树的特点：
- ⼆叉树不存在度⼤于2的结点
- ⼆叉树的⼦树有左右之分，次序不能颠倒，因此⼆叉树是有序树
对于任意的⼆叉树都是由以下⼏种情况复合⽽成
2.特殊的二叉树
满二叉树
⼀个⼆叉树，如果每⼀个层的结点数都达到最⼤值，则这个⼆叉树就是满⼆叉树。也就是说，如果⼀个⼆叉树的层数为k，且结点总数是2k -1，则它就是满二叉树，如图：
完全二叉树
完全⼆叉树是效率很⾼的数据结构，完全⼆叉树是由满⼆叉树⽽引出来的。对于深度为K的，有n个结点的⼆叉树，当且仅当其每⼀个结点都与深度为K的满⼆叉树中编号从1⾄n的结点⼀⼀对应时称之为完全⼆叉树
也就是说完全二叉树就是除了最后一层，其它层次的节点个数都达到最大，而满二叉树则要求不仅其它层次的节点个数都达到最大，最后一层的节点个数也要达到最大，所以满⼆叉树是⼀种特殊的完全⼆叉树，我们画一个完全二叉树看看：
二叉树的性质(由满二叉树特点推导)
- 如果根节点是二叉树的第1层，那么一颗非空二叉树中的第k层最多有2k-1个节点
- 如果根节点是二叉树的第1层，那么一共k层的二叉树最多有2k -1个节点，可以根据等比数列求和公式证明
- 如果根节点是二叉树的第1层，并且有n个节点，那么这颗二叉树有h = log2 (n+1)层
三、二叉树的存储结构
⼆叉树⼀般可以使⽤两种结构存储，⼀种是顺序结构，另⼀种则是链式结构
1.二叉树的顺序结构
顺序结构存储就是使⽤数组来存储二叉树，⼀般使⽤数组更适合表⽰完全⼆叉树，因为不是完全⼆叉树会有空间的浪费，我们简单画两个图对比一下：
根据上图可以看到，如果我们使用数组存放完全二叉树，基本上不会产生空间浪费，就算有也只浪费了较少的空间，但是如果使用数组存放非完全二叉树的话，就会产生极大的空间浪费
所以我们一般使用数组存放完全二叉树，而使用数组存放完全二叉树的这种结构就是我们二叉树的顺序结构，但是如果我们存放的二叉树不是完全二叉树呢？这时候我们就会采用二叉树的链式结构来存放
2.二叉树的链式结构
⼆叉树的链式存储结构是指，⽤链表来表⽰⼀棵⼆叉树，即⽤链来指⽰元素的逻辑关系。通常表示的⽅法是，链表中每个结点由三个域组成，分别是数据域和左右指针域，左右指针域用来存放左右孩子的地址，数据域则是当前节点存放的数据
链式结构⼜分为⼆叉链和三叉链，当前我们学习中⼀般都是⼆叉链。在C++篇章我们学到⾼阶数据结构后会⽤到三叉链，接下来我们分别来画一画二叉链，三叉链我们后面再学习，如图：
二叉树链式结构最大的特点就是，它可以存储非完全二叉树的同时不浪费空间，所以我们常常使用链式结构来存放一些不规则的二叉树，使用顺序结构存放完全二叉树
四、堆和完全二叉树之间的关系以及堆的特性
1.堆和完全二叉树之间的关系
我们平常所说的堆是一种特殊的数据结构，那么它的本质是什么呢？它的本质其实就是一颗完全二叉树，并且使用顺序结构存储数据，也就是说堆是使用数组存放数据的一颗完全二叉树
但是堆比起平常普通的完全二叉树要多出一些特性，普通二叉树在上面已经介绍过了，我们现在重点介绍堆这种特殊的完全二叉树
堆这种特殊的完全二叉树特殊在它的根节点，它的根节点要么就是整个完全二叉树中的最大值，要么就是整个完全二叉树中的最小值，如果堆的根节点是最大值，那么就叫大根堆，如果是最小值就叫小根堆
那么是不是除了根节点以外其它节点就没有要求了呢？并不是的，因为一颗完全二叉树可以看成是由多颗子树构成，这些子树也有自己的根节点，它们也必须遵守在整颗子树中，根节点最大或最小这个要求，我们简单画个图理解：
在这颗完全二叉树中，首先整颗完全二叉树的最小值是根节点，然后根节点下面有左右两颗子树，其中左子树中的根节点15为左子树中的最小值，右子树中的根节点56为左子树中的最小值
随后左子树又有自己的左右子树，右子树也有自己的左右子树，只要一直遵守这个规则，最终我们就会得到一个堆，但是我们发现了一个问题，15为根节点的子树下面的两个节点25和30，比15的兄弟节点56都要小，这会不会有问题呢？
注意注意： 在堆中，子树之间是独立存在的，互不影响，我们只看一颗子树的根节点是否是这颗子树的最小值，在左子树中15是它的最小值，在右子树中56是它的最小值，所以它依然满足堆的定义，因为子树之间是独立存在的，互不影响
所以上图的完全二叉树可以说完全遵守了堆的规则，每颗子树的根节点是整颗子树的最小值，那么上面的这颗完全二叉树其实是一个小根堆
现在应该能大致理解完全二叉树和堆的关系了吧，堆是一种更加特殊的完全二叉树，我们一般实现二叉树的顺序结构就是实现的堆这种特殊的完全二叉树
2.堆的特性
其实堆的特性我们上面基本上已经讲完了，我们现在可以总结一下它的特性，为我们后面的实现做一些铺垫，如下：
- 堆中某个结点的值总是不⼤于或不⼩于其⽗结点的值
- 堆总是⼀棵完全⼆叉树
- 对于具有n个结点的堆来说，如果按照从上⾄下，从左⾄右的顺序对所有结点依次编号(编号的目的是为了将它们存放到数组中)，那么对下标为k的节点有以下特性：
（1）如果k > 0，那么k节点的父节点/双亲节点的下标为(k - 1)/2，k == 0时为根节点的编号，无双亲节点
（2）如果2k + 1 < n，那么k节点的左孩子下标为2k + 1，否则i无左孩子
（3）如果2k + 2 < n，那么k节点的右孩子下标为2k + 2，否则i无右孩子
这里特别说明一下，上面总结的第三点的特性也适用于普通完全二叉树，普通完全二叉树中一个节点的父节点/双亲节点、左孩子和右孩子的下标规律也是这样
今天我们学习了树、二叉树以及堆的一些基础知识后，下一篇博客我们就来将这些知识运用到实战中，正式实现堆这种数据结构，敬请期待吧！
那么今天就到这里啦，有什么疑问欢迎提出，bye~
