【数据结构】二叉树之堆

刺骨的言语ヽ痛彻心扉 2023-07-09 02:09 21阅读 0赞

本篇章主要梳理下二叉树的内容，重点在于堆的创建、插入、删除、排序等内容，进行详细图解。

## 1. 二叉树 ##

##### 1.1 概念 #####

一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根节点加上两棵别称为左子树和右子树的二叉树组成。

**【二叉树的特点】**

1.  每个节点最多有两棵子树，即二叉树不存在度大于2的节点；
2.  二叉树的子树有左右之分，其子树的次序不能颠倒。

##### 1.2 特殊二叉树 #####

**【满二叉树】**

*  一棵二叉树，如果每一个层的节点数都达到最大值，则这个二叉树就是满二叉树，也就是说，如果一个二叉树的层数为K，且节点总数是(2^k) -1，则它就是满二叉树。

**【完全二叉树】**

*  完全二叉树是由满二叉树引申而来。对于深度为K，有n个节点的二叉树，当且仅当其每一个节点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树；
 *  满二叉树是一种特殊的完全二叉树。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjg2Mzcz_size_16_color_FFFFFF_t_70]

##### 1.3 二叉树的存储 #####

*  二叉树有两种结构存储：顺序结构，链式结构 。
 *  顺序结构存储：使用数组来存储，一般使用数组只适合完全二叉树，因为不是完全二叉树会有空间的浪费。而顺序结构存储通常是把堆进行数组存储，二叉树顺序存储在是一个数组，在逻辑上是一颗二叉树。
 *  链式存储结构：用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。通常的方法是链表中每个节点由三个域组成，数据域和左右指针域，左右指针分别用来给出该节点左孩子和右孩子所在的链节点的存储地址。

## 2. 顺序结构 ##

*  通常把堆(一种二叉树)使用顺序结构的数组来存储。

##### 2.1 堆的概念 #####

*  如果有一个关键码的集合K = \{k0，k1，k2，…，kn-1\}，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足：Ki <= K2i+1 且 Ki <= K2i+2 ，i = 0，1，2…，则称为小堆；Ki >= K2i+1 且 Ki >= K2i+2 ，i = 0，1，2…，则称为大堆。
 *  根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。

**【堆的性质】**

*  堆中某个节点的值总是不大于或不小于其父节点的值 ；
 *  堆总是一棵完全二叉树。

**【堆的存储】**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjg2Mzcz_size_16_color_FFFFFF_t_70 1]

##### 2.2 堆的实现 #####

**2.2.1 堆的创建**

*  一般给出一个数组，这个数组逻辑上可以看做一颗完全二叉树，但是并一个堆，通过算法把它构建成一个堆。从倒数的第一个非叶子节点的子树开始调整，一直调整到根节点的树，就可以调整成堆。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjg2Mzcz_size_16_color_FFFFFF_t_70 2]  
    **2.2.2 堆的插入**
 *  将数据插入到数组的尾上，再进行向上调整算法，直到满足堆结构。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjg2Mzcz_size_16_color_FFFFFF_t_70 3]  
    **2.2.3 堆的删除**
 *  删除堆是删除堆顶的数据，将堆顶的数据与最后一个数据交换，然后删除数组最后一个数据，再进行向下调整算法。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjg2Mzcz_size_16_color_FFFFFF_t_70 4]  
    **2.2.4 堆的排序**  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjg2Mzcz_size_16_color_FFFFFF_t_70 5]

## 3.链式结构 ##

**【遍历】**

*  NLR：前序遍历(Preorder Traversal 也称先序遍历)——根、左、右
 *  LNR：中序遍历(Inorder Traversal)——左、根、右
 *  LRN：后序遍历(Postorder Traversal)——左、右、根
 *  层序遍历：从二叉树的根节点(第1层)出发，首先访问第一层的树根节点，然后从左到右访问第2层上的节点，接着是第3层的节点，以此类推，自上而下，自左至右逐层访问树的结点  
    ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjg2Mzcz_size_16_color_FFFFFF_t_70 6][]  
    若哪里有不足，请指正，会及时改正。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjg2Mzcz_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200227104641519.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjg2Mzcz,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjg2Mzcz_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200227105157896.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjg2Mzcz,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjg2Mzcz_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200227105221955.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjg2Mzcz,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjg2Mzcz_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200227105231743.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjg2Mzcz,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjg2Mzcz_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200227105238560.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjg2Mzcz,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjg2Mzcz_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20200227105250506.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjg2Mzcz,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjg2Mzcz_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20200301092537571.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMjg2Mzcz,size_16,color_FFFFFF,t_70