C语言实现二叉树_c语言 二叉树

1.树的概念及结构

1.1树的概念

•因此，树是递归定义的。

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

1.2树的相关概念 

1.3树的表示

typedef int DataType;
struct Node
{
 struct Node* _firstChild1; // 第一个孩子结点
 struct Node* _pNextBrother; // 指向其下一个兄弟结点
 DataType _data; // 结点中的数据域
};

2. 二叉树的概念及结构

2.1概念

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

1. 或者为空

注意：对于任意的二叉树都是由以下几种情况复合而成的：

 2.2特殊的二叉树

 2.3二叉树的性质

2.4二叉树的存储结构

二叉树一般可以使用两种结构存储，一种顺序结构，一种链式结构。

2.4.1 顺序存储

顺序结构存储就是使用 数组来存储 ，一般使用数组 只适合表示完全二叉树 ，因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储，二叉树顺 序存储在物理上是一个数组，在逻辑上是一颗二叉树。

2.4.2 链式存储

3.二叉树的顺序结构及实现

3.1 二叉树的顺序结构

3.3堆的实现

 3.3.1函数申明

typedef int MyDataType;
typedef struct Heap
{
	MyDataType* a;
	int capacity;
	int size;
}HP;
 
void AdjustUp(MyDataType* a,int child);//向上调整
void AdjustDown(MyDataType* a, int n, int parent);//向下调整
void Swap(MyDataType* x, MyDataType* y);//交换两个数的值
void HeapPrint(HP* php);//打印堆
void InitHeap(HP*php);//堆的初始化
void DestroyHeap(HP*php);//堆的销毁
void PushHeap(HP*php ,MyDataType x);//向堆中增加数据
void PopHeap(HP*php);//从堆中删除数据
MyDataType HeapTop(HP*php);//堆顶元素
bool HeapEmpty(HP*php);//堆是否为空

3.3.2函数实现

void Swap(MyDataType*x,MyDataType*y)//交换两个数的值
{
	MyDataType temp = 0;
	temp = *x;
	*y = *x;
	*y = temp;
}
void InitHeap(HP* php)//初始化
{
	assert(php);
	php->a = NULL;
	php->capacity = 0;
	php->size = 0;
}
 
void DestroyHeap(HP* php)//销毁堆
{
	assert(php);
	free(php->a);
	php->a = NULL;
	free(php);
}
void HeapPrint(HP* php)//打印堆
{
	assert(php);
	for (int i = 0; i < (php->size - 1); i++)
	{
		printf("%d ", php->a[i]);
	}
	printf("\n");
}
void AdjustUp(MyDataType* 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;
		}
		else
		{
			break;
		}
	}
}
void AdjustDown(MyDataType* a, int n, int parent)//向下调整
{
	int child = parent * 2 + 1;
	while (parent < n)
	{
		if (child + 1 < n&&a[child+1]<a[child])
		{
			child +=1;
		}
		if (a[child] < a[parent])
		{
			Swap(&a[child],& a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
void PushHeap(HP*php,MyDataType x)
{
	assert(php);
	if (php->capacity == php->size)
	{
		int Newsize = php->capacity == 0 ? 4:php->capacity * 2;
		MyDataType* tmp = (MyDataType*)realloc(php->a, Newsize);
		if (tmp == NULL)
		{
			perror("perror fail");
			exit(-1);
		}
		php->a = tmp;
	}
	php->a[php->size] = x;
	php->size++;
 
	AdjustUp(php->a, php->size - 1);
	
}
void PopHeap(HP* php)
{
	assert(php);
	assert(!HeapEmpty(php));
	Swap(&php->a[0], &php->a[php->size - 1]);
	php->size--;
	AdjustDown(php->a, php->size, 0);
}
MyDataType HeapTop(HP*php)
{
	assert(php);
	assert(!HeapEmpty(php));
	return php->a[0];
}
bool HeapEmpty(HP*php)
{
	if (php->a == NULL)
		return true;
	else
		return false;
}

3.4堆的应用

3.4.1堆排序

 代码实现：

void HeapSort(MyDataType* a,int n)
{
	for (int i = (n - 1 - 1) / 2; i > 0; i--)
		AdjustDown(a, n, i);
	int end = n - 1;
	while (end > 0)
	{
		Swap(&a[0], &a[end]);
		end--;
		AdjustDown(a, end, 0);
	}
}

3.4.2TopK问题

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");
}

typedef struct BinaryTreeNode
{
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
	BTDataType val;
}BTNode;
typedef int BTDataType;
BTNode* BuyNode(BTDataType x)
{
	BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		return NULL;
	}
	newnode->val = x;
	newnode->left = NULL;
	newnode->right = NULL;
	return newnode;
}
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);
	BTNode* node7 = BuyNode(7);
 
 
	node1->left = node2;
	node1->right = node4;
	node2->left = node3;
	node4->left = node5;
	node4->right = node6;
	//node5->left = node7;
	node2->right = node7;
 
	return node1;
}

