二叉树—堆（C语言实现）

 一、树的概念及结构

1.树的概念

树是一种非线性的数据结构，它是有n（n > 0）个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一颗倒挂的树，也就是说它是根朝上，而叶朝下。

●  有一个特殊的结点，成为根结点，根结点没有前驱结点

●  除根节点外，其余节点被分成M（M > 0）个互不相交的集合T1、T2、......、Tm，其中每个集合Ti(1 <= i <= m)又是一颗结构与树相类似的子树。每棵子树的根结点有且只有一个前驱，可以有0个或多个后继

●  因此，树是递归定义

注意：树形结构中，子树之间不能有交集，否则就不是树形结构。

2.树的相关概念

3.树的表示

树结构相对线性表就比较复杂，要存储表示起来就比较麻烦，既然保存值域，也要保存结点和结点之间的关系，实际上数有很多表示方式比如：双亲表示法，孩子表示法，孩子双亲表示法以及孩子兄弟表示法等。我们这里就简单的理解其中最常用的孩子兄弟表示法。

typedef int DataType;
struct Node
{struct Node* firstChild1; // 第一个孩子结点struct Node* pNextBrother; // 指向其下一个兄弟结点DataType data; // 结点中的数据域
};

二、二叉树的概念及结构

1.概念

一颗二叉树是节点的一个有限集合，该集合：
1.由一个根结点加上两颗别称为左子树和右子树的二叉树组成

2.或者为空

由上图可知：

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

2.二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树

 注意：对于任意的二叉树都是有以下几种情况符合而成的：

2.特殊的二叉树 

(1)满二叉树：一个二叉树，如果每一层的结点数都要达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且总结点数是，则它就是满二叉树。

(2)完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树印出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点——对应时称之为完全二叉树。要注意的是满二叉树是一种特殊的完全二叉树。

3.二叉树的性质

(1)若规定根结点的层数为1，则一颗树非空二叉树的第i层上最多有个结点。

(2)若规定根结点的层数为1，则深度为h的二叉树的最大结点数是。

(3)对任何一颗二叉树，如果度为0其叶结点个数为n0，度为2的分支结点个数为n2，则有n0=n2+1 

<1>类比归纳（图解） ：

<2>定义推导：

假设二叉树有N个结点

从总结点数角度考虑：N = n0 + n1 + n2   ①

从边的角度考虑，N个结点的任意二叉树，总共有N-1条边

因为二叉树中每一个结点都有双亲，根结点没有双亲，每个结点向上与其双亲之间存在一条边，因此N个结点的二叉树总共有N-1条边。

因为度为0的节点没有孩子，故度为0的节点不产生边；度为1的结点只有一个孩子。故每个度为1的结点产生一条边；度为2的结点有两个孩子，故每个度为2的结点产生两条边，所以总边数为：n1 + 2*n2

故从边的角度考虑：N-1 = n1 + 2*n2   ②

结合①和②得：n0 + n1 + n2 = n1 + 2*n2 - 1

即n0 = n2 + 1

(4)若规定根结点的层数为1，具有n个结点的满二叉树的深度，（是log以2为底,n+1为对数）

(5)对于具有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否则无右孩子 

4.题目 

1. 某二叉树共有 399 个结点，其中有 199 个度为 2 的结点，则该二叉树中的叶子结点数为（B）
A 不存在这样的二叉树
B 200
C 198
D 199

 由性质3：n0 = n2 + 1 = 199 + 1 = 200

2.在具有 2n 个结点的完全二叉树中，叶子结点个数为（A）
A n
B n+1
C n-1
D n/2

度为0 —> n0个，度为1 —> n1个，度为2 —> n2个

因为n0 + n1 + n2 = 2N，n0 = n2 + 1

则2n0 + n1 - 1 = 2N

因为完全二叉树的n1的数量是0 or 1，为了保证等号左侧与等号右侧统一成偶数，此时，n1 = 0

所以n0 = N

3.一棵完全二叉树的结点数位为531个，那么这棵树的高度为（B）
A 11
B 10
C 8
D 12

