二叉树02（数据结构初阶）

欢迎大家阅读我的博客，给生活加点impetus！！

今天我们学习二叉树的顺序结构实现！！

堆

一：实现顺序结构二叉树

⼀般堆使⽤顺序结构的数组来存储数据，堆是⼀种特殊的⼆叉树，具有⼆叉树的特性的同时，还具备其他的特性。

1.1堆的概念与结构

如果有⼀个关键码的集合K= {k0，k1,k2…kn-1}，把它的所有元素按完全⼆叉树的顺序存储方式存储，在⼀个⼀维数组中，并满⾜：Ki<=K2i-1（K>=K2i+1且K<=K2*i+2），i = 0、1、2… ，则称为⼩堆(或⼤堆)。将根结点最⼤的堆叫做最⼤堆或⼤根堆，根结点最⼩的堆叫做最⼩堆或⼩根堆。

定义难以理解，接下来我们来看看图示

堆的性质：
1：:根结点的值最大或最小，子树的根结点的值最大或最小。
2： 堆总是⼀棵完全⼆叉树。

非小堆：

二叉树性质：
•对于具有 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.2堆的实现

结构定义

堆的底层为数组，所以我们先来定义堆的结构。

初始化，销毁，打印堆，判空

这四个方法在栈和队列里面都实现过，我们直接来看结果。

交换数据

复习：有一种不创建临时变量也能够交换数据的方法：
a=a^b; b=a^b; a=a^b;
这里我们使用按位或。

上述主要是为核心方法做铺垫，上述方法的实现都比较简单。

重点：入堆

我们先来画图演示一下：

这种算法叫做向上调整算法。尾部插入数据，与父结点数据进行比较。

接下来我们将思路转化成代码：

向上调整函数

注意：1：向上调整没有比较和兄弟结点的关系。只比较一个子节点与父结点的大小关系。
2：是拿子与父比较，父是由子算来的。

重点：出堆

我们来画图理解一下：

接下来我们举例：

我们再来一个找大数据：

代码实现

注意：1：
向下算法需要brother结点相互比较找最大。
2：拿父与子比较，子是由父得来的。

取堆顶元素

我们有关用顺序结构实现栈就实现完了，下去记得勤敲代码哦！！

1.3堆的应用

1.3.1堆排序

首先，我们来实现一下堆排序。

第一种：使用数据结构堆来实现

核心：每次堆顶都为最值，反复重置堆顶，并取堆顶元素

没有堆结构，函数实现方法涉及堆的都无法执行

我们需要先创建堆

建堆，向下调整时，i此时指向的时最后一个元素的父节点，从这个位置，i–，逐渐遍历完所有树。
向上调整时是从低层往高层逐渐建堆，向下建堆时是高层往低层逐渐建堆。

堆排序：

结语：

感谢大家阅读我的博客，有错之处欢迎大家指针，感谢大家支持！！
莫等闲，白了少年头，空悲切！！，加油！！