文章目录

• 树
• • 树的相关概念
  • 树的表示
  • • 孩子兄弟表示法
  • 特殊的二叉树
  • • 满二叉树
    • 完全二叉树
  • 二叉树性质
  • • • 二叉树的顺序结构
    • 堆
    • • 小根堆
      • 大根堆
    • 堆的实现
    • • 堆的初始化
      • 堆向上调整算法（logN)
      • 堆的插入
      • 向下调整算法
      • 堆的删除
      • 拿到堆顶的数据
      • 获取堆的数据个数
      • 堆是否为空
    • 堆排序
    • • 升序
    • 建堆时间复杂度
    • TOP-K问题

树

是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做树是因
为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。

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

注意：树形结构中，子树之间不能有交集，否则就不是树形结构

树的相关概念

• 节点的度：一个节点含有的子树的个数称为该节点的度； 如上图：A的为6

• 叶节点或终端节点：度为0的节点称为叶节点； 如上图：B、C、H、I…等节点为叶节点

• 非终端节点或分支节点：度不为0的节点； 如上图：D、E、F、G…等节点为分支节点

• 双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点； 如上图：A是B的父节点

• 孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点； 如上图：B是A的孩子节点

• 兄弟节点：具有相同父节点的节点互称为兄弟节点； 如上图：B、C是兄弟节点

• 树的度：一棵树中，最大的节点的度称为树的度； 如上图：树的度为6

• 节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；

• 树的高度或深度：树中节点的最大层次； 如上图：树的高度为4

• 堂兄弟节点：双亲在同一层的节点互为堂兄弟；如上图：H、I互为兄弟节点

• 节点的祖先：从根到该节点所经分支上的所有节点；如上图：A是所有节点的祖先

• 子孙：以某节点为根的子树中任一节点都称为该节点的子孙。如上图：所有节点都是A的子孙

• 森林：由m（m>0）棵互不相交的树的集合称为森林

树的表示

孩子兄弟表示法

树结构相对线性表比较复杂，存储起来比较麻烦，树既然保存值域，也要保存结点和结点之间
的关系 ，我们采用常用的孩子兄弟表示法 ，即左孩子右兄弟 ，右兄弟是指亲兄弟 ，不是表（堂）兄弟

A 的第一个孩子是B ，A 只指向B ，B的亲兄弟是C ，B指向第一个孩子节点D ，D指向亲兄弟节点E 、F

typedef int DataType;
struct TreeNode
{
	struct TreeNode* firstChild1;//第一个孩子节点 

	struct TreeNode* pNextBrother;//指向其下一个兄弟节点 
	DataType data;

};

特殊的二叉树

满二叉树

一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是
说，如果一个二叉树的层数为K，根据等比数列求和 算出 (2^k) - 1 ，则它就是满二叉树

完全二叉树

高度为k的完全二叉树 , 前 k -1 都是满的 ,最后一层要求从左到右是连续的, 满二叉树是一种特殊的完全二叉树 ,完全二叉树节点个数最大是满二叉树的状态 ,个数为(2^k)-1

完全二叉树节点个数最小是前k-1 层的总数再加上第K层的第一个节点 ，前k-1 层的总数是2 ^(k-1) -1 ，所以个数是 2 ^ (k-1 )

二叉树性质

对任何一颗二叉树,如果度为0其叶节点数为n0 ，度为2的分支节点个数为n2 ,则有n0 = n2 +1
度为0的永远比度为2的多一个节点
对于一颗完全二叉树n1要么为0 要么是1

二叉树的顺序结构

普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结
构存储。现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储，需要注意的是这里的堆和操作系统
虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段。

完全二叉树的值在数组位置中父子下标的关系
parent = (child-1) /2
leftchild = parent *2 +1
rightchild =parent *2 +2

堆

堆的性质：
堆中某个节点的值总是不大于或不小于其父节点的值；
堆总是一棵完全二叉树。

小根堆

树中所有父亲都小于或等于孩子

大根堆

树中所有父亲都大于或等于孩子

堆的实现

堆的初始化

void HeapInit(Heap* php)
{
	assert(php);
    php->a = (HeapDataType*)malloc(sizeof(HeapDataType) *4);
	if (php->a == NULL)
	{
		printf("malloc fail");
		exit(-1);
	}
	php->capacity = 4;
	php->size = 0;
}

堆向上调整算法（logN)

