数据结构—— 再探二叉树

1. TOP-K问题

TOP-K问题：求数据结合中前K个最大或者最小的数据

比如：专业前10名、世界500强、富豪榜、游戏中前100的活跃玩家等

思路：

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

                                          一般推荐建小堆   

2. 用剩余的数据依次与堆顶的数据来比较，如果比堆顶的数据大就替换堆顶数据（覆盖位置，向下调整）

将剩余的数据依次与堆顶元素比完之后，堆中剩余的数据就是所求的前K个最小或最大的元素

通俗来讲就是：用前K个数建立一个小堆，然后剩下的数依次遍历和堆顶最小的数据比较，如果比堆顶的数据大,就把大的数赋给堆顶，再向下调整，最后堆里剩下的K个数就是最大的K个 ，因为小堆的堆顶一定是最小的数，只要随便拿个数比他大就交换他俩，大的那个数进入堆后再建小堆，大的数就沉在最下面，所以最后堆里面一定是K个最大的数

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
 
void Swap(HPDataType* p1, HPDataType* p2)
{
	HPDataType tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
 
void AdjustDown(HPDataType* a, int size, int parent)
{
	int child = parent * 2 + 1;
	while (child < size) {
		if (child + 1 < size && 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 CreateNData()
{
	int n = 100000;
	srand(time(0));
	const char* file = "data.txt";
	FILE* fin = fopen(file, "w");
	if (fin == NULL)
	{
		perror("fopen error");
		return;
	}
	for (size_t i = 0; i < n; i++) {
		int x = rand() % 10000000;
		fprintf(fin, "%d\n", x);
	}
	fclose(fin);
}
 
void PrintTopK(int k)
{
	const char* file = "data.txt";
	FILE* fout = fopen(file, "r");
	if (fout == NULL)
	{
		perror("fopen error");
		return;
	}
	int* kminheap = (int*)malloc(sizeof(int) * k);
	if (kminheap == NULL)
	{
		perror("malloc error");
		return;
	}
 
	for (int i = 0; i < k; i++)
	{
		fscanf(fout, "%d", &kminheap[i]);
	}
	// 建小堆
	for (int i = (k - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(kminheap, k, i);
	}
 
	int val = 0;
	while (!feof(fout))
	{
		fscanf(fout, "%d", &val);
		if (val > kminheap[0])
		{
			kminheap[0] = val;
			AdjustDown(kminheap, k, 0);
		}
	}
 
	for (int i = 0; i < k; i++)
	{
		printf("%d ", kminheap[i]);
	}
	printf("\n");
	fclose(fout);
}
 
int main()
{
	CreateNData();
	PrintTopK(5);
	return 0;
}

---

2. 二叉树（BinaryTree）

2.1 介绍

前面我们的完全二叉树和满二叉树是使用数组来存储，如果不是完全二叉树和满二叉树就不适合使用数组存储，更适合链式结构来存储

二叉树是：

                1. 空树

                2. 非空：根结点，根结点的左子树、根结点的右子树组成的

                3.二叉树是递归结构

二叉树是整棵树拆分为根和子树，然后拆分过的子树再作为根继续拆分 ，一直这样持续至最后一个没有子树的根

---

在遍历之前先手搓一个二叉树的基础模板（Creat Binary Tree）：

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
#include<stdbool.h>
 
 
typedef int BTDataType;
typedef struct BinaryTreeNode
{
	BTDataType val;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
}BTNode;
 
BTNode* BuyNode(int x)
{
	BTNode* node = (BTNode*)malloc(sizeof(BTNode));
	if (node == NULL)
	{
		perror("malloc fail");
		return NULL;
	}
 
	node->val = x;
	node->left = NULL;
	node->right = NULL;
 
	return node;
}
 
BTNode* CreatBinaryTree()
{
	BTNode* node1 = BuyNode(1);
	BTNode* node2 = BuyNode(2);
	BTNode* node3 = BuyNode(3);
	BTNode* node4 = BuyNode(4);
	BTNode* node5 = BuyNode(5);
	BTNode* node6 = BuyNode(6);
 
	//node1的左和右指向node2和node4
	node1->left = node2;
	node1->right = node4;
 
	//node1的左指向node3
	node2->left = node3;
 
	//node4的左和右指向node5和node6
	node4->left = node5;
	node4->right = node6;
 
	return node1;
}
 
 
 
int main()
{
	//root:根   CreatBinaryTree：创建二叉树
	BTNode* root = CreatBinaryTree();
 
	return 0;
}

---

2.2 二叉树的遍历

前序遍历 （Prer Order）   

访问顺序：（根  左子树 右子树  )任何一棵树的访问，都要符合前序，被拆成根   左子树  右子树

访问顺序为：

 

//前序
void PrerOrder(BTNode* root)
{
	//如果根为空
	if (root == NULL)
	{
		printf("N ");
		return;
	}
	else
	{
        //打印根的数
		printf("%d\n", root->val);
        //打印完之后访问根的左子树和右子树
		PrerOrder(root->left);
		PrerOrder(root->right);
	}
}

                        代码执行完成之后就进行递归调用，一直到遇到空根结束

int main()
{
	//root:根   CreatBinaryTree：创建二叉树
	BTNode* root = CreatBinaryTree();
	PrerOrder(root);
	printf("\n");
	return 0;
}

---

中序遍历（In Order）

访问顺序：（左子树   根  右子树 ）任何一棵树的访问，都要符合中序，被拆成左子树   根  右子树

访问顺序为：

 
//中序
void InOrder(BTNode* root)
{
	//如果根为空
	if (root == NULL)
	{
		printf("N ");
		return;
	}
	else
	{
		//先访问左子树
		InOrder(root->left);
		//打印根的数
		printf("%d\n", root->val);
		//打印完之后访问根的右子树
		InOrder(root->right);
	}
}

int main()
{
	//root:根   CreatBinaryTree：创建二叉树
	BTNode* root = CreatBinaryTree();
	
	//中序
	//InOrder(root);
 
	printf("\n");
	return 0;
}

---

后序遍历（Post Order）

访问顺序：（左子树  右子树   根）任何一棵树的访问，都要符合后序，被拆成左子树  右子树   根

访问顺序为： 

//后序
void PostOrder(BTNode* root)
{
	//如果根为空
	if (root == NULL)
	{
		printf("N ");
		return;
	}
	else
	{
		//先访问左子树和右子树
		PostOrder(root->left);			
		PostOrder(root->right);
		//再打印根的数
		printf("%d\n", root->val);
	}
}

int main()
{
	//root:根   CreatBinaryTree：创建二叉树
	BTNode* root = CreatBinaryTree();
	//前序
	//PrerOrder(root);
	//中序
	//InOrder(root);
	//后序
	PostOrder(root);
	printf("\n");
	return 0;
}

---

求二叉树节点的个数 （Tree Size）：

节点个数：

                1.如果为空，则为0

                2.如果不为空，则是左子树 + 右子树 + 1

//求整棵树节点的个数
int TreeSize(BTNode* root)
{
	//如果为空则返回0，不为空则返回左子树加右子树加1
	return root == NULL ? 0 :TreeSize(root->left) + TreeSize(root->right) + 1;
}

int main()
{
	//root:根   CreatBinaryTree：创建二叉树
	BTNode* root = CreatBinaryTree();
	//前序
	//PrerOrder(root);
	//中序
	//InOrder(root);
	//后序
	//PostOrder(root);
	//printf("\n");
    
    //求整棵树节点的个数
	printf("TreeSize:%d\n", TreeSize(root));
	
	return 0;
}

---

获取叶子节点个数（Tree Leaf Size）：

叶子：就是度为0，不包括任何子节点，通俗来讲就是没有孩子的节点

//获取叶子节点个数
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);
}

int main()
{
	//root:根   CreatBinaryTree：创建二叉树
	BTNode* root = CreatBinaryTree();
	//前序
	//PrerOrder(root);
	//中序
	//InOrder(root);
	//后序
	//PostOrder(root);
	//printf("\n");
    //求整棵树节点的个数
	//printf("TreeSize:%d\n", TreeSize(root));
 
    //获取叶子节点个数
	printf("TreeLeafSize:%d\n", TreeLeafSize(root));
	
	return 0;
}

---

二叉树的高度 （Tree Height）：

                        二叉树的高度是有几层高度就是几

//二叉树的高度
int TreeHeight(BTNode* root)
{
	if (root == NULL)
		return 0;
	//使用两个变量记录下来，避免重复计算
	int leftHeight = TreeHeight(root->left);
	int rightHeight = TreeHeight(root->right);
 
	return leftHeight > rightHeight ?
		leftHeight + 1 : rightHeight + 1;
}

int main()
{
	//root:根   CreatBinaryTree：创建二叉树
	BTNode* root = CreatBinaryTree();
	//前序
	//PrerOrder(root);
	//中序
	//InOrder(root);
	//后序
	//PostOrder(root);
	//printf("\n");
	 //求整棵树节点的个数
	//printf("TreeSize:%d\n", TreeSize(root));
 
    //获取叶子节点个数
	//printf("TreeLeafSize:%d\n", TreeLeafSize(root));
 
    //二叉树的高度
	printf("TreeHeight:%d\n", TreeHeight(root));
 
	return 0;
}

---

 二叉树第k层结点个数：

// 二叉树第k层节点个数
int TreeLevelKSize(BTNode* root, int k)
{
	if (root == NULL)
		return 0;
 
	if (k == 1)
		return 1;
 
	// 子问题
	return TreeLevelKSize(root->left, k - 1)
		+ TreeLevelKSize(root->right, k - 1);
}

---

二叉树查找值为x的结点：

// 二叉树查找值为x的节点
BTNode* TreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
		return NULL;
 
	if (root->val == x)
		return root;
 
	BTNode* ret1 = TreeFind(root->left, x);
    //如果找到了直接返回数值，没有找到直接返回空
	if (ret1)
		return ret1;
 
	BTNode* ret2 = TreeFind(root->right, x);
    //如果找到了直接返回数值，没有找到直接返回空
	if (ret2)
		return ret2;
 
	return NULL;
}

---

                                                            休息一下，马上回来~