数据结构——树型结构二叉树与堆的代码功能讲解（1）

目录

一. 二叉树

1.概念

2.二叉树的种类 

3.特殊二叉树 

二.堆

1.定义：

2.性质

小根堆：

大根堆：

三.堆的代码实现——数组形式

1.堆的结构

2.堆的初始化函数

3.在堆中插入数据 

        当插入数据40:

        当插入数据30时：

        当插入数据10时：

        算法函数代码：

        插入数据代码：

        测试：

4.删除堆顶的数据

        向下调整算法示例：

        向下调整算法代码 ：

        删除堆顶数据函数

5.判断堆是否为空函数

---

一. 二叉树

1.概念

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

如图可知道： 

二叉树的基本特点：

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

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

2.二叉树的种类 

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

3.特殊二叉树 

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

如上图为满二叉树，它有4层，那么K=4，所以总结点个数为(2^4)-1=15个，符合条件。

---

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

完全二叉树的节点数范围在：count:[ 2^(K-1)，(2^k)-1 ]  

        满二叉树每一层都是满的；完全二叉树前K-1层都是满的，第K层不一定是满的，但至少有一个节点，而且必须是从左到右依次连续的。

如下图是非完全二叉树：

二.堆

1.定义：

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

注：这里的堆并不是内存空间的区域划分！！！

2.性质

1.堆中某个节点的值总是不大于或不小于其父节点的值；

2.堆总是一棵完全二叉树。

对于性质1：堆可以分为大根堆和小根堆

---

小根堆：

任何一个节点的值都<= 孩子节点的值。

 如图所示，小根堆的最小值在根节点上，下一层的子节点都比其父节点的值多。

大根堆：

任何一个节点的值都>= 孩子节点的值。

 大根堆的最大值在根节点上，父节点的值永远比子节点值多。

---

        堆的物理结构是数组，因为完全二叉树是从上到下，从左到右依次存储的，所以数组很符合连续性。所以堆（完全二叉树）的数据结构实现适合用数组实现：

 当父节点找子节点时：

