【手撕数据结构】二叉树和堆

树的概念

• 树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的
  
• 有一个特殊的结点，称为根结点，根节点没有前驱结点
• 除根节点外,每棵子树的根结点有且只有一个前驱，可以有0个或多个后继
• 树是递归定义的
• ⼀棵N个结点的树有N-1条边

树的相关概念

• 叶节点或终端节点：度为0的节点称为叶节点； 如上图：B、C、H、I…等节点为叶节点
• 节点的度：一个节点含有的子树的个数称为该节点的度； 如上图：A的为6
• 双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点； 如上图：A是B的父节点
• 孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点； 如上图：B是A的孩子节
• 树的度：一棵树中，最大的节点的度称为树的度； 如上图：树的度为6
• 节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；
• 树的高度或深度：树中节点的最大层次； 如上图：树的高度为4

二叉树

二叉树的概念

一棵二叉树是结点的一个有限集合，该集合:

• 或者为空
• 由一个根节点加上两棵别称为左子树和右子树的二叉树组成
  
• 二叉树不存在度大于2的结点（节点的度是含含有子树节点个数的数）
• 二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树
  

满二叉树和完全二叉树

• 满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是
  说，如果一个二叉树的层数为K，且结点总数是 2^k-1，则它就是满二叉树。
  
• 完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K
  的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点（从左到右）一一对
  应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。
  
  ##求满二叉树和完全二叉树的高度

堆的概念与结构

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

堆的性质

• 堆的子节点总是大于或小于根节点
• 堆总是一颗完全二叉树

基本了解堆的概念后，我们来看看琢磨一下什么是大根堆和小根堆

• 父节点(parent)和子节点(child)的下标关系(堆底层是一个数组)
  【lchild = parent * 2 + 1】 左孩子
  【rchild = parent * 2 + 2】 右孩子
  parent = (child - 1) / 2】

堆的向上调整算法

思路分析

• 对于向上调整，从字面意思上看就是从下往上左一个调整，那具体是怎么一个调整法呢，我们看下面
  
• 可以看到向上调整算法实际上就是在堆底插入数据的时候，我们需要保证插入这个数据后这个堆还是一个大根堆或者小根堆，大根就是保证父节点一定比子节点大，小根就是保证父节点一定比子节点小，所以我们需要把插入的数据与他的父节点进行比较，例如小跟堆，如果比父节点大不需要交换，如果比父节点小就需要交换

代码详细解说

• 首先我们应该知道出入什么参数，我们需要改变堆，堆实际是一个用结构体定义的顺序表，所以第一个参数是需要传结构体指针,第二我们需要找父节点与孩子节点进行比较，要求父节点就是(child-1)/2,所以我们需要传孩子节点。

void Adjust_UP(Hp* hp, int child)
1

• 有了这个新入的孩子后，我们就要去查找到它的父亲，因为是要和它的父亲去做一个对比，前面我们有说到过怎么通过一个孩子去找它的父亲，忘了的再翻上去找找哦

int parent = (child - 1) / 2;
1

• 找到父节点后就需要和孩子节点进行比较(这里举例大根堆)，如果孩子比父节点大，就交换

if (hp->a[child] > hp->a[parent])
	swap(&hp->a[child], &hp->a[parent]);		//交换孩子和父亲，逐渐变为大根堆

1
2
3

• 但是呢我们交换一次就可以了吗❓那当然不是，这是一个不断进行调整的过程，所以我们每次在交换完后需要再次去更新父亲和孩子的值，然后将这段逻辑放到一个循环里。若是调整到符合堆的性质了，就break跳出这个循环

那么什么时候不用交换了呢？要么循环过程中，父节点不再比孩子节点小，要么孩子节点已经到达下标为0(也就是祖宗节点)也可以说是堆顶

