目录

1. Top-K问题

2. 链式二叉树

题目要求：要求在N个数中，N的数据量很大，找出大小为前K大的数

思路（用时间换空间）：

建立一个K个数组成的小根堆，后面N-K个数比较堆顶数据，如果比堆顶数据大就替换掉堆顶

#include 
#include 
#include 
#include 
#include 
#include 

typedef int HPDataType;

void Swap(HPDataType* pdata, int child, int parent)
{
	HPDataType tmp = pdata[child];
	pdata[child] = pdata[parent];
	pdata[parent] = tmp;
}

void AdjustDown(HPDataType* pdata, int size, int parent)    //向下调整建小根堆
{
	int child = parent * 2 + 1;
	while (child < size)
	{
		if (child + 1 < size && pdata[child + 1] < pdata[child])
		{
			child++;
		}
		if (pdata[child] < pdata[parent])
		{
			Swap(pdata, child, parent);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

void TestTopK(int* a, int n, int k)
{
	int* KMinHeap = (int*)malloc(sizeof(int) * k);
	int i = 0;
	for (i = 0; i < k; i++)
	{
		KMinHeap[i] = a[i];
	}
	for (i = (k - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(KMinHeap, k, i);
	}
	for (i = k; i < n; i++)
	{
		if (a[i] > KMinHeap[0])
		{
			KMinHeap[0] = a[i];
			AdjustDown(KMinHeap, k, 0);
		}
	}
	for (i = 0; i < k; i++)
	{
		printf("%d ",KMinHeap[i]);
	}
	free(KMinHeap);
	KMinHeap = NULL;
}

int main()
{
	int a[10000] = { 0 };
	srand(time(0));
	int i = 0;
	for (i = 0; i < 10000; i++)
	{
		a[i] = rand() % 100000;
	}
	a[213] = 1000000 + 1;
	a[32] = 1000000 + 2;
	a[3435] = 1000000 + 3;
	a[1242] = 1000000 + 4;
	a[2323] = 1000000 + 5;
	a[336] = 1000000 + 6;
	a[4664] = 1000000 + 7;
	a[5657] = 1000000 + 8;
	a[453] = 1000000 + 9;
	a[4531] = 1000000 + 10;    //只有这10个数超过1000000

	TestTopK(a, 10000, 10);
	return 0;
}

2. 链式二叉树

遍历二叉树（分治算法）：

• 前序遍历：根      左子树      右子树
• 中序遍历：左子树      根      右子树
• 后序遍历：左子树      右子树      根

程序中创建的测试二叉树如图：

实现的功能：

• 二叉树的前序创建与后序销毁；
• 二叉树的前序、中序、后序遍历；
• 二叉树的节点、叶节点、所包含树的统计；
• 二叉树的x值查找、第K层节点数统计；
• 补充：二叉树的层序遍历要利用队列的性质；

源代码：

#include 
#include 

typedef char BTData;

typedef struct BinaryTreeNode
{
	BTData data;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
}BTNode;

BTNode* BuyBTNode(BTData x)
{
	BTNode* new = (BTNode*)malloc(sizeof(BTNode));
	new->data = x;
	new->left = new->right = NULL;
	return new;
}

BTNode* BinaryTreePreCreat(BTData* a, int* pi)	//前序法输入字符串构造二叉树
{
	if (a[*pi] == '#')
	{
		(*pi)++;
		return NULL;
	}
	BTNode* root = BuyBTNode(a[(*pi)++]);
	root->left = BinaryTreePreCreat(a, pi);
	root->right = BinaryTreePreCreat(a, pi);
	return root;
}

void BinaryTreeDestory(BTNode* root)
{
	if (root == NULL)
		return;
	BinaryTreeDestory(root->left);
	BinaryTreeDestory(root->right);
	printf("%c ", root->data);
	free(root);
}

void PreOrder(BTNode* root)		//前序遍历：每棵子树都遵循“根 左 右”原则
{
	if (root == NULL)
	{
		printf("# ");
		return;
	}
	printf("%c ", root->data);
	PreOrder(root->left);
	PreOrder(root->right);
}

void InOrder(BTNode* root)		//中序遍历：每颗子树都遵循“左 根 右”原则
{
	if (root == NULL)
	{
		printf("# ");
		return;
	}
	InOrder(root->left);
	printf("%c ", root->data);
	InOrder(root->right);
}

void PastOrder(BTNode* root)	//后序遍历：每颗子树都遵循“左 右 根”原则
{
	if (root == NULL)
	{
		printf("# ");
		return;
	}
	PastOrder(root->left);
	PastOrder(root->right);
	printf("%c ", root->data);
}

int BinaryTreeSize(BTNode* root)	//二叉树节点个数
{
	return root == NULL ? 0 :
		BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;
}

int BinaryTreeLeafSize(BTNode* root)	//二叉树叶节点个数
{
	if (root == NULL)
		return 0;
	if (root->left == NULL && root->right == NULL)
		return 1;
	return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}

int BinaryTreeLevelKSize(BTNode* root, int k)	//默认根节点层数为1，则求第K层节点个数
{
	assert(k >= 1);
	if (k == 1)
	{
		if (root)
			return 1;
		else
			return 0;
	}
	return BinaryTreeLevelKSize(root->left, k - 1) +
		BinaryTreeLevelKSize(root->right, k - 1);
}

BTNode* BinaryTreeFind(BTNode* root, BTData x)		//查找值为x的节点
{
	if (root == NULL)
		return NULL;
	if (root->data == x)
		return root;
	BTNode* ret = BinaryTreeFind(root->left, x);
	if (ret)
		return ret;
	return BinaryTreeFind(root->right, x);
}

int BinaryTreeDepth(BTNode* root)		//二叉树深度
{
	if (root == NULL)
		return 0;
	int left_depth = BinaryTreeDepth(root->left);
	int right_depth = BinaryTreeDepth(root->right);
	return left_depth > right_depth ? left_depth + 1 : right_depth + 1;
}

int TreeSize(BTNode* root)		//二叉树中所包含的所有树的个数
{
	if (root == NULL)
		return 0;
	return (root->left == NULL && root->right == NULL) ? 0 :
		(TreeSize(root->left) + TreeSize(root->right) + 1);
}

int main()
{
	int i = 0;
	BTNode* root = BinaryTreePreCreat("123###45##6##", &i);		//用前序遍历进行构建二叉树

	printf("PreOrder:  ");
	PreOrder(root);			// 1 2 3 # # # 4 5 # # 6 # #
	printf("n");
	printf("InOrder:   ");
	InOrder(root);			// # 3 # 2 # 1 # 5 # 4 # 6 #
	printf("n");
	printf("PastOrder: ");
	PastOrder(root);		// # # 3 # 2 # # 5 # # 6 4 1
	printf("n");

	printf("BinaryTreeSize: %d n", BinaryTreeSize(root));
	printf("BinaryTreeLeafSize: %dn", BinaryTreeLeafSize(root));
	printf("BinaryTreeLevelKSize: %dn", BinaryTreeLevelKSize(root, 1));
	BTNode* tmp = BinaryTreeFind(root, 5);
	if (tmp)
		printf("BinaryTreeFind: tmp->data == %dn", tmp->data);
	else
		printf("BinaryTreeFind: tmp->data == NULL");
	printf("BinaryTreeDepth: %dn", BinaryTreeDepth(root));
	printf("TreeSize: %dn", TreeSize(root));

	printf("BinaryTreeDestory: ");
	BinaryTreeDestory(root);
	root = NULL;
	return 0;
}

暑期编程PK赛 得CSDN机械键盘等精美礼品！