二叉树和堆
- 树的概念及结构
- 树的一些术语（概念）
- 树的表示
- 二叉树的概念及结构
- 二叉树概念与其结构
- 二叉树的性质
- 二叉树的存储
- 堆
- 堆的概念
- 堆的实现
- 向上调整算法
- 向下调整算法
- 实现堆数据结构
- 堆的插入
- 取堆顶数据
- 堆顶数据删除
- 堆排序
- TopK问题
本文主要介绍二叉树的一些基本概念，同时介绍堆的结构并且使用堆来实现排序（堆排序），以及通过堆来实现topk问题。 对于建堆与堆排序主要向下调整算法，当然建堆也可使用向上调整算法。
树的概念及结构
树是一种非线性的数据结构，它是由n(n>=0)个有限节点组成的一个具有层次关系的集合，由于它的结构看起来像一颗树（像是一颗倒立的数），根朝上，叶子在下。有一个特殊的结点，称为根结点，根结点没有前驱结点除根结点外，其余结点被分成M(M>0)个互不相交的集合T1、T2、……、Tm，其中每一个集合Ti(1<= i<= m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有0个或多个后继因此，树是递归定义的。树的结构可参考下图
需要注意的是：树形结构，子树之间不能有交集，否则就不能称为树了，子树是不相交的，除了根节点，每个节点有且只有一个父节点，一棵树有N个节点那么它有N-1条边。
树的一些术语（概念）
节点的度：一个节点含有子树的个数称为该节点的度，如上图所示，其D的节点的度为3，A节点的度为2.
叶子节点（终端节点）：该节点的度为0就叫叶子节点。如上图中的G，H，I，J，F都是叶子节点。
非叶子节点（分支节点）：节点的度不为0。如上图中的A，B，C，D，E。
父节点（双亲节点）：若一个节点含有子节点，则这个节点称为其子节点发父节点。如上图中的A是B的父节点，A也是C的父节点。
子节点（孩子节点）：一个节点含的子树的根节点称为该节点的子节点，如上图B是A的子节点。
兄弟节点：具有相同父节点的节点互称为兄弟节点。如上图，B和C互为兄弟节点。
树的度：一棵树中，最大的节点的度称为树的度。如上图，该树的度为3。
节点的层次：从根开始定义，根为第一层，更多子节点为第二层，以此类推。
树的高度（树的深度）:树中节点的最大层次，如上图，该树的高度为4。
堂兄弟节点：双亲在同一层的节点互为堂兄弟。如上图，D和E互为堂兄弟节点。
节点的祖先：从根到该节点所经历分支上的所有节点。如上图，A是该树所有节点（除了A本身）的祖先。
子孙：以某节点为根的子树中的任一节点都称为该节点的子孙。如上图，该树的所有节点(除了A本身）都是A的子孙
森林：由m(m>0)颗互不相交的树的集合称为森林。
树的表示
树的结构相比较于前面的顺序表和链表来说更复杂了，由于需要将该节点的值保存起来有需要将其结构（节点与节点之间的关系）也保存起来，因此树这种结构存储起来就比前面的要麻烦。实际中树有很多种表示方式如：双亲表示法，孩子表示法，孩子双亲表示法以及孩子兄弟表示法等。我们下面简单介绍最常用的孩子兄弟表示法。
typedef int DataType;
struct Node
{
struct Node* firstChild1; // 第一个孩子结点
struct Node* pNextBrother; // 指向其下一个兄弟结点
DataType data; // 结点中的数据域
};
树在实际中的运用（表示文件系统的目录树结构）如下图所示。
二叉树的概念及结构
二叉树概念与其结构
一颗二叉树是节点的有限集合，这个集合要么是空的，要么是一个根节点加上两颗别称为左子树和右子树的二叉树组成。
二叉树不存在度大于2的节点，二叉树的子树有左右之分，次序不能够颠倒，因此二叉树是有序树。任意一颗二叉树都是由以下几种情况组合而成的。如下图所示：
在二叉树中有两种特殊的存在，这两种树分别是满二叉树和完全二叉树。
满二叉树：一颗二叉树，如果每一层的节点数都达到其最大值（除了最后一层，其余每层的每个节点的度均为2）。当一棵树有k层，其节点总数有2^k-1，那么它就是慢二叉树。
完全二叉树：完全二叉树时效率很高的数据结构，完全二叉树是由满二叉树引出来的。对于深度是k（其实就是指的是层数是k），有n个节点的二叉树，当且仅当其每一个节点都与深度为k的满二叉树中编号从1-n的节点一一对应时称为完全二叉树。满二叉树是一种特殊的完全二叉树。
满二叉树和完全二叉树的示例图如下所示。
二叉树的性质
①若规定根结点的层数为1，则一棵非空二叉树的第i层上最多有2^(i-1)个节点。
②若规定根节点的层数是1，则深度为h的二叉树的最大结点数是2^h-1。
③ 对任何一棵二叉树, 如果度为0其叶结点个数为n0 , 度为2的分支结点个数为n2 ,则有n0＝n2＋1
总节点个数为：n=n0+n1+n2。
④ 若规定根结点的层数为1，具有n个结点的满二叉树的深度，h=log(n+1)。注意：其中log(n+1)是log以2为底，n+1为对数
⑤对于具有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否则无右孩子
二叉树的存储
二叉树一般可使用两种结构进行存储，一种是顺序存储，另一种是链式存储。
①顺序存储：顺序结构存储就是使用数组来进行存储。如果要用数组来进行存储的话，这就很适合完全二叉树了(示意图如下所示)。如果不是完全二叉树就会造成数组空间的浪费（如下图所示,虚线表示不存在的节点）。在实际中，只有堆这种结构才会使用数组来存储。如果一颗二叉树用顺序结构来存储，其在物理上是一个数组（是连续的），在逻辑上是一颗二叉树（是不连续的）。
②链式结构：二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。链式结构又分为二叉链和三叉链，一般都是使用二叉链。二叉链指的是左右指针，三叉链不仅有左右指针还有指向父节点的指针。关于二叉链和三叉链其结构定义如下
typedef int BTDataType;
// 二叉链
struct BinaryTreeNode
{
struct BinTreeNode* left; // 指向当前结点左孩子
struct BinTreeNode* right; // 指向当前结点右孩子
BTDataType data; // 当前结点值域
}
// 三叉链
struct BinaryTreeNode
{
struct BinTreeNode* parent; // 指向当前结点的父节点
struct BinTreeNode* left; // 指向当前结点左孩子
struct BinTreeNode* right; // 指向当前结点右孩子
BTDataType data; // 当前结点值域
}；
堆
堆的概念
首先需要知道，堆是用数组存储的，但是其逻辑结构是一颗二叉树，堆是一颗完全二叉树。堆分为大堆（大根堆）和小堆（小根堆）。
大堆：父节点的值总是 大于或等于其子节点的值。
小堆：父节点的值总是 小于或等于其子节点的值。
需要注意的是：大堆或小堆，其关系是父节点根其子节点之间的关系，而对于兄弟节点或堂兄弟节点是无关的。
大堆和小堆的示例如下图所示（左边是逻辑结构，右边是物理结构）
堆的实现
建堆算法有两种，一种是向下调整算法，另一种是向上调整算法。向上调整算法的时间复杂度相比较于向下调整算法更高，所以直接使用向下调整算法就可以建堆。
向上调整算法
使用向上调整算法需要保证这个位置前面的数据是堆，每次跟父节点进行比较。如果要建大堆，计算当前节点的父节点的下标 parents，其中 (child - 1) / 2 是因为数组从下标 0 开始存储数据，且二叉堆中下标为 child 的节点的父节点的下标为 (child - 1) / 2。比较当前节点和其父节点的大小，如果当前节点较大，则交换这两个节点的值，并更新 child 和 parents 的值，以便在下一次循环中继续比较当前节点和其祖父节点的大小。如果当前节点较小，则直接退出循环，因为此时当前节点已经位于其正确的位置，不再需要进行调整。需要注意的是，这段代码假设数组从下标 0 开始存储数据，且二叉堆中的节点满足大顶堆的性质，即每个节点的值都不小于其左孩子节点和右孩子节点的值。建小堆与上面的过程类似
建大堆其代码的实现如下：
void swap(int* p1, int* p2)
{
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
//向上调整算法,需要保证child之前的数据是堆
void adjustup(int* arr, int child)
{
int parents = (child - 1) / 2;
while (child > 0)
{
if (arr[parents] < arr[child])//建大堆
{
swap(&arr[parents], &arr[child]);
child = parents;
parents = (child - 1) / 2;
}
else
{
break;
}
}
}
使用向上调整算法建堆需要让i之前的位置是堆，所以从i=1的这个位置进行调整(i=0这个位置不需要调整，因为当只有一个数时它就是堆)，其建堆代码如下：
void BuildHeap(int* arr,int n)
{
for (int i = 1; i < n; i++)
{
adjustup(arr, i);
}
}
int main()
{
int arr[] = { 1,3,4,6,7,8,2,5,9,0 };
int n = sizeof(arr) / sizeof(arr[0]);
BuildHeap(arr, n);
return 0;
}
建堆结果如下：
将建堆结果画成二叉树其结构如下：
向上调整算法建堆时间复杂度：
为了方便计算，假设是满二叉树，并且每次都需要调整，其推到过程如下：
向上调整算法的时间复杂度为： O(NlogN)
向下调整算法
向下调整算法的建堆的时间复杂度为O(N)，需要注意的是向下调整算法是从父节点开始向下调整的，需要保证左右子树都是堆。首先计算当前节点的左孩子节点的下标 child。首先判断当前节点的右孩子节点是否存在，如果存在，则比较左右孩子节点的大小，选择较大的那个孩子节点，并更新 child 的值。接下来，比较当前节点和选择的孩子节点的大小，如果当前节点较小，则交换这两个节点的值，并更新 parents 和 child 的值。如果当前节点较大，则直接退出循环。需要注意的是，这段代码假设数组从下标 0 开始存储数据，且下标为 parents 的节点的左孩子节点的下标为 parents * 2 + 1，右孩子节点的下标为 parents * 2 + 2。
//向下调整算法,需要保证parents左右子树都是堆
void adjustdown(int* arr,int parents, int n)
{
int child = parents * 2 + 1;
while (child < n)
{
if (child + 1 < n && arr[child + 1] > arr[child])//建大堆，选最大的孩子
{
child++;
}
if (arr[parents] < arr[child])//建大堆
{
swap(&arr[child], &arr[parents]);
parents = child;
child = parents * 2 + 1;
}
else
{
break;
}
}
}
使用向下调整算法建堆从最后一个叶子节点的父节点进行调整，这是由于要调整的这个父节点之后位置都是堆，不需要进行调整。向下调整算法建堆其代码如下：
void BuildHeap(int* arr,int n)
{
//从最后一个叶子节点的父节点进行调整
for (int i = (n - 1 - 1) / 2; i >= 0 ; i--)
{
adjustdown(arr, i, n);
}
}
建堆结果如下：
将建堆结果画成二叉树其结构如下：
向下调整算法建堆时间复杂度：
为了方便计算，假设是满二叉树，并且每次都需要调整，其推到过程如下：
向下调整算法的时间复杂度为： O(N)
实现堆数据结构
构建堆这种数据结构需要用到两种算法(向上调整算法和向下调整算法)。
由于前面已经介绍了向下调整算法和向上调整算法，所以实现堆的话，下面主要介绍堆的插入和以及获取删除。
堆这个数据结构其底层就是用数组来进行存储的，所以其结构和顺序表一致。
定义堆的结构如下：
typedef int HPDataType;
typedef struct Heap
{
HPDataType* _a;//堆的底层就是数组
int _size;
int _capacity;
}Heap;
堆的插入
堆的插入与顺序表是一致的，只是还需要使用向上调整算法来进行调整使其满足堆的结构。其实现的代码如下：
// 堆的插入
void HeapPush(Heap* hp, HPDataType x)
{
assert(hp);
if (hp->_capacity == hp->_size)
{
//进行扩容
int newcapacity = hp->_capacity == 0 ? 4 : hp->_capacity * 2;
HPDataType* tmp = (HPDataType*)realloc(hp->_a, sizeof(HPDataType) * newcapacity);
if (tmp == NULL)
{
perror("malloc");
return;
}
hp->_a = tmp;
hp->_capacity = newcapacity;
}
hp->_a[hp->_size] = x;//将新进来的数据放到hp->_size这个位置
adjustup(hp->_a, hp->_size);//从hp->_size这个位置向上调整
hp->_size++;//最后让hp->_size进行++表示堆进入了一个新数据
}
取堆顶数据
这个函数的接口实现较为简单，只需要将堆顶数据返回就可。但需要注意判断堆中是否还有数据。代码实现如下：
// 取堆顶的数据
HPDataType HeapTop(Heap* hp)
{
assert(hp);
assert(hp->_size > 0);
return hp->_a[0];//返回堆顶元素
}
堆顶数据删除
堆顶数据的删除同样需要注意当前堆中是否还有数据。将堆顶的数据与堆中最后一个数据进行交换，然后堆中数据个数进行减1操作就表示将堆顶数据删除了，此时这个数据中除了顶部不是堆，左右两边都是堆，因此我们采用向下调整算法将剩下的数据调整成堆。
// 堆顶数据的删除
void HeapPop(Heap* hp)
{
assert(hp);
assert(hp->_size > 0);
swap(&hp->_a[0], &hp->_a[hp->_size - 1]);//将堆顶数据与最后一个数据交换
hp->_size--;//hp->_size进行减1操作，就表示删除了堆顶
adjustdown(hp->_a, 0, hp->_size);//使用向下调整算法让这些数据还是满足堆结构
}
实现堆的完整代码
heap.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int HPDataType;
typedef struct Heap
{
HPDataType* _a;
int _size;
int _capacity;
}Heap;
void HeapInit(Heap* hp);
// 堆的销毁
void HeapDestory(Heap* hp);
// 堆的插入
void HeapPush(Heap* hp, HPDataType x);
// 堆的删除
void HeapPop(Heap* hp);
// 取堆顶的数据
HPDataType HeapTop(Heap* hp);
// 堆的数据个数
int HeapSize(Heap* hp);
// 堆的判空
bool HeapEmpty(Heap* hp);
//向下调整算法
void adjustdown(HPDataType* arr, int parents, int n);
//向上调整算法，前面的数据是堆结构才适用
void adjustup(HPDataType* arr, int child);
//交换
void swap(int* p1, int* p2);
test.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"heap.h"
void test1()
{
Heap hp;
HeapInit(&hp);
HeapPush(&hp, 4);
HeapPush(&hp, 5);
HeapPush(&hp, 6);
HeapPush(&hp, 1);
HeapPush(&hp, 2);
HeapPush(&hp, 3);
HeapPush(&hp, 99);
while (!HeapEmpty(&hp))
{
HPDataType ret = HeapTop(&hp);
HeapPop(&hp);
printf("%d ", ret);
}
HeapDestory(&hp);
}
int main()
{
test1();
return 0;
}
heap.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"heap.h"
void HeapInit(Heap* hp)
{
assert(hp);
hp->_a = NULL;
hp->_capacity = hp->_size = 0;
}
// 堆的销毁
void HeapDestory(Heap* hp)
{
assert(hp);
free(hp->_a);
hp->_capacity = hp->_size = 0;
}
void swap(int* p1, int* p2)
{
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
//向上调整算法，前面的数据是堆结构才适用
void adjustup(HPDataType* arr, int child)
{
int parents = (child - 1) / 2;
while (child > 0)
{
if (arr[child] > arr[parents])//建立大堆
{
swap(&arr[child], &arr[parents]);
child = parents;
parents = (child - 1) / 2;
}
else
{
break;
}
}
}
//向下调整算法
void adjustdown(HPDataType*arr,int parents,int n)
{
int child = parents * 2 + 1;
while (child < n)
{
//大堆
if (child + 1 < n && arr[child + 1] > arr[child])
{
child++;
}
if (arr[child] > arr[parents])
{
swap(&arr[child], &arr[parents]);
parents = child;
child = parents * 2 + 1;
}
else
{
break;
}
}
}
// 堆的插入
void HeapPush(Heap* hp, HPDataType x)
{
assert(hp);
if (hp->_capacity == hp->_size)
{
//进行扩容
int newcapacity = hp->_capacity == 0 ? 4 : hp->_capacity * 2;
HPDataType* tmp = (HPDataType*)realloc(hp->_a, sizeof(HPDataType) * newcapacity);
if (tmp == NULL)
{
perror("malloc");
return;
}
hp->_a = tmp;
hp->_capacity = newcapacity;
}
hp->_a[hp->_size] = x;
adjustup(hp->_a, hp->_size);
hp->_size++;
}
// 堆顶数据的删除
void HeapPop(Heap* hp)
{
assert(hp);
assert(hp->_size > 0);
swap(&hp->_a[0], &hp->_a[hp->_size - 1]);
hp->_size--;
adjustdown(hp->_a, 0, hp->_size);
}
// 取堆顶的数据
HPDataType HeapTop(Heap* hp)
{
assert(hp);
assert(hp->_size > 0);
return hp->_a[0];
}
// 堆的数据个数
int HeapSize(Heap* hp)
{
assert(hp);
return hp->_size;
}
// 堆的判空
bool HeapEmpty(Heap* hp)
{
return hp->_size == 0;
}
运行结果如下：
堆排序
堆排序使用的核心算法就是向下调整算法，首先用向下调整算法进行建堆。如果建的是大堆（排升序），将堆顶数据与堆中最后一个数据进行交换，再将最后这个数据不算作堆中的数据，然后使用向下调整算法将前面的数据调整成堆，直至能算作堆中的数据为0为止。注意：排升序建大堆，排降序建小堆。
其代码实现如下：
void Heapsort(int* arr, int n)
{
for (int i = (n - 1 - 1) / 2; i >= 0; i--)
{
adjustdown(arr, i, n);
}
int k = n - 1;
while (k >= 0)
{
swap(&arr[0], &arr[k]);//堆顶与最后一个数据进行交换
adjustdown(arr, 0, k);//调整之前的数据，让其成为堆
k--;
}
}
int main()
{
int arr[] = { 3,5,7,6,2,4,1,0,9,8 };
int n = sizeof(arr) / sizeof(arr[0]);
Heapsort(arr, n);
for (int i = 0; i < n; i++)
{
printf("%d ", arr[i]);
}
return 0;
}
堆排序时间复杂度：O(NlogN)
堆排序时间复杂度推导过程:
①首先是将数组进行建堆操作，由上面可知使用的是向下调整算法，这部分时间复杂度是O(N)。
②将堆顶数据与堆中最后一个数据进行交换，然后再将最后这个数据不算做堆中的数据再使用进行向下调整算法。继续上面的操作，直至算作堆中的数据为0为止。这部分时间复杂度是O(NlogN)。这部分推到过程如下：
TopK问题
TopK问题即求数据结合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。
对于Top-K问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了(可能
数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决，基本思路如下：
用数据集合中前K个元素来建堆
前k个最大的元素，建小堆，前k个最小的元素，则建大堆，用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素将剩余N-K个元素依次与堆顶元素比完之后，堆中剩余的K个元素就是所求的前K个最小或者最大的元素。
以下代码实现的是选出k个最大值，通过createdata函数构造数据范围是0-999(为了方便观察，通过手动改写文件，我将这些数字中的5个数改到了5位数)。通过fprintf将生成的数据存放到文件中,通过fscanf函数进行读取文件中的数据。
//向下调整算法,需要保证parents左右子树都是堆
void adjustdown(int* arr, int parents, int n)
{
int child = parents * 2 + 1;
while (child < n)
{
if (child + 1 < n && arr[child + 1] < arr[child])
{
child++;
}
if (arr[parents] > arr[child])//建小堆
{
swap(&arr[child], &arr[parents]);
parents = child;
child = parents * 2 + 1;
}
else
{
break;
}
}
}
void topk(int* arr, int n, int k)
{
FILE* pf = fopen("text.txt", "r");
if (pf == NULL)
{
perror("open file fail");
return;
}
//从文件中读取k个数据
for (int i = 0; i < k; i++)
{
fscanf(pf, "%d", &arr[i]);
}
//将k个数进行建堆
for (int i = (k - 1 - 1) / 2; i >= 0; i--)
{
adjustdown(arr, i, k);
}
int tmp = 0;
while (fscanf(pf, "%d", &tmp) != EOF)
{
if (tmp > arr[0])
{
arr[0] = tmp;
adjustdown(arr, 0, k);
}
}
fclose(pf);
pf = NULL;
}
//创建数据
void createdata(int n)
{
srand((unsigned int)time(0));
FILE* pf = fopen("text.txt", "w");//以写的形式将该文件打开
if (pf == NULL)
{
perror("open file fail");
return;
}
for (int i = 0; i < n; i++)//往文件中写入
{
fprintf(pf, "%d\n", rand() % 1000);//生成0-999的随机数
}
//关闭文件
fclose(pf);
pf = NULL;
}
void test()
{
int n = 100;
//createdata(n);//创建数据，创建好了之后将其注释防止每次生成的数据不一样不便于观察
int k = 0;
scanf("%d", &k);//输入k，表示选出k个最大的数
int* arr = (int*)malloc(sizeof(int) * k);//开辟k个空间
topk(arr, n, k);
for (int i = 0; i < k; i++)
{
printf("%d\n", arr[i]);
}
free(arr);//释放动态开辟的空间
}
int main()
{
test();
return 0;
}
运行结果如下所示（注意这是手动改了文件中的5个数据所输出的结果）：
总结：本文主要介绍了树的一些概念，如树的度，父节点，子节点，兄弟节点等，还介绍了完全二叉树和满二叉树，以及二叉树的一些性质和结论，满二叉树是一种特殊的完全二叉树。还介绍了堆这种数据结构，堆通常使用数组来进行存储的，其中堆最重要的就是利用可使用堆来进行堆排序。通过堆引出了topk问题。对于topk问题通过建立小堆可以选出最大的k个数，建立大堆可选出最小的k个数。感谢大家观看，如有错误不足之处，欢迎大家批评指正！！！