前提 ： 左右子树必须是大堆或者小堆

向堆中插入数据，需要使用向上调整算法，因为向堆中插入数据是将数据插入到下标为size的位置，插入一个数据，size++,此时可能就不满足小堆（或大堆），因此要对其进行调整

向上调整算法
先将元素插入到堆的末尾,即最后一个孩子之后
从插入的结点位置开始和父节点比较
插入之后如果堆的性质遭到破坏,将新插入的节点顺着双亲往上调整到合适的位置即可

void AdjustUp(HeapDataType* a, int child) //向上调整算法
{
	int parent = (child-1)/2; //父子节点下标关系推论
	while (child >0 )
	{
		//大队根
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			//向上调整
			child = parent;
			parent = (child - 1) / 2;//更新parent
		}
		//不满足大堆根条件
		else
		{
			break;
		}
	}
}

堆的插入

插入一个数据是插入到数组的末尾，即树形结构的最后一层的最后一个结点，插入数据仍然需要保持堆的结构，所以插入数据后需要使用堆的向上调整算法对堆进行调整

void HeapPush(Heap* php, HeapDataType x)
{
	assert(php);
	if (php->capacity == php->size)
	{
		//扩容
		HeapDataType*  tmp = (HeapDataType *)realloc(php->a, sizeof(HeapDataType) * php->capacity * 2);
		//扩容失败
		if (tmp == NULL)
		{
			printf("realloc fail");
			exit(-1);
		}

		//扩容成功
		php->a = tmp;
		php->capacity *= 2;

	}
	php->a[php->size] = x;
	php->size++;
	AdjustUp(php->a, php->size-1);
}

以大堆根为例 ，插入一个60

向下调整算法

前提 ： 左右子树必须是大堆或者小堆

从根节点处开始，选出左右孩子中值较大的孩子
父节点和较大的子节点进行比较, 如果父节点的数据比大的那个孩子结点的数据要小，那就进行交换

在选左右孩子节点较大的时候，我们可以使用假设逻辑 ，假设默认左孩子大于右孩子， 如果左孩子大于右孩子 ，则假设成立 , 如果左孩子小于右孩子 ，child++ ,指向右孩子节点

最坏的情况下调整到叶子节点为止
那如何判断是否调整到叶子节点？ 如果调整到叶子节点，也就意味着没有子节点，换句话说就是子节点超出了数组的范围

这里以大堆为例 ,以5为根节点的左右子树，都满足大堆的性质，只有根节点不满足大堆的性质，因此只需要将根节点向下调整到合适的位置，即可形成堆结构

void AdjustDown(HeapDataType* a, int n, int parent) // parent 是下标 , n 是数组元素个数
{
	int child = parent * 2 + 1; // 父子节点之间的关系
	while (child < n ) //调整到叶子节点结束 ,即超出数组范围
	{ 
		//以大堆为例 ， 左右孩子比较 ，选出较大值
		//假设默认左孩子大于右孩子 
		if ( child+1<n && a[child + 1] > a[child])  // 右孩子是否存在 ，防止越界
		{
			child++; //如果右孩子存在,并且右孩子结点的数据大于左孩子结点的数据，就child++,此时child指向右孩子结点，这样永远保证是左右孩子的较大值 
		}
		if (a[child] > a[parent])
		{

			Swap(&a[child], &a[parent]); // 交换
			parent = child;
			child = parent * 2 + 1; //更新子节点
		}
		else
		{
			break; 
		}
	}
}

堆的删除

堆的删除以大堆根为例
如果直接挪动数据 ，时间复杂度为O(N) ，且破化了堆中的父子兄弟关系 ,堆的删除采用向下调整算法

