数据结构:Heap(二叉树)的基本操作

目录

1.有关二叉树必须知道的几个基本概念

2.有关二叉树的基本操作

2.0有关元素的定义以及要进行的操作

2.1初始化和销毁操作

2.2插入操作以及上调操作

2.2.1插入操作以及上调操作的图解

2.2.2插入操作以及上调操作的代码

2.3删除根元素及其下调操作

2.3.2删除根元素及其下调操作的代码

---

1.有关二叉树必须知道的几个基本概念

完全二叉树：前n-1层满，最后一层未必满，但自左向右是连续的

满二叉树：相较于完全二叉树，最后一层叶子是完全的

经实验可知，数组是实现叉树这种数据结构的最好方式

由图可知

算孩子公式 leftchild= 2parent +1   rightchild=2parent+2

算父亲公式 parent=（child-1）/2

2.有关二叉树的基本操作

2.0有关元素的定义以及要进行的操作

typedef int HPDataType;
typedef struct Heap
{
	HPDataType* a;
	int size;
	int capacity;
}HP;

void HPInit(HP* php);
void HPDestroy(HP*php);

void HPPush(HP* php, HPDataType x);//插入操作
void Swap(HPDataType* px, HPDataType* py);
void AdjustUp(HPDataType* a, int child);//上调操作

void HPPop(HP* php);//删除根操作
void AdjustDown(HPDataType* a, int n, int parent);//下调操作

bool HPEmpty(HP* php);

2.1初始化和销毁操作

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

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

2.2插入操作以及上调操作

2.2.1插入操作以及上调操作的图解

2.2.2插入操作以及上调操作的代码

void HPPush(HP* php, HPDataType x)//入
{
	assert(php);
	if (php->size = php->capacity)
	{
		size_t newcapacity = php->capacity == 0 ? 4 : 2 * php->capacity;
		HPDataType* tmp = (HPDataType*)realloc(php->a, newcapacity * sizeof(HPDataType));
		if (tmp == NULL)
		{
			perror("realloc fail");
		}
		php->a = tmp;
		php->capacity = newcapacity;
	}
	php->a[php->size] = x;
	php->size++;//开辟空间并且插入到最后一个树叶
	AdjustUp(php->a, php->size-1);//将此被插入元素向上调整至合适位置
}

void AdjustUp(HPDataType* a, int child)//将size-1传递给child,让child的初始指向被插入的新元素
{
	int parent = (child - 1) / 2;
	while (child>0)//一旦这个被插入元素到了根部(child=0),停止!
	{
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			child = parent;//将child移动到parent的位置
			parent = (parent - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

void Swap(HPDataType* px, HPDataType* py)
{
	HPDataType temp;
	 temp = *px;
	*px = *py;
	*py = temp;
}

2.3删除根元素及其下调操作

2.3.1删除根元素及其下调操作的图解

2.3.2删除根元素及其下调操作的代码

void HPPop(HP* php)//删除根元素
{
	assert(php);
	assert(php->size > 0);
	Swap(&php->a[0], &php->a[php->size - 1]);
	php->size--;
	AdjustDown(php->a, php->size, 0);
}

//向下调整,就是将新的根元素下移至它的合适的位置
void AdjustDown(HPDataType* a, int n, int parent)
{
	int child = (2 * parent) + 1;
	while (child<n)//n=size
	{
		if (a[child] > a[child + 1])//找小孩子,和小孩子交换,
		{//让最小的孩子成为新根才能保持小堆形态
			child++;//如果左孩子不是小,那么右才是小
		}
		if(a[child]<a[parent])//如果小孩子比父小,那么不符合小堆,需要交换
		{
			Swap(&a[parent], &a[child]);
			parent = child;//更新父下标指向
			child = (2 * parent) + 1;//更新孩子下标指向
		}
		else
		{
			break;
		}
	}
}

3.研究笔记