5.二叉树的存储结构 

二叉树一般有两个结构，一种是顺序结构，一种是链式结构。

(1)顺序结构

顺序结构存储就是使用数组来存储，一般使用数字只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储。

二叉树顺序存储在物理上是一个数组，在逻辑上是一颗二叉树。

(2)链式存储

二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来表示元素的逻辑关系。通常的方法是链表中每个结点右三个域组成，数据域和左右指针域，左右指针分别表示用来给出结点左孩子和右孩子所在的链节点的存储地址。

三、二叉树的顺序结构及实现

普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。现实中我们通常把堆（完全二叉树）使用顺序结构的数组来存储，需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段。

1.堆的概念及结构

如果有一个关键码的集合K={ ，，，……， }，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足： 且（ 且 ）i = 0 , 1 , 2……，则称为小堆（大堆）。将根结点最大的堆交租最大堆或大根堆，根结点最小的堆叫做最小堆会小根堆。

2.堆的性质

（1）堆中某个结点的值总是不大于或不小于其父亲结点的值

（2）堆总是一颗完全二叉树

3.堆的实现

<1>堆的创建图示

通过插入数据和向上调整算法实现，后面会有解释

<2>Heap.h

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>typedef int HPDateType;
typedef struct Heap
{HPDateType* a;int size;int capacity;
}HP;//交换函数
void swap(HPDateType* p1, HPDateType* p2);//初始化和销毁
void HPInit(HP* php);
void HPDestory(HP* php);//向上调整算法
void AdjustUp(HPDateType* a, int child);
//插入数据
void HPPush(HP* php, HPDateType x);void AdjustDown(HPDateType* a, int n, int parent);
//删除数据
void HPPop(HP* php);
//返回堆顶的元素
HPDateType HPTop(HP* php);
//判空
bool HPEmpty(HP* php);

<3>Heap.c

(1)交换函数

//交换函数
void swap(HPDateType* p1, HPDateType* p2)
{HPDateType tmp = *p1;*p1 = *p2;*p2 = tmp;
}

(2)初始化

void HPInit(HP* php)
{assert(php);php->a = NULL;php->capacity = php->size = 0;
}

(3)销毁

void HPDestory(HP* php)
{assert(php);free(php);php->a = NULL;php->capacity = php->size = 0;
}

(4)向上调整算法

//向上调整算法
void AdjustUp(HPDateType* a, int child)
{int parent = (child - 1) / 2;//堆的父子关系while (child > 0){if (a[child] < a[parent])//向上调整{swap(&a[child], &a[parent]);//交换位置child = parent;//最初的parent赋值给childparent = (child - 1) / 2;//重新规划parent}else{break;}}
}

(5)插入数据（建堆）

 堆的创建过程图示：

时间复杂度为：logN 

 

//插入数据
void HPPush(HP* php, HPDateType x)
{assert(php);//空间不够if (php->size == php->capacity){int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;HPDateType* tmp = (HPDateType*)realloc(php->a, newcapacity * sizeof(HPDateType));if (tmp == NULL){perror("realloc fail!");return;}php->a = tmp;php->capacity = newcapacity;}php->a[php->size] = x;//插在数组的结尾php->size++;AdjustUp(php->a, php->size - 1);//传的是下标，用来找父子关系
}

(6)向下调整算法

我们通过从根结点开始的向下调整算法可以把它调整成一个小堆。向下调整算法的前提：左右子树必须是一堆，才能调整。 

