【数据结构】--二叉树--堆(上)

一、树的概念和结构

概念：

树是一种非线性的数据结构，他是由n(n>=0)个有限结点组成一个具有层次关系的集合。其叫做树，是因为他倒过来看就和一棵树差不多，其实际上是根在上，树枝在下的。

树的特点：

1、其有一个特殊的结点，称为根结点，根结点没有前驱结点。

2、除根结点，其余的结点被分为M(M>0)个互不相交的集合，其中每个集合其又是一棵结构与树类似的子树，每棵子树的根结点有且只有一个前驱，其可以有0个或者多个后继。所以树是递归定义的。

如上图所示，树的结构其倒过来就和我们现实生活中的树长得很像了。

要注意的是，树形结构中，我们的子树之间是不能有交集的。

下面为树的几个要求：

1、子树之间是不相交的（如果相交那么就是另外一种数据结构图了）

2、除了根结点外，每个结点有且仅有一个父节点，即前驱结点有且仅有一个。

3、一颗有N个结点的树，其边有N-1条。

树的相关术语：

父结点： 若⼀个结点含有⼦结点，则这个结点称为其⼦结点的⽗结点；如上图：A是B的⽗结点

子结点：⼀个结点含有的⼦树的根结点称为该结点的⼦结点；如上图：B是A的孩⼦结点

结点的度：⼀个结点有⼏个孩⼦，他的度就是多少；⽐如A的度为6，F的度为2，K的度为0

树的度：一颗树中，最大的结点的度就是这个树的度，如上图，结点的度最大的是A为6，那么树的度就为6。

叶子节点：度为0的结点就为叶子结点，如上图，B、C、H、I、J、P、Q、K、L、M、N就为叶子结点。

分支结点：度不为0的结点

结点的层次：从根的开始定义起，根为第1层、以此类推

树的高度或深度：树中结点的最大层次。如上图为4

结点的祖先：根结点。如上就是A结点

路径：⼀条从树中任意节点出发，沿⽗节点-⼦节点连接，达到任意节点的序列；⽐如A到Q的路径为： A-E-J-Q；H到Q的路径H-D-A-E-J-Q

子孙：以某结点为根的子树中任一结点都称为该结点的子孙。

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

树的表示：

前面我们已经知道我们的树是咋样的情况了，那么我们在代码中要如何进行表示一个树结构呢？

在程序中我们表示树的方式有很多种，我们要根据使用场景来选择合适的表示方式，常见的表示方法有：孩子表示法，孩子兄弟表示法，双亲表示法。

下面是我们的孩子兄弟表示法：

孩子兄弟表示法，就是两个指针，一个指针指向其左孩子，一个指针指向其右边的第一个兄弟。

树在实际运用：

实际上我们早已在电脑上使用过树结构了，我们计算机上的文件存储和管理文件的结构，其就是使用的树形结构来组织和管理文件和文件夹的。在文件系统中，树结构被广泛应用，通过父结点，层层的往下找其子结点，然后找到最终的文件。其通过父结点和子结点之间的关系来表示不同的层级之间的文件和上一层文件夹之间的关系。

二、二叉树

二叉树的概念和结构：

二叉树是树形结构中的一种特殊情况，也是我们最常用的一种树形结构，一颗二叉树是结点的一个有限集合，该集合由一个根结点再加上两棵分别称为左子树和右子树的二叉树组成，或者为空。

如下：

在上面的图中我们可以看到二叉树的特点：

1、二叉树不存在度大于2的结点

2、二叉树的子树是有左右之分的，次序是不能颠倒的，所以二叉树是有序树

二叉树会有下面几种情况：

特殊的二叉树：

1、满二叉树

一个二叉树，如果其每一层的结点树都达到最大值，那么这个二叉树就是满二叉树。即：我们现在有一个层数为k的二叉树，那么我们的结点数，为2的k次方-1的时候，那么我们的二叉树就是满二叉树。

如下：

2、完全二叉树