//while (parent >= 0)	这样写不好，程序会非正常结束
while (child  > 0)
{
	if (hp->a[child] > hp->a[parent])
	{
		swap(&hp->a[child], &hp->a[parent]);		//交换孩子和父亲，逐渐变为大根堆
		//迭代 —— 交替更新孩子和父亲
		child = parent;		
		parent = (child - 1) / 2;
	}
	else {
		break;		//若是比较无需交换，则退出循环
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

以下整体代码:

/*交换函数*/
void swap(HpDataType* x1, HpDataType* x2)
{
	HpDataType t = *x1;
	*x1 = *x2;
	*x2 = t;
}

1
2
3
4
5
6
7
8

/*向上调整算法*/
void Adjust_UP(Hp* hp, int child)
{
	int parent = (child - 1) / 2;

	//while (parent >= 0)	这样写不好，程序会非正常结束
	while (child  > 0)
	{
		if (hp->a[child] > hp->a[parent])
		{
			swap(&hp->a[child], &hp->a[parent]);		//交换孩子和父亲，逐渐变为大根堆
			//迭代 —— 交替更新孩子和父亲
			child = parent;		
			parent = (child - 1) / 2;
		}
		else {
			break;		//若是比较无需交换，则退出循环
		}
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

堆的向下调整算法

• 对于向下调整算法这一块，在后面堆的数据结构中的删除堆顶数据和堆排序都需要用到它，因此重点掌握

算法图解分析

• 对于向下调整算法，前提很重要就是保证他的左子树和右子树是大堆或者小堆，才能从堆顶进行向下调整。
  

• 此时就需要使用到这个【向下调整算法】，当然我这个是大堆的调整，小堆的话刚好相反。原理：找出当前结点的两个孩子结点中教大的那一个换上来，将这个【18】换下去，但是呢此时还不构成大堆，因此我们还需要再去进行一个调整，一样是上面的找法，然后直到这个【18】的孩子结点到达【n - 1】就不作交换了，因为【n - 1】就相当于是位于数组下标的最后一个值

代码详解分析

• 首先也是对所需参数进行分析，我们需要结构体定义的一个堆进行调整，所以需要指向这个堆的结构体指针，还需要找孩子节点进行根父节点进行比较，而公式2 * parent + 1（左孩子）,2 * parent +2(右孩子),所以传parent,然后我们需要孩子节点到达 n - 1的时候结束调整(n是有效数据个数)

void Adjust_Down(int* a, int n, int parent)

1
2

• 因为我们是需要和孩子结点中大的那个做交换，因为我这里是直接假设左孩子比较大
  那么如果右孩子大呢？这就需要比较左孩子和右孩子谁大了，但注意右孩子下标不能超过 n 否则会越界

		//判断是否存在右孩子，防止越界访问
if (child + 1 < n && a[child + 1] > a[child])
{
	++child;		//若右孩子来的大，则转化为右孩子
}

1
2
3
4
5
6

• 然后是循环内部的逻辑，和【向上调整算法】一样，就是一个比较和迭代更新的过程

if (a[child] > a[parent])
{
	swap(&a[child], &a[parent]);
	parent = child;
	child = parent * 2 + 1;
}
else {
	break;
}

1
2
3
4
5
6
7
8
9
10

下面是全部代码

/*向下调整算法*/
void Adjust_Down(int* a, int n, int parent)
{
	int child = parent * 2 + 1;		//默认左孩子来得大
	while (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;
		}
	

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

堆的各个接口

堆的定义及声明

• 首先看到结构体的定义及声明，是不是回想起了我们之前所学的顺序表，因为顺序表的底层其实也是一种数组

typedef int HpDataType;
typedef struct Heap {
	HpDataType* a;
	int size;
	int capacity;
}Hp;

1
2
3
4
5
6
7

堆的初始化

/*初始化堆*/
void HeapInit(Hp* hp)
{
	assert(hp);
	hp->a = NULL;
	hp->size = hp->capacity = 0;
}

1
2
3
4
5
6
7
8

• 和顺序表一样

堆的销毁

/*销毁堆*/
void HeapDestroy(Hp* hp)
{
	assert(hp);
	if(hp->a)
	{
		free(hp->a);
		hp->a = NULL;
		hp->size = hp->capacity = 0;
	}
}

1
2
3
4
5
6
7
8
9
10
11
12

• 这里要注意只释放首地址，因为底层是数组，数组是一块连续的空间所以只需要释放首地址就可以全部释放了。

堆的插入

• 在堆底插入也就是数组末尾，然后为了保证他是大根堆或者小根堆，需要进行向上调整。

/*堆的插入*/
void HeapPush(Hp* hp, HpDataType x)
{
	assert(hp);
	//扩容逻辑
	if (hp->size == hp->capacity)
	{
		int newCapacity = hp->capacity == 0 ? 4 : hp->capacity * 2;
		HpDataType* tmp = (HpDataType*)realloc(hp->a, newCapacity * sizeof(HpDataType));
		if (tmp == NULL)
		{
			perror("fail realloc");
			exit(-1);
		}
		hp->a = tmp;
		hp->capacity = newCapacity;
	}
	hp->a[hp->size] = x;
	hp->size++;

	Adjust_UP(hp, hp->size - 1);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

• 注意向上调整传参的时候孩子节点减1，因为插入的时候自增到了下一个空白节点，但是我们要调整的是插入的节点。所以减1

堆的删除

• 首先可以来看下代码，可以看到很显目的一句，就是交换【a[0]】和【a[hp->size - 1]】，这其实值的就是堆顶的结点和堆顶的末梢结点，为什么先要交换它们呢，我们来分析一下
• 注意删除堆的数据是删除堆顶
• List item

数据

/*堆的删除*/
void HeapPop(Hp* hp)
{
	assert(hp);
	assert(hp->size > 0);
	//首先交换堆顶和树的最后一个结点 —— 易于删除数据，保护堆的结构不被破坏
	swap(&hp->a[0], &hp->a[hp->size - 1]);
	hp->size--;		//去除最后一个数据

	Adjust_Down(hp->a, hp->size, 0);
}

1
2
3
4
5
6
7
8
9
10
11
12

改写族谱，关系紊乱