数据结构-二叉树

数据结构-二叉树_堆

1.二叉树的概念

编辑1.1树的概念与结构

1.2树的相关语

1.3 树的表示

2. ⼆叉树

2.1 概念与结构

2.2 特殊的⼆叉树

2.2.2 完全⼆叉树

2.3 ⼆叉树存储结构

2.3.1 顺序结构

2.3.2 链式结构

3. 实现顺序结构⼆叉树

3.2 堆的实现

3.2.2 向下调整算法

1.二叉树的概念

1.1树的概念与结构

二叉树和上面的图片一样，有一个根，然后生出两个枝，一个枝又长出两个枝，并且每个枝最多长出两个枝。

有一个特殊的节点，叫做根节点，他没有前驱节点
除根结点外，其余结点被分成 M(M>0) 个互不相交的集合 T1、T2、……、Tm ，其中每⼀个集合 Ti(1 <= i <= m) ⼜是⼀棵结构与树类似的⼦树。每棵⼦树的根结点有且只有⼀个前驱，可以有 0 个或多个后继。因此，树是递归定义的。

子树之间是不能有交集的

1.2树的相关语

⽗结点/双亲结点：若⼀个结点含有⼦结点，则这个结点称为其⼦结点的⽗结点；如上图：A是B的⽗结点
⼦结点/孩⼦结点：⼀个结点含有的⼦树的根结点称为该结点的⼦结点；如上图：B是A的孩⼦结点
结点的度：⼀个结点有⼏个孩⼦，他的度就是多少；⽐如A的度为6，F的度为2，K的度为0 树的度：⼀棵树中，最⼤的结点的度称为树的度；如上图：树的度为 6
叶⼦结点/终端结点：度为 0 的结点称为叶结点；如上图： B、C、H、I... 等结点为叶结点分⽀结点/⾮终端结点：度不为 0 的结点；如上图： D、E、F、G... 等结点为分⽀结点
兄弟结点：具有相同⽗结点的结点互称为兄弟结点(亲兄弟)；如上图： B、C 是兄弟结点比特就业课
结点的层次：从根开始定义起，根为第 1 层，根的⼦结点为第 2 层，以此类推；
树的⾼度或深度：树中结点的最⼤层次；如上图：树的⾼度为 4
结点的祖先：从根到该结点所经分⽀上的所有结点；如上图： A 是所有结点的祖先
路径：⼀条从树中任意节点出发，沿⽗节点-⼦节点连接，达到任意节点的序列；⽐如A到Q的路径为： A-E-J-Q；H到Q的路径H-D-A-E-J-Q
⼦孙：以某结点为根的⼦树中任⼀结点都称为该结点的⼦孙。如上图：所有结点都是A的⼦孙
森林：由 m（m>0）棵互不相交的树的集合称为森林；

1.3 树的表示

孩⼦兄弟表⽰法：树结构相对线性表就⽐较复杂了，要存储表⽰起来就⽐较⿇烦了，既然保存值域，也要保存结点和结点之间的关系，实际中树有很多种表⽰⽅式如：双亲表⽰法，孩⼦表⽰法、孩⼦双亲表⽰法以及孩⼦兄弟表⽰法等。我们这⾥就简单的了解其中最常⽤的孩⼦兄弟表⽰法

struct TreeNode
{
struct Node* child; // 左边开始的第⼀个孩⼦结点
struct Node* brother; // 指向其右边的下⼀个兄弟结点
int data; // 结点中的数据域
};

1.4 树形结构实际运⽤场景⽂件系统是计算机存储和管理⽂件的⼀种⽅式，它利⽤树形结构来组织和管理⽂件和⽂件夹。在⽂件系统中，树结构被⼴泛应⽤，它通过⽗结点和⼦结点之间的关系来表⽰不同层级的⽂件和⽂件夹之间的关联。

2. ⼆叉树

2.1 概念与结构

在树形结构中，我们最常⽤的就是⼆叉树，⼀棵⼆叉树是结点的⼀个有限集合，该集合由⼀个根结点加上两棵别称为左⼦树和右⼦树的⼆叉树组成或者为空。