堆的删除其实就是删除堆顶元素(最大的元素）
先将数组末尾的元素与堆顶元素交换，size-- , 堆顶元素就被删除了
删除堆顶数据之后 ，堆的结构就被破坏了 ，使用向下调整算法 ，恢复堆的结构

void HeapPop(Heap* php) // 删除 
{
	assert(php);
	assert(!HeapEmpty(php));
	// 堆顶和数组最后一个元素交换
	Swap(&php->a[0], &php->a[php->size - 1]);
	php->size--; //删除
	//向下调整算法
	AdjustDown(php->a, php->size , 0);

}

拿到堆顶的数据

获取堆顶的数据，即返回数组下标为0的数据

HeapDataType  HeapTop(Heap* php) // 拿到堆顶的数据
{
	assert(php);
	return php->a[0];
}

获取堆的数据个数

获取堆的数据个数，即返回堆结构体中的size变量

int HeapSize(Heap* php)// 获取堆的数据个数
{
	assert(php);
	return php->size;
}

堆是否为空

堆的判空，即判断堆结构体中的size变量是否为0

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

完整代码
Test.c

#include"Heap.h"

void TestHeap1()
{
	Heap hp;
	HeapInit(&hp);
	HeapPush(&hp , 70);
	HeapPush(&hp, 56);
	HeapPush(&hp, 30);
	HeapPush(&hp, 25);
	HeapPush(&hp, 15);
	HeapPush(&hp, 10);
	HeapPush(&hp, 20);
	HeapPush(&hp, 60);

	//打印
	int k = 0;
	scanf_s("%d",&k);
	while (!HeapEmpty(&hp) && k--)
	{
		printf("%d ", HeapTop(&hp));
		HeapPop(&hp);
	}
	printf("\n");



}
 void TestHeap2()
{
	 Heap hp;
	 HeapInit(&hp);
	 HeapPush(&hp, 70);
	 HeapPush(&hp, 56);
	 HeapPush(&hp, 30);
	 HeapPush(&hp, 25);
	 HeapPush(&hp, 15);
	 HeapPush(&hp, 10);
	 HeapPush(&hp, 20);
	 HeapPush(&hp, 60);

	 HeapPop(&hp);
	 HeapPop(&hp);
	 HeapPop(&hp);

}
 void TestHeap3()
 {
	 Heap hp;
	 HeapInit(&hp);
	 HeapPush(&hp, 70);
	 HeapPush(&hp, 56);
	 HeapPush(&hp, 30);
	 HeapPush(&hp, 25);
	 HeapPush(&hp, 15);
	 HeapPush(&hp, 10);
	 HeapPush(&hp, 20);
	 HeapPush(&hp, 60);

int a =  HeapTop(&hp);
	int c =  HeapSize(&hp);
	 

  }
 void TestHeap4()
 {
	 Heap hp;
	 HeapInit(&hp); 
	 HeapEmpty(&hp);
  }

//int main()
//{
//	TestHeap1();
//	//TestHeap2();
//	/*TestHeap3();*/
//	//TestHeap4();
//	return 0;
//}

---

Heap.c

#include"Heap.h"
void HeapInit(Heap* php)
{
	assert(php);
    php->a = (HeapDataType*)malloc(sizeof(HeapDataType) *4);
	if (php->a == NULL)
	{
		printf("malloc fail");
		exit(-1);
	}
	php->capacity = 4;
	php->size = 0;
}
void Swap(HeapDataType* p1, HeapDataType* p2)
{
	HeapDataType  x = *p1;
	*p1 = *p2;
	*p2 = x;
}
void AdjustUp(HeapDataType* a, int child) //向上调整算法 ，child 是插入数据下标
{
	int  parent = (child-1)/2; //父子节点下标关系推论
	while (child >0 )
	{
		//大堆根
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			//向上调整
			child = parent;
			parent = (child - 1) / 2;//更新parent
		}
		//不满足大堆根条件
		else
		{
			break;
		}
	}
}


void HeapPush(Heap* php, HeapDataType x)
{
	assert(php);
	if (php->capacity == php->size)
	{
		//扩容
		HeapDataType*  tmp = (HeapDataType *)realloc(php->a, sizeof(HeapDataType) * php->capacity * 2);
		//扩容失败
		if (tmp == NULL)
		{
			printf("realloc fail");
			exit(-1);
		}

		//扩容成功
		php->a = tmp;
		php->capacity *= 2;

	}
	php->a[php->size] = x;
	php->size++;
	AdjustUp(php->a, php->size-1);  // php->size-1 是插入数据的下标
}




void AdjustDown(HeapDataType* a, int n, int parent) // parent 是下标 , n 是数组元素个数
{
	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; 
		}
		
	}


}
void HeapPop(Heap* php) // 删除 
{
	assert(php);
	assert(!HeapEmpty(php));
	// 堆顶和数组最后一个元素交换
	Swap(&php->a[0], &php->a[php->size - 1]);
	php->size--; //删除
	//向下调整算法
	AdjustDown(php->a, php->size , 0);

}

