C++实现二叉树及堆的示例代码

1 树

树是一种非线性数据结构，它是由n个有限结点组成的具有层次关系的集合。把它叫树是因为它是根朝上，叶子朝下的
来上图瞧瞧

1.1 树的相关名词

2 二叉树

2.1 二叉树的概念

一颗二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根结点加上两棵分别称为左子树和右子树。
如图所示：

二叉树有以下特点：

1、每个二叉树最多有两颗子树，所以二叉树不存在度为2的结点。
2、二叉树的子树有左右之分，其子树的顺序不能颠倒。

2.2 二叉树的性质

1、若规定根结点的层数为第一层，则一颗非空二叉树的第i层上最多有z^(k-1)个结点
2、若规定根结点的层数为第一层，则深度为h的二叉树的最大结点数是2^k-1个。
3、对于任何一颗二叉树，度为0的结点（叶子结点）的个数为n0 ,度为2的结点个数为n2则一定有，n0 = n2 + 1。
4、若规定根结点的层数为第一层,具有N个结点的满二叉树的深度h = log2(N+1)[说明：以2为底的N+1的对数]，这个可以由性质2推导得到。
5、对于具有n个结点的完全二叉树，如果按照从上到下从左到右的数组顺序对所有结点从0开始编号，即对于数组下标i的结点有：
1）i>1,i位置的父结点的在数组中的下标为（i-1）/2.
2)i位置结点的左孩子结点的下标为2i+1,右结点下标为2i+2。

2.3 特殊的二叉树

1、满二叉树：一个二叉树，如果每一层的结点数都达到了最大，如果这个二叉树的层次是k，则其结点数是2^k-1。
2、完全二叉树：用最直白的话来说就是，树的深度或者高度为k，前k-1层的结点都是满的，只有最后的第k层不满但是从左到右的结点必须是连续的。
其实满二叉树是一种特殊的完全二叉树。
如图所示：

图为完全二叉树，要是最后一层全满则为满二叉树。
满足：
2^k-1-x = N;
x的取值范围是[0,2^(k-1)-1]

3 堆

3.1 堆的概念

普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费，而完全二叉树更适合用顺序存储，顺序存储的随机访问特性，会右巨大的优点。我们通常把堆（是一种完全二叉树）采用顺序存储，需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事，一个是数据结构一个是OS中管理内存的一块区域分段。
堆分为大根堆和小根堆。
大根堆：父亲结点>=孩子结点
小根堆：父亲结点<=孩子结点

上面是堆的逻辑结构，下面是物理结构

3.2 堆的实现

首先构建堆我们要了解一个算法，叫向下调整算法。我们以小根堆为例，我们把图示的完全二叉树构建为小堆，这个二叉树有个条件是根结点的两个子树都是小堆才可以进行向下调整算法。

3.2.1 向下调整算法

根结点的左右子树都是小堆，根结点27和左右子树的根结点较小的那一个交换位置，然后依次进行，直到叶子结点。就把最小的15结点上浮到堆顶的位置。这个算法的前提是根节点的左右子树都是小堆，如果我们想把任意的的数组构建成小堆显然不满足条件。在下面我们介绍把任意数组构建成小堆的办法。
向下调整算法的代码如下：

void AdjustDown(HeapDataType* a, int n, int root)
{
	//父子下标的初始化
	int parent = root;
	int child = parent * 2 + 1;
	//循环向下调整，把最小值（或者最大值浮到堆顶）
	while (child < n)
	{
		//选出左右孩子中较小的孩子，作为child，child+1 < n保证下标不能越界
		if (child+1 < n && a[child + 1] < a[child])
		{
			++child;
		}
		//父亲比孩子小二者交换位置,并更新迭代孩子的位置
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			//迭代parent child
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;//当孩子 >= 父亲的时候，满足小堆的条件，跳出循环节课，否则就会死循环
		}
	}
}

3.2.2 堆的构建

把给定的数据化成完全二叉树的逻辑结构如上图所示，这个数组（二叉树）显然不能满足向下调整算法的理想条件，所以我们把问题拆分，比如你先思考下这个问题，把左子树和右子树全部构建成小堆不就满足条件了嘛，但是子树的左右子不是小堆怎么办呢，那么同样的道理，把它也构建成子树就可以了，那么我们可以从叶子结点向上每个结点都执行一边向下调整算法不就可以了嘛。其实我们不必从叶子结点开始因为叶子结点没有子树其实都可以看成是小堆或者大堆。所以从第一个非叶子结点开始调整即可。

也就是从图中紫色圈圈画出来的那个开始调整即可，直到根结点93，就会把一个数组构建成小堆（大堆）。

for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(a, n, i);
	}

（n-1-1）/2为第一非叶子结点下标。

3.2.3 堆排序

有了上面的知识做铺垫，堆排序就可以很好的理解了。
1、把数组构建成大堆或者小堆，位于堆顶的数据就是最大值或者最小值，把堆顶数据和最后的结点位置的数据（数组元素最后一个）互换。然后对前n-1个结点重新向下调整为大堆或者小堆。直到剩下最后一个根节点就排序完成。
只是要升序：构建大堆，要降序：构建小堆，你细细品。
代码如下：