完全二叉树，也是一种特殊的二叉树，它的定义是在二叉树的前提下，其除了最后一层外，其余的层的结点都是满的，而且最后一层的结点都是集中在左侧。

如下：

二叉树的性质：

1、若规定根结点的层次为1，则一颗树非空二叉树的第i层上最多的结点个数为2的i次方-1个结点

2、若规定根结点的层次为1，则一棵深度为h的二叉树的最多的结点数为2的h次方-1个结点

3、若规定根结点的层次为1 ，具有n个结点的满二叉树的深度h=log2(n+1)

二叉树的存储结构：

二叉树一般使用两种结构存储吗，一种顺序结构，一种是链式结构。

顺序存储：

顺序存储结构底层上是使用数组来存储，不过一般使用数组存储的话就是满二叉树，因为完全二叉树使用数组存储，这是因为不是完全二叉树的话，其会造成空间的浪费。

如下所示：

不过实际上我们通常将堆（二叉树的一种）使用顺序结构的数组来进行存储，不过要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两个回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段。

链式存储：
二叉树的链式存储通过链表形式动态的进行表示结点间的逻辑关系，其方法如下：

通常的⽅法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别⽤来给出该结点左孩⼦和右孩⼦所在的链结点的存储地址。链式结构⼜分为⼆叉链和三叉链，当前我们学习中⼀般都是⼆叉链。后⾯课程学到⾼阶数据结构如红⿊树等会⽤到三叉链。

其具体思路如下：

1、结点结构：

其有三个成员组成：

数据域：存储当前结点的元素值

左指针域：指向左子结点的地址

右指针域：指向右子结点的地址

2、链式类型划分：

二叉链：仅含左右子结点指针

空间效率高，满足基础算法实现需求

三叉链：增加父结点指针域

便于逆向溯源，应用于红黑树等复杂数据结构

三、实现顺序结构二叉树

堆的概念和结构：

如果有⼀个关键码的集合K = {k0 ,k1, k2, ...，kn−1 }，把它的所有元素按完全⼆叉树的顺序存储⽅式存储，在⼀个⼀维数组中，并满⾜：Ki<= K(2i+1)

（K >=K（2*i+1）且Ki<= K (2*i+2))i = 0、1、2...，则称为⼩堆(或⼤堆)。将根结点最⼤的堆叫做最⼤堆或⼤根堆，根结点最⼩的堆叫做最⼩堆或⼩根堆。

如下：

堆的性质：

1、堆中的某个结点的值总是不大于或者不小于其父结点

2、堆总是一棵完全二叉树

二叉树的一些特点：

对于具有n个结点的完全二叉树，如果按照从上到下，从左至右的顺序，对所有的结点从0开始进行编号，那么对于编号为i的结点有下面的几个性质：

1、若i>0，i位置的父结点序号：(i-1)/2;i=0的话，那么其是根结点，没有父结点

2、若2i+1<n，那么左孩子序号为2i+1，如果2i+1>=n，那么没有左孩子

3、若2i+2<n，那么其右孩子序号为2i+2，如果2i+2>=n那么没有右孩子

堆的实现：

前面我们已经了解了啥是堆，堆的结构是如何的，那么我们下面就通过代码来实现堆的功能。

首先我们要创建一个堆结构，那么我们该如何进行表示呢？通过上面的学习我们知道，堆是顺序存放的，那么我们堆的实现的底层还是使用数组来实现。

然后就是简单的初始化：

那么我们的堆如何进行插入数据呢？

我们会选择在尾部进行插入，我们插入后，如何将当前的二叉树变成堆的结构，我们的堆是有序的，其子结点要不就是大于或者等于其父结点，要不就小于或者等于其父结点，所以我们插入尾部后，我们还需要对这个二叉树进行调整，那么我们的堆如果是小堆，那么我们小的元素就要往上存放，父结点一定要小于子结点，所以我们可以通过当前结点找到其父结点，然后进行比较，如果新插入的结点比其父结点要小，那么新插入的结点和父结点就进行交换。如果是大堆的话，那么就还是一样，大的往上走即可。这种方法我们叫做向上调整法。

代码如下：