数据结构--二叉树和堆

目录

1.基本概念

2.树的遍历方法

3.满二叉树&&完全二叉树

4.逻辑结构&&物理结构

5.推理公式

6.二叉树应用--堆

7.简单实现堆

---

1.基本概念

（1）这个里面的概念还是比较多的，但是大部分我们只需要了解即可，因为这个我们在离散数学里面已经学习过一些理论知识，这个地方就不在进行这个详细的赘述了；

（2）重点就是知道这个叶子结点和终端节点，双亲节点，孩子节点，树的高度，树的高度是从1开始的，这个是和离散数学里面相互区别点一个点，重点记忆一下就行了；

（3）每一个树都是有很多的节点组成的，但是这个节点都有自己的分支，我们把一个节点的分支的个数叫做这个节点的度，其中所有节点里面的度数的最大值就是这个树的度；

2.树的遍历方法

（1）我们知道这个树肯定是有这个val表示这个节点的数值，但是这个具体要定义多少个指针，这个是不确定的，因为我们的这个树的节点的个数是不确定的；

（2）这个时候一个很厉害的定义方法就出来了，不是这个树里面的节点个数不确定吗，这个时候我们只需要定义两个节点，一个节点就是左边节点，一个节点就是右边节点；

（3）在实现这个数据结构的时候，我们只需要先定义一个指针指向这个左边的节点，让后通过一个循环，让这个节点指向他右边的兄弟节点，如果没有的话就会直接到下一个父节点，这个就可以实现这个树的遍历；

3.满二叉树&&完全二叉树

（1）满二叉树：每一个节点都有两个子节点，一个是左边的节点，一个是右边的节点；

（2）完全二叉树：上面的每一层都是满的，但是最后一层没有满，满二叉树就是特殊的完全二叉树，后面的大部分介绍对于这个满二叉树通常都是使用的完全二叉树；

4.逻辑结构&&物理结构

（1）我们之前学习这个链表就介绍过这个逻辑结构和物理结构，这个逻辑结构就是这个我们自己想的图，例如这个脸表里面不同的节点之间使用一个有方向的箭头相互连接，实际上真实存在的这个链表之间通过指针就会直接找到下一个节点了，这个箭头就是我们认为的构想出来的，实际上就是不存在的；

（2）在二叉树里面，我们的这个完全二叉树（实际上是满二叉树）也是我们认为臆想出来的，在真实存储的时候，这个是使用数组的方式进行存储的；

（3）对于一个数组的序列，我们也是可以快速地画出它的逻辑结构的，直接按照这个父子节点的顺序排列即可；

5.推理公式

（1）通过一个数组，我们可以画出对应的逻辑结构，我们接下俩就是想要得到通过这个父节点的下标，找到这个子节点的下标，通过子节点的下边，推理出来这个父节点的下标；

（2）已知这个父节点下标i，左子树就是i*2+1,右子树就是i*2+2，已知这个子树的下标j,这个时候他的父亲节点的下标就是(j-1)/2因为这个进行的除法运算，这个时候即使两个子节点对应同一个父亲节点，这个也是可以计算出来的；

（3）我们上面介绍的这个满二叉树的逻辑结构就是一个数组，但是对于一个完全二叉树（非满二叉树），如果还是使用数组进行表示，这个时候就会造成这个空间的浪费，因为这个，满二叉树和完全二叉树都是有顺序的，我们对于这个完全二叉树里面没有节点的位置，就相当于是浪费一个数组的空间，因为这个地方如果放数据，我们上面的这个父子节点下标的推理公式就不成立了；

6.二叉树应用--堆

（1）这里的堆是一种数据结构，和我们之前在C语言里面说的malloc在对堆上面开辟空间的“堆”虽然写法是一样的，但是真正的意义是不一样的，malloc是操作系统里阿米的一个区域，我们在这个区域上面开辟内存空间，和这里的数据结构对截然不同，我们在数据结构里面学习的堆是用来排序的，是一种算法；

（2）堆的分类：大堆和小堆，这个定义是根据这个子节点和父亲节点val值的大小确定的，当一个二叉树里面的任何一个父亲节点的数值都大于这个子节点的，我们就称之为一个大堆，反之就是一个小堆；

（3）通过观察我们不难发现，小堆根是最小的，大堆的根是最大的，这个就可以找到一组数据里面的极值，后续我们回去学习这个如何把一个不是堆序列的数据经过这个顺序的变换使之成为这个大堆或者小堆，或者说是这个本来开始就是一个堆序列，经过数据的添加删除之后，他依然还是一个堆序列；

（3）堆的实质就是一个完全二叉树，这个就是堆和二叉树的联系；

7.简单实现堆

（1）头文件

typedef int HPDataType;
 
typedef struct Heap
{
	HPDataType* a;
	int size;
	int capacity;
}HP;
 
void Swap(HPDataType* p1, HPDataType* p2);
void AdjustUp(HPDataType* a, int child);
void AdjustDown(HPDataType* a, int n, int parent);
 
void HPInit(HP* php);
void HPDestroy(HP* php);
void HPPush(HP* php, HPDataType x);

这个里面包括这个数组的初始化，销毁，数据的插入，向上调整，向下调整；

（2）对一个简单的对堆，实际上就是一个数组，只不过结构上面更加体系化，我们想要插入数据，如果这个数据插入之后，原来的小堆还是小堆，这个直接插入即可，但是如果不是，我们就需要调整，因为这个小堆的父节点的值小，说明我们这个时候插入的数据比这个父节点还小，我们就需要要向上调整，把这个插入的节点和祖先节点进行比较，直到满足这个小堆的定义才停止；

因为我们插入的数据更加小，这个函数实现的就是向上调整；

void AdjustUp(HPDataType* a, int child)
{
	// 初始条件
	// 中间过程
	// 结束条件
	int parent = (child - 1) / 2;
	//while (parent >= 0)
	while (child > 0)
	{
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

（3）如果我们想要实现堆的删除，这个地方的删除不是删除最后一个节点，这样的话直接size--即可，完全没有其他必要了，我们要删除的是这个堆顶部元素节点；

删除的方法就是把这个堆的顶部节点和这个最后一个节点互换，我们再size--把这个节点删除，这个时候堆的顶部节点删除了，但是这个时候肯定是不满足堆的定义的，因为我们把这个堆顶元素换掉了啊，我们这个时候就需要把这个节点向下进行查找，直到符合这个堆的定义才停止；仔细观察我们会发现，这个实际上就是一个简单的排序了，但是这个还不是真正的堆排序，但是前期阶段我们可以这样进行理解；

下面是这个向下调整的实现代码：

void AdjustDown(HPDataType* a, int n, int parent)
{
	// 先假设左孩子小
	int child = parent * 2 + 1;
 
	while (child < n)  // child >= n说明孩子不存在，调整到叶子了
	{
		// 找出小的那个孩子
		if (child + 1 < n && a[child + 1] < a[child])
		{
			++child;
		}
 
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}