//向下调整算法(前提：左右字树是小堆/左右子树是大堆)
void AdjustDown(HPDateType* a,int n,int parent)
{//假设法：先假设左孩子小int child = parent * 2 + 1;//child >= n说明孩子已经不存在了，超出二叉树范围了(叶子)while (child < n)  {//找出小的那个孩子if (a[child] > a[child + 1] && child +1 < n){++child;//让右孩子成为小的}if (a[child] < a[parent]){swap(&a[child], &a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}

(7)删除数据

删除堆是删除堆顶的数据，将堆顶的数据根最后一个数据交换，然后删除数组最后一个数据，在进行向下调整算法

//删除数据(堆顶的数据)
//不能挪动数据，覆盖删除堆顶数据—>关系错乱
//堆顶数据交换到最后一个数据，再删除最后一个数据，在进行向下调整算法
void HPPop(HP* php)
{assert(php);assert(php->size > 0);swap(&php->a[0], &php->a[php->size - 1]);php->size--;//先size--了，缩小数组大小//所以调用完AdjustDown()函数后，交换到最后一位的堆顶元素就已经被删除了AdjustDown(php->a, php->size, 0);}

(8)返回栈顶元素

//返回堆顶的元素
HPDateType HPTop(HP* php)
{assert(php);assert(php->size > 0);return php->a[0];
}

(9)判空

//判空
bool HPEmpty(HP* php)
{assert(php);return php->size == 0;
}

<4>test.c

void TestHeap1()
{int a[ ] = { 2,4,5,6,1,7,8,9 };HP hp;HPInit(&hp);for (size_t i = 0; i < sizeof(a) / sizeof(int); i++){HPPush(&hp, a[i]);}while (!HPEmpty(&hp)){printf("%d ", HPTop(&hp));HPPop(&hp);}
} 
int main()
{TestHeap1();return 0;
}

4.堆的应用 

<1>堆排序 

(1)建堆

升序：建大堆

降序：建小堆

 (2)排序

● 向上调整建堆思想：

例如，我们想得到升序，先建好大堆，再将堆的最后一个元素与栈顶元素交换，此时数组的最后一个空间存储的就是集合中的最大元素（位置锁定了），然后对新的堆顶元素进行向下调整之后，栈顶元素就是集合中第二大的元素。再将栈顶元素与数组的倒数第二个位置进行交换，逐此往复。直到所有元素都锁定了。

向上调整建堆的时间复杂度： O(N*logN)

void swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}
void AdjustUp(int* a, int child)
{int parent = (child - 1) / 2;//堆的父子关系while (child > 0){if (a[child] < a[parent])//向上调整{swap(&a[child], &a[parent]);//交换位置child = parent;//最初的parent赋值给childparent = (child - 1) / 2;//重新规划parent}else{break;}}
}//堆排序
//->时间复杂度：O(N* logN)
//这里我们把数组当做完全二叉树
void HeapSort(int* a, int n)
{//向上调整建堆//降序，建小堆 (升序,建大堆)for (int  i = 0; i < n; i++){AdjustUp(a, i);}int end = n - 1;while (end > 0){//把最大的数换到最后一位swap(&a[0], &a[end]);//在将第一个数向下调整，选出次大的数AdjustDown(a, end, 0);//最后一位数据被固定，数组的范围缩小--end;}
}void TestHeap3()
{int a[] = { 5,4,3,16,17,20 };HeapSort(a, sizeof(a) / sizeof(int));
}
int main()
{TestHeap3();return 0;
}

● 向下调整建堆思想 

以最后一个有子树的元素为根结点所形成的树开始建堆（向下调整算法），下来是以倒数第二个有子树的元素为根节点所形成的树建堆，直到以栈顶元素为根结点所形成的树建堆完成。

 

向下调整建堆的时间复杂度： O(N)

#include<stdio.h>
#include<stdlib.h>
void swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}void AdjustDown(int* a, int n,int parent)
{//建小堆int child = 2 * parent + 1;//先假设左孩子小while (child < n){if (a[child] > a[child + 1]){child++;}if (a[child] < a[parent]){swap(&a[child], &a[parent]);parent = child;child = 2 * parent + 1;}else{break;}}
}void HPSort(int* a, int n)
{//向下调整建堆(从最后一个有子树的元素开始向上建)->666	//数组最后一个元素的小标为n-1for (int i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDown(a, n, i);}
}int main()
{int a[] = { 5,6,2,3,7,8,9,1,4 };int n = sizeof(a) / sizeof(a[0]);HPSort(a, n);for (int i = 0; i < n; i++){printf("%d ",a[i]);}return 0;
}

<2>Top—K问题