HeapDataType  HeapTop(Heap* php) // 拿到堆顶的数据
{

	assert(php);
	return php->a[0];
}
int HeapSize(Heap* php)// 获取堆的数据个数
{
	assert(php);
	return php->size;
}
bool HeapEmpty(Heap* php)  // 堆是否为空
{
	assert(php);
	
	/*return php->size == 0; */
	if (php->size == 0)
	{
		return true;
	}
	else
	{
		return false;
	}
}

---

Heap.h

#include<stdio.h>
#include<stdbool.h>
#include<stdlib.h>
#include<assert.h>	
typedef int HeapDataType;
typedef struct Heap
{
	HeapDataType * a;
	int capacity;//存储容量 
	int size; //  实际大小
} Heap;

void HeapInit(Heap * php);

void Swap(HeapDataType* p1, HeapDataType* p2);

void AdjustUp(HeapDataType* a, int child); //向上调整算法

void HeapPush(Heap* php, HeapDataType x);

void AdjustDown(HeapDataType* a, int child, int n); 

void HeapPop(Heap* php); // 删除 

HeapDataType  HeapTop(Heap* php);  // 拿到堆顶的数据

int HeapSize(Heap* php); // 获取堆的数据个数

bool HeapEmpty(Heap* php);  // 堆是否为空

堆排序

排降序 建立小堆
排升序 建立大堆

升序

向上调整建堆,时间复杂度为O(N* longN)

使用向上调整算法建大堆，将数组建成大堆后,此时堆顶元素是最大的 ，将堆顶元素和最后一个元素进行交换,这样最大的元素就到了数组最后一个元素,对剩下的元素使用向下调整 ， 当下一次向下调整时，我们不管这个处在数组最后一个位置的最大元素（有点类似堆的删除 ），此时第二大的元素来到的堆顶 ，堆顶元素继续与最后一个元素进行交换，（注意第一个交换过去的最大的元素已经不在范围内了） ，依次类推 ，升序就完成了

 void HeapSort(int* a, int n)
 {
	 //向上调整建堆
	 for (int i = 0; i < n; i++)
	 {
		 AdjustUp(a, i);
	}
	 //向下调整排序
	 int end = n - 1;// end 是最后一个元素的下标
	 while (end > 0)
	 {
		 Swap(&a[0], &a[end]);
		 AdjustDown(a, end, 0);
		 end--;
	 }
 }
 int main()
 {
	 int a[10] = { 2, 1, 5, 7, 6, 8, 0, 9, 4, 3 };
	 HeapSort(a, 10);
	 return 0; 
 }

---

向下调整建堆的前提是左右子树都是堆 ，从倒数第一个非叶子节点开始倒着调整,如何找到倒数第一个非叶子节点？通过最后一个节点的父节点来找到 , 那为什么要找倒数第一个非叶子节点？ 因为倒数第一个非叶子节点的左右子树都满足大堆或小堆的条件

 void HeapSort(int* a, int n)
 {
	 //向下调整建堆
	 for (int i = (n-1-1)/ 2; i >= 0; i--) // n-1是最后一个节点的下标，（n-1-1)/2 通过下标找到最后一个节点的父节点
	 {
		 AdjustDown(a,n , i);
	 }
	 //向下调整排序
	 int end = n - 1; //end 是最后一个元素的下标 
	 while (end >=0)
	 {
		 Swap(&a[0], &a[end]);
		 AdjustDown(a, end, 0);
		 end--;
	 }

 }
 int main()
 {
	 int a[10] = { 2, 1, 5, 7, 6, 8, 0, 9, 4, 3 };
	 HeapSort(a, 10);
	 return 0; 
 }

建堆时间复杂度

向上调整建堆——O(N*logN)

向下调整建堆—— O(N)

TOP-K问题

即求数据结合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大

找N个数中最大的前k个一般建立N个的大堆 ,再Pop K 次就完成了，这种思路适合数据量比较小

如果数据量比较大
前K个数据建一个小堆
遍历剩下的元素，如果这个数据比堆顶的数据大，就将这个数据代替堆顶数据进堆（ 向下调整）
最后小堆的数据就是最大的前K个

用数据集合中前K个元素来建堆

• 前k个最大的元素，则建小堆
• 前k个最小的元素，则建大堆

如果你觉得这篇文章对你有帮助，不妨动动手指给点赞收藏加转发，给鄃鳕一个大大的关注
你们的每一次支持都将转化为我前进的动力！！！