从上图可以看出⼆叉树具备以下特点：

1. ⼆叉树不存在度⼤于 2 的结点
2. ⼆叉树的⼦树有左右之分，次序不能颠倒，因此⼆叉树是有序树

2.2 特殊的⼆叉树

满二叉树和名字一样，就是每层的节点数都到达最大数。

⼀个⼆叉树，如果每⼀个层的结点数都达到最⼤值，则这个⼆叉树就是满⼆叉树。也就是说，如果⼀个⼆叉树的层数为 K ，且结点总数是2^k-1.

2.2.2 完全⼆叉树

完全二叉树和满二叉树又不同，完全⼆叉树是效率很⾼的数据结构，完全⼆叉树是由满⼆叉树⽽引出来的。对于深度为 K 的，有 n 个结点的⼆叉树，当且仅当其每⼀个结点都与深度为K的满⼆叉树中编号从 1 ⾄ n 的结点⼀⼀对应时称之为完全⼆叉树。要注意的是满⼆叉树是⼀种特殊的完全⼆叉树。

2.3 ⼆叉树存储结构

2.3.1 顺序结构

无非就创建一个数组，挨个存二叉树的数据，根节点无疑是0，然后他的两个孩子节点就是1和2,1的两个孩子节点就是4和5，以此类推。

2.3.2 链式结构

链式结构更容易想象到，就是每个节点有两个指向，一个指向左孩子，一个指向右孩子，然后每个节点都存储数据。

3. 实现顺序结构⼆叉树

顺序结构实现二叉树一般使用堆的方式，

堆又分为大堆和小堆

小堆：根节点是最小的数据，每个节点都比他的父节点大
大堆：和小堆刚相反，根节点最大，每个节点都比父节点大

并且堆是一种完全而二叉树

3.2 堆的实现

头文件Heap.h

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
typedef int HPDataType;
typedef struct Heap
{
	HPDataType* arr;
	int size;
	int capacity;
}HP;
void HPInit(HP* php);
void HPPush(HP* php,HPDataType x);
void HPPop(HP* php);
void HPDestory(HP* php); 
bool HPEmpty(HP* php);

Heap.c

#include"Heap.h"
void HPInit(HP* php)
{
	php->arr = NULL;//你的初始化有问题，这里size是多少你自己想想看呢
	php->capacity = php->size=0;
}
void Swap(int* x, int* y)
{
	int* tmp = *x;
	*x = *y;
	*y = *x;
}
void AdjustUp(HP* php)
{
	int child = php->size - 1;
	int parent = (php->size - 1) / 2;
	
	while (child>0)
	{
		if (php->arr[parent] > php->arr[child])
		{
			Swap(&php->arr[parent], &php->arr[child]);
			child = parent;
			parent = (child - 1) / 2;

		}
		else
		{
			break;

		}

	}
}
void HPPush(HP* php, HPDataType x)
{
	assert(php);
	//判断空间是否足够
	if (php->size == php->capacity)
	{
		//扩容
		int newCapacity = php->capacity == 0 ? 4 : 2 * php->capacity;//所以到了这边你的cap也有问题导致你后面realloc出错
		HPDataType* tmp = (HPDataType*)realloc(php->arr, newCapacity * sizeof(HPDataType));
		if (tmp == NULL)
		{
			perror("realloc fail!");
			exit(1);
		}
		php->arr = tmp;
		php->capacity = newCapacity;
	}
	php->arr[php->size] = x;

	AdjustUp(php);

	++php->size;
}
void AdjustDown(HP* php)
{

	int parent = 0;
	int child = 2 * parent + 1;
	while (child < php->size)
	{
		if (child + 1 < php->size && php->arr[child] > php->arr[child + 1])
		{
			child++;
		}
		if (php->arr[parent] > php->arr[child])
		{
			Swap(&php->arr[parent], &php->arr[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		
		else
		{
			break;

		}
	}
		
}
void HPPop(HP* php)
{
	Swap(&php->arr[0], &php->arr[php->size-1]);
	--php -> size;
	AdjustDown(php);



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


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