即求数据集合中前K个最大的元素或最小的元素，一般情况下数据量都比较大。

对于Top—K问题，能想到的最简单直接的方式就是排序

void TestHeap2()
{int a[] = { 27,15,19,18,28,34,65,49,25,37 };HP hp;HPInit(&hp);for (size_t i = 0; i < sizeof(a) / sizeof(int); i++){HPPush(&hp, a[i]);}//找出最小的前k个int k = 0;scanf("%d", &k);while (k--){printf("%d ", HPTop(&hp));HPPop(&hp);}printf("\n");
}int main()
{TestHeap2();return 0;
}

但是：如果数据量非常大，排序就不太可取了（可能数据都不能快速全部加载到内存中）。

最佳的方式就是用堆来解决。

(1)用数据集合中前K个元素来建堆——>O(K)

求前K个最大的元素，则建小堆

求前K个最小的元素，则建大堆

(2)用剩余的N-K个元素一次与堆顶元素进行比较，不满足则替换堆顶元素——>O((N-K)*logN)

将剩余的N-K个元素一次与对顶元素比较完后，堆中剩余的K歌元素就是所求的前K个最小的或最大的元素。

合计时间复杂度是O(N)

#include<stdio.h>
#include<stdlib.h>
#include<time.h>void swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}void AdjustDown(int* a, int n,int parent)
{//建小堆int child = 2 * parent + 1;//先假设左孩子小while (child < n){if (a[child] > a[child + 1]){child++;}if (a[child] < a[parent]){swap(&a[child], &a[parent]);parent = child;child = 2 * parent + 1;}else{break;}}
}void PrintTopK(int* a, int n, int k)
{// 1. 建堆--用a中前k个元素建堆for (int i = (k - 1 - 1) / 2; i >= 0; i--){AdjustDown(a, n, i);//小堆}// 2. 将剩余n-k个元素依次与堆顶元素交换，不满则则替换for (int j = k; j < n-1; j++){if (a[0] < a[j]){a[0] = a[j];AdjustDown(a, n, 0);}}for (int s = 0; s < k - 1; s++){printf("%d ", a[s]);}printf("\n");
}
void TestTopk()
{int n = 10000;int* a = (int*)malloc(sizeof(int) * n);srand(time(0));for (size_t i = 0; i < n; ++i){a[i] = rand() % 1000000;}a[5] = 1000000 + 1;a[1231] = 1000000 + 2;a[531] = 1000000 + 3;a[5121] = 1000000 + 4;a[115] = 1000000 + 5;a[2335] = 1000000 + 6;a[9999] = 1000000 + 7;a[76] = 1000000 + 8;a[423] = 1000000 + 9;a[3144] = 1000000 + 10;printf("最大的前k个数\n");int k;scanf("%d", &k);PrintTopK(a, n, k);
}
int main()
{TestTopk();return 0;
}

另一种写法，在文件中生成： 

void CreateNDate()
{// 造数据int n = 10000;srand(time(0));const char* file = "data.txt";FILE* fin = fopen(file, "w");if (fin == NULL){perror("fopen error");return;}for (size_t i = 0; i < n; ++i){int x = rand() % 1000000;fprintf(fin, "%d\n", x);}fclose(fin);
}void HeapTest()
{int k;printf("请输入K:");scanf("%d", &k);int* a = (int*)malloc(sizeof(int) * k);if (a == NULL){perror("malloc error");return;}//打开文件，读前k个数const char* file = "data.txt";FILE* fout = fopen(file, "r");if (fout == NULL){perror("fopen error");return;}for (int i = 0; i < k; i++){fscanf(fout,"%d", &a[i]);}//建有k个数的小堆for (int i = (k - 1 - 1) / 2; i >= 0; i--){AdjustDown(a, k, i);}//读取剩下的N-K个int x = 0;while (fscanf(fout,"%d", &x) > 0){if (a[0] < x){a[0] = x;AdjustDown(a, k, 0);}}//打印for (int i = 0; i < k; i++){printf("%d ", a[i]);}printf("\n");
}int main()
{CreateNDate();HeapTest();return 0;
}