//堆排序
void HeapSort(int* a, int n)
{
	//堆排序的第一步就是构建堆,构建堆的时间复杂度是O(n),此时是小堆
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(a, n, i);
	}
	//如果是升序，构建大堆
	//如果是降序，构建小堆
	//是反着的，因为要和最后一个进行交换
	int end = n - 1;
	while (end>0)
	{
		//把堆顶（最小或者最大）和最后的的元素交换，然后从0到n-2继续向下调整
		//把次小（次大）的元素也选出来，直到剩最后一个，堆排序完成
		Swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);
		--end;
	}
}

### 3.2.4 堆的的增删查改
声明：
```c
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>
#include <windows.h>

typedef int HeapDataType;

typedef struct Heap
{
	HeapDataType* arr;
	int size;
	int capacity;
} Heap;

//堆的初始化，内部有堆的创建
void HeapInit(Heap* php, HeapDataType* a, int n);
//堆的销毁
void HeapDestory(Heap* php);
//堆的插入数据
void HeapPush(Heap* php, HeapDataType x);
//堆的删除数据
void HeapPop(Heap* php);
//获取堆顶数据
HeapDataType HeapTop(Heap* php);
//对传入的数组内的数据进行堆排序
void HeapSort(int* a, int n);

定义：

#include "Heap.h"
//堆是一种完全二叉树，用顺序存储（数组）比较好
//用于交换两个数据
void Swap(HeapDataType* n1, HeapDataType* n2)
{
	HeapDataType temp = *n1;
	*n1 = *n2;
	*n2 = temp;
}
//向下调整算法___老重要了，这是理解堆排序和topk问题以及堆这里相关题的基础
//向下调整结束的情况有两个一个是a[parent]<a[child],另一个是从堆顶到数组结束全部比较完
void AdjustDown(HeapDataType* a, int n, int root)
{
	//父子下标的初始化
	int parent = root;
	int child = parent * 2 + 1;
	//循环向下调整，把最小值（或者最大值浮到堆顶）
	while (child < n)
	{
		//选出左右孩子中较小的孩子，作为child，child+1 < n保证下标不能越界
		if (child+1 < n && a[child + 1] < a[child])
		{
			++child;
		}
		//父亲比孩子小二者交换位置,并更新迭代孩子的位置
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			//迭代parent child
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;//当孩子 >= 父亲的时候，满足小堆的条件，跳出循环节课，否则就会死循环
		}
	}
}
//向上调整算法
//用在HeapPush中
void AdjustUp(HeapDataType* a, int n, int child)
{
	int parent = (child - 1) / 2;
	while (child>0)
	{
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			//迭代
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}
//堆的初始化，内部有堆的创建
void HeapInit(Heap* php, HeapDataType* a, int n)
{
	HeapDataType* temp = (HeapDataType*)malloc(sizeof(HeapDataType)*n);
	if (temp)
	{
		php->arr = temp;

	}
	else
	{
		printf("内存申请失败！");
		exit(-1);
	}
	//将传进来的数组拷贝给malloc出来的空间，用来后续的堆的创建，删除，插入数据等操作
	memcpy(php->arr, a, sizeof(HeapDataType)*n);
	php->size = n;
	php->capacity = n;

	//把拷贝进来的数组，构建成堆
	//从倒数第一个非叶子节点进行构建(直接把数组画成一个完全二叉树可以直接由图得到第一个
	//非叶子节点的下标）
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(php->arr, php->size, i);
	}
}
//堆排序
void HeapSort(int* a, int n)
{
	//堆排序的第一步就是构建堆,构建堆的时间复杂度是O(n),此时是小堆
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(a, n, i);
	}
	//如果是升序，构建大堆
	//如果是降序，构建小堆
	//是反着的，因为要和最后一个进行交换
	int end = n - 1;
	while (end>0)
	{
		//把堆顶（最小或者最大）和最后的的元素交换，然后从0到n-2继续向下调整
		//把次小（次大）的元素也选出来，直到剩最后一个，堆排序完成
		Swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);
		--end;
	}
}

//销毁堆
void HeapDestory(Heap* php)
{
	assert(php);
	free(php->arr);
	php->arr = NULL;
	php->capacity = php->size = 0;
}

//堆的插入数据
void HeapPush(Heap* php, HeapDataType x)
{
	assert(php);
	if (php->size == php->capacity)
	{
		php->capacity *= 2;
		HeapDataType* tmp = (HeapDataType*)realloc(php->arr, sizeof(HeapDataType)*php->capacity);
		if (tmp)
		{
			php->arr = tmp;
		}
		else
		{
			printf("扩容失败！\n");
			exit(-1);
		}
	}
	php->arr[php->size++] = x;
	AdjustUp(php->arr, php->size, php->size - 1);
}

//堆的删除数据,要删除堆顶的数据
void HeapPop(Heap* php)
{
	assert(php);
	assert(php->size > 0);
	Swap(&php->arr[0], &php->arr[php->size - 1]);
	php->size--;
	AdjustDown(php->arr, php->size, 0);
}

//获取堆顶数据
HeapDataType HeapTop(Heap* php)
{
	assert(php);
	assert(php->size > 0);
	return php->arr[0];
}

看这里的小伙伴可以自己下去测试一下代码哦。

到此这篇关于C++实现二叉树及堆的示例代码的文章就介绍到这了,更多相关C++实现二叉树及堆内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！