数据结构-二叉树（2）

3.4堆的应用

3.4.1 堆排序

堆排序即利用堆的思想来进行排序，总共分为两个步骤：

1. 建堆

   1.升序：建大堆；

   2.降序：建小堆。

2. 利用堆删除思想来进行排序

这种写法有两个缺点：

 1、先有一个堆的数据结构
 2、空间复杂度复杂度的消耗

void HeapSort(int* a, int n)
{
	HP hp;
	HeapInit(&hp);
	for (int i = 0; i < n; i++)
	{
		HeapPush(&hp, a[i]);
	}
	
	int i = 0;
	while (!HeapEmpty(&hp))
	{
		//printf("%d ", HeapTop(&hp));
		a[i++] = HeapTop(&hp);
		HeapPop(&hp);
	}

	HeapDestroy(&hp);
}

所以我们可以稍微改进一下，使得只要有一个数组就可以进行堆排序：

假设要排一个升序：

先使用向下调整的方式建一个大堆，然后再写一个循环，当end=0时结束循环，每次进入循环先交换首尾数据，然后从头开始进行向下调整，每次end--。

void AdjustDown(int* a,int n, int parent)
{
	int child = parent * 2 + 1;
	while(child < n)
	{
		if (a[child] < a[child + 1] && child + 1 < n)
		{
			child += 1;
		}
		if (a[child] > a[parent])
		{
			Swap(&a[parent], &a[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
void HeapSort(int* a, int n)
{
	//向下调整建堆
	for (int i = (n-1-1)/2; i >= n; i--)
	{
		AdjustDown(a,n,i);
	}
	int end = n - 1;
	while (end > 0)
	{
		Swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);
		end--;
	}
}

3.4.2 TOP-K问题

TOP-K问题：即求数据结合中前K个最大的元素或者最小的元素，一般情况下数据量都比较大。
比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等。
对于Top-K问题，能想到的最简单直接的方式就是排序，但是：如果数据量非常大，排序就不太可取了(可能数据都不能一下子全部加载到内存中)。最佳的方式就是用堆来解决，基本思路如下：

1. 用数据集合中前K个元素来建堆
前k个最大的元素，则建小堆
前k个最小的元素，则建大堆

2. 用剩余的N-K个元素依次与堆顶元素来比较，不满足则替换堆顶元素
将剩余N-K个元素依次与堆顶元素比完之后，堆中剩余的K个元素就是所求的前K个最小或者最大的元素。

 void PrintTopK(const char* filename, int k)
 {
	 // 1. 建堆--用a中前k个元素建堆
	 FILE* fout = fopen(filename, "r");
	 if (fout == NULL)
	 {
		 perror("fopen fail");
		 return;
	 }

	 int* minheap = (int*)malloc(sizeof(int) * k);
	 if (minheap == NULL)
	 {
		 perror("malloc fail");
		 return;
	 }

	 for (int i = 0; i < k; i++)
	 {
		 fscanf(fout, "%d", &minheap[i]);
	 }

	 // 前k个数建小堆
	 for (int i = (k - 2) / 2; i >= 0; --i)
	 {
		 AdjustDown(minheap, k, i);
	 }


	 // 2. 将剩余n-k个元素依次与堆顶元素交换，不满则则替换
	 int x = 0;
	 while (fscanf(fout, "%d", &x) != EOF)
	 {
		 if (x > minheap[0])
		 {
			 // 替换你进堆
			 minheap[0] = x;
			 AdjustDown(minheap, k, 0);
		 }
	 }


	 for (int i = 0; i < k; i++)
	 {
		 printf("%d ", minheap[i]);
	 }
	 printf("\n");

	 free(minheap);
	 fclose(fout);
 }

4.二叉树链式结构的实现

4.1 前置说明

在学习二叉树的基本操作前，需先要创建一棵二叉树，然后才能学习其相关的基本操作。此处手动快速创建一棵简单的二叉树，快速进入二叉树操作学习，等二叉树结构了解的差不多时，我们反过头再来研究二叉树真正的创建方式。
首先我们手动创建一个链式二叉树，链接完后的二叉树大概是这个样子。

再看二叉树基本操作前，再回顾下二叉树的概念，二叉树是：
1. 空树
2. 非空：根节点，根节点的左子树、根节点的右子树组成的。

从概念中可以看出，二叉树定义是递归式的，因此后序基本操作中基本都是按照该概念实现的。
 

typedef struct BinaryTreeNode
{
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
	int val;
}BTNode;
int main()
{
	BTNode* node1 = BuyListNode(1);
	BTNode* node2 = BuyListNode(2);
	BTNode* node3 = BuyListNode(3);
	BTNode* node4 = BuyListNode(4);
	BTNode* node5 = BuyListNode(5);
	BTNode* node6 = BuyListNode(6);

	node1->left = node2;
	node1->right = node4;
	node2->left = node3;
	node4->left = node5;
	node4->right = node6;
}

4.2二叉树的遍历

4.2.1 前序、中序以及后序遍历

学习二叉树结构，最简单的方式就是遍历。所谓二叉树遍历(Traversal)是按照某种特定的规则，依次对二叉树中的节点进行相应的操作，并且每个节点只操作一次。访问结点所做的操作依赖于具体的应用问题。 遍历是二叉树上最重要的运算之一，也是二叉树上进行其它运算的基础。

 按照规则，二叉树的遍历有：前序/中序/后序的递归结构遍历：

1. 前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。
2. 中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中（间）。
3. 后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。
由于被访问的结点必是某子树的根，所以N(Node）、L(Left subtree）和R(Right subtree）又可解释为根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。

下面主要分析前序递归遍历，中序与后序图解类似：

前序,中序,后序遍历代码：

//前序 根 左子树 右子树
void PrevOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
			return;
	}
	printf("%d ", root->val);
	PrevOrder(root->left);
	PrevOrder(root->right);
}

//中序 左子树 根 右子树
void InOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	InOrder(root->left);
	printf("%d ", root->val);
	InOrder(root->right);
}

//右序 左子树 右子树 根
void PostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	PostOrder(root->left);
	PostOrder(root->right);
	printf("%d ", root->val);
}

前序遍历递归图解：

先访问根，在访问左子树，也就是先访问1，再访问1的左子树，1的左子树的根是2，所以再访问2，2的左子树还没有访问完，所以访问2的左子树的根3，再访问3的左子树NULL，到这里3的左子树访问完毕，开始访问3的右子树NULL，到这里3的右子树也访问完毕，开始访问2的右子树NULL......以此类推

 前序遍历递归展开图：

 中序和后序都是一样的过程，总之就是要把对应的左子树/右子树遍历到NULL才返回上一层。

4.3二叉树节点个数

这里也要把问题转化为递归的子问题，使用一个三目操作符，差不多是一个后序遍历，如果当前节点为NULL则返回0，不是NULL则返回他的左子树和右子树的节点个数加1，也就是自己这个节点。比方说要求以下二叉树的节点个数，后序就是从3的左子树NULL开始，节点3的左右子树都为空，则节点3返回0+0+1=1，再求节点2，节点2的左子树返回了1，右子树返回0，所以节点2返回1+0+1=2，以此类推1的右子树返回的是3，所以1这个根节点的返回值是2+3+1=6.

//节点个数
int TreeSize(BTNode* root)
{
	//后序
	return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}

4.4二叉树叶子节点个数

叶子节点就是没有左右子树的节点，所以进入函数先判断当前节点是否为NULL，如果是则返回0，再判断是否为叶子节点，左子树和右子树都为NULL才是叶子节点，返回1。如果两个if都未进入，说明当前节点至少有一个子节点，再写一个递归往下找，返回左右子树的全部叶子节点。

int TreeLeafSize(BTNode* root)
{
	//当前节点为空
	if (root == NULL)
		return 0;
	//左右子树为空，自己就是叶子
	if (root->left == NULL && root->right == NULL)
		return 1;
	//往下找
	return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}

4.5二叉树第k层节点个数

要求第k层的节点个数，首先我们要知道一个思路，假设要求这个二叉树第3层的节点个数，那么第3层就相当于根节点1的第3层，根节点1的第三层又相当于2和4的第二层，2和4的第二层又相当于3，5，6的第一层，所以当k=1且不为空时，返回1即可。递归左右子树，每次k-1.

int TreeKLevel(BTNode* root, int k)
{
	assert(k > 0);
	if (root == NULL)
	{
		return 0;
	}
	//走到最后一层
	if (k == 1)
	{
		return 1;
	}
	//每次往下找一层
	return TreeKLevel(root->left, k - 1) + TreeKLevel(root->right, k - 1);
}

4.6二叉树查找值为x的节点

查找节点的话，首先判断当前节点是否满足val=x，如果满足直接返回当前节点，再判断是否为空，如果既不为空也不是要查找的节点则开始往左子树开始找，这个时候要创建一个变量tail来保存返回值，使用if判断返回值是什么情况，如果是空则开始往右子树找，如果不为空则说明找到了，直接返回tail。右子树也是一样的步骤，如果左右子树都没找到说明找不到了，返回NULL。

BTNode* TreeFind(BTNode* root,int x)
{
	if (root->val == x)
		return root;
	if (root == NULL)
		return NULL;
	BTNode* tail = NULL;
	tail = TreeFind(root->left,x);
	if (tail)
		return  tail;
	tail = TreeFind(root->right,x);
	if (tail)
		return tail;
	return NULL;
}

今天的分享到这里就结束啦！感谢大家的阅读！！！