leftchild=parent*2+1；(左孩子）

rightchild=parent*2+2；(右孩子）

 例：当节点20要寻找自己的子节点时，那么节点20的左子树位置为：1*2+1=3，节点为20的右子树位置为：1*2+2=4，正好符合45和25两个节点的位置！

 当子节点找父节点时：

parent=(leftchild-1) /2；

parent=(rightchild-1) /2；

总的可以结合成一个公式：

parent=(child-1) /2；

例当leftchild=20时，它的位置为1，parent=(1-1)/2=0 ，而rightchild=56时，它的位置为2，parent=(2-1) /2=0，由此可以得出左子树与右子树两个公式找到的结果是一样的，所以直接结合成一个公式，默认按照左子树的公式即可。

那么我们可以用这几个公式去完成数据结构的实现。

三.堆的代码实现——数组形式

1.堆的结构

typedef int HPDataType;
typedef struct HPNode {
	HPDataType* a;    //指向动态开辟的空间
	int size;         //数组中当前存储的数据个数
	int capacity;     //数组可以存放的最大容量
}HP;

堆的物理结构是数组，所以是采用顺序表的动态结构书写的。 

2.堆的初始化函数

//初始化
void HeapInit(HP* php) {
	assert(php);    //断言，判断形参接收到的实参内容是否为空
	php->a = NULL;
	php->size = php->capacity = 0;
}

3.在堆中插入数据 

在插入数据前，需要明白：

        堆的核心就是任何一个节点的值都大于等于或者小于等于子节点的值，要么是小根堆，要么是大根堆。

例如，已经创建了一个符合堆排序的数组：

        该完全二叉树是小根堆，堆顶的元素根节点是整个二叉树中最小的值15。 

        当插入数据40:

         a[100]={15,18,19,27,33,30,42,56,77,90,40}，40是放在数组的末尾的，在逻辑结构中也是放在节点33的左子树位置：

 数据40不会改变堆的结构顺序。

        当插入数据30时：

        当插入数据10时：

        经过这几种情况的变化，总结出：每次插入的数据时候，都需要与其父节点进行比较，若子节点小于等于父节点的值，那么需要转换两者的位置，直到最后子节点的值大于等于父节点才可以！               

        这需要用到一种算法——向上调整算法。这个算法的核心就是通过子节点寻找父节点，进行比较，公式核心是：

算法函数代码：

//交换两个数据的位置
void Swap(HPDataType* p1, HPDataType* p2) {
	HPDataType tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
 
//向上调整算法——用于添加数据后让堆结构顺序继续保持
void Adjustup(HPDataType* a, int child) {
	int parent = (child - 1) / 2;
	while (child > 0) {
		//情况1：当子节点小于父节点时
		if (a[child] < a[parent]) {
			Swap(&a[child], &a[parent]);
			//转换后子节点成为了父节点，但仍需要找到父节点的父节点进行比较
			child = parent;
			parent = (child - 1) / 2;
		}
		//情况2：仍保持堆
		else {
			break;
		}
	}
}

插入数据代码：

//插入x，并继续保持堆
void HeapPush(HP* php, HPDataType x) {
	//断言：实参传过来的不可以为空指针
	assert(php);
	//只要当数组现存储的大小等于数组当前的最大容量时，才可以扩容
	if (php->size == php->capacity) {
		//若大小和容量都为0时，说明需要第一次开辟空间；
		//若大小等于容量且不为0时，说明是数组满了，需要扩容，一般扩二倍
	int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
	HPDataType* tmp = (HPDataType*)realloc(php->a, newcapacity*sizeof(HPDataType));
		//判断是否开辟成功
		if (tmp == NULL) {
			perror("realloc fail");
			return -1;
		}
		php->a = tmp;	
		php->capacity = newcapacity;
	}
	//成功插入数据
	php->a[php->size] = x;	
	php->size++;
	//插入元素还要保持堆
	Adjustup(php->a, php->size - 1);
}

测试：

 

 

 

 每一次节点是都会找比他大的父节点进行调换位置，直到没有它的父节点会比它大才停止。

 

---

4.删除堆顶的数据

删除堆顶数据如下图：

        堆顶的数据15被删除后，堆（完全二叉树）的结构遭到破坏，需要重建堆，在物理结构中，数组a的首元素被删除，其余的元素需要往前挪动一次，若删除多个元素时，就需要挪动n次，所以这种删除方式的时间复杂度为：O(N)。

 

 

 

        这里介绍一种新算法——向下调整算法，该算法的原理是将堆顶元素与堆的最后一个叶子节点交换位置，让堆的最后一个叶子节点成为堆顶元素，让堆顶元素成为最后一个元素，然后直接把最后一个元素删去，之后就逐层向下比较父节点与子节点的大小，若是小根堆，则头尾交换后 ，堆顶父节点就要和它的左右子节点进行比较，堆顶父节点会找比它小的子节点进行交换，以此类推，直到没有它的子节点比他小即可。大根堆则是相反的。

        当堆顶节点被删去后，使用向下调整算法可以重建堆，节点之间的关系破坏较少，而且时间复杂度也大大降低，为O(log2（N) )，这个效率就比O(N)高很多了。

 

向下调整算法示例：

 

 

 向下调整算法的核心在于堆顶元素与下层子节点的关系，所以用到公式：

向下调整算法代码 ：

//向下调整算法——用于删除堆顶数据
void AdjustDown(HPDataType* a, int n, int parent) {
 
    //通过父节点找子节点——默认调换左子节点和父节点
	int minchild = parent * 2 + 1;
 
    //向下寻找时，子节点为数组之外的值
	while (minchild < n) {
        //注：midchild+1位置的节点必须存在才可以进行比较
        //因为默认调换父节点与左子节点，
        //所以应该先比价左子节点与右子节点大小才行
		if (minchild+11]>a[minchild]) {
            //交换
			Swap(&a[minchild + 1], &a[minchild]);
			parent = minchild;
			minchild = parent * 2 + 1;
		}
		else {
			break;
		}
	}
}

删除堆顶数据函数

//删除堆顶元素
void HeapPop(HP* php) {
	assert(php);
	assert(!HeapEmpty(&php));
 
    //交换首尾节点位置
	Swap(&php->a[0], &php->a[php->size-1]);
	php->size--;
    
    //使用向下调整，
	AdjustDown(php->a, php->size, 0);
}

5.判断堆是否为空函数

//判断堆是否为空
bool HeapEmpty(HP* php) {
	assert(php);
	return php->size == 0;
}