void PrevOrder(BTNode* root)//前叙
{
	if (root == NULL)
	{
		return;
	}
	printf("%d ", root->val);
	PrevOrder(root->left);
	PrevOrder(root->right);
}
 
void InOrder(BTNode* root)//中序
{
	if (root == NULL)
	{
		return;
	}
	InOrder(root->left);
	printf("%d ", root->val);
	InOrder(root->right);
}
 
void PostOrder(BTNode* root)//后序
{
	if (root == NULL)
	{
		return;
	}
	PostOrder(root->left);
	PostOrder(root->right);
	printf("%d ", root->val);
}

前序、后序、中序代码实现都利用到了递归的思想。而层序则需要利用到队列这一数据结构。

typedef BTNode* MyDataType;
typedef struct QueueNode
{
	MyDataType val;
	struct QueueNode* next;
}QNode;
 
typedef struct Queue
{
	QNode* front;
	QNode* back;
	int size;
}QL;
 
void LevelOrder(BTNode* root)//层序
{
	QL ql;
	QueueInit(&ql);//创建一个队列
	if (root != NULL)
		QueuePush(&ql, root);//只要非空就进入队列
	while (!QueueEmpty(&ql))
	{
		BTNode* front = QueueFront(&ql);
		printf("%d ", front->val);
		QueuePop(&ql);
		if (front->left)
			QueuePush(&ql, front->left);
		if (front->right)
			QueuePush(&ql, front->right);
	}//出队列的同时将根的左子树和右子树带入队列
	printf("\n");
	QueueDestroy(&ql);//销毁队列
}

 其余一些常见功能：

//二叉树结点个数
int BTreeSize(BTNode* root)
{
	if (root == NULL)
		return 0;
	return BTreeSize(root->left) +
		BTreeSize(root->right) + 1;
}
 
//求叶子结点个数
int BTreeLeafSize(BTNode* root)
{
	if (root == NULL)
		return 0;
	if (root->left == NULL && root->right == NULL)
		return 1;
	return BTreeLeafSize(root->left) + BTreeLeafSize(root->right);
}
 
//求二叉树高度
int BTreeHeight(BTNode* root)
{
	if (root == NULL)
		return 0;
	int LeftHeight = BTreeHeight(root->left);
	int RightHeight = BTreeHeight(root->right);
	return LeftHeight > RightHeight ? LeftHeight+1 : RightHeight+1;
}
 
// 二叉树第k层结点个数
int BTreeLevelKSize(BTNode* root, int k)
{
	if (root == NULL)
		return 0;
	if (k == 1)
		return 1;
	return BTreeLevelKSize(root->left, k - 1) + BTreeLevelKSize(root->right, k - 1);
}
// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
		return NULL;
	if (root->val == x)
		return root;
	BTNode* LeftTreeFind = BinaryTreeFind(root->left, x);
	BTNode* RightTreeFind = BinaryTreeFind(root->right, x);
	return LeftTreeFind == NULL ? RightTreeFind : LeftTreeFind;
}
// 判断二叉树是否是完全二叉树
int BinaryTreeComplete(BTNode* root)
{
	QL ql;
	QueueInit(&ql);
	if (root)
		QueuePush(&ql, root);
	while (QueueFront(&ql) != NULL)
	{
		BTNode* front = QueueFront(&ql);
		QueuePop(&ql);
		QueuePush(&ql, front->left);
		QueuePush(&ql, front->right);
	}
	while (!QueueEmpty(&ql))
	{
		BTNode* front = QueueFront(&ql);
		if (front != NULL)
			return 0;
		QueuePop(&ql);
	}
	return 1;
}

 测试函数功能：

int main()
{
	BTNode* root = CreatBinaryTree();
	PrevOrder(root);
	printf("\n");
	InOrder(root);
	printf("\n");
	PostOrder(root);
	printf("\n");
	LevelOrder(root);
	printf("\n");
	printf("BTreeSize:%d\n", BTreeSize(root));
	printf("BTreeLeafSize:%d\n", BTreeLeafSize(root));
	printf("BTreeHeight:%d\n", BTreeHeight(root));
	printf("BTreeLevelK2Size:%d\n", BTreeLevelKSize(root, 2));
	printf("BTreeLevelK4Size:%d\n", BTreeLevelKSize(root, 4));
	printf("BinaryTreeComplete:%d\n", BinaryTreeComplete(root));
	return 0;
}

 结果如下：