二叉树——链式结构的实现

首先是分为三个文件进行实现：tree.h、tree.c、test.c

• tree.h

用链表来表示⼀棵⼆叉树，即用链来指示元素的逻辑关系。通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩⼦和右孩⼦所在的链结点的存储地址。

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>

typedef int BTDataType;

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

//前序遍历
void PreOrder(BTNode* root);
//中序遍历
void InOrder(BTNode* root);
//后序遍历 
void PostOrder(BTNode* root);

// ⼆叉树结点个数
int BinaryTreeSize(BTNode* root);

// ⼆叉树叶⼦结点个数
int BinaryTreeLeafSize(BTNode* root);

// ⼆叉树第k层结点个数
int BinaryTreeLevelKSize(BTNode* root, int k);

//⼆叉树的深度/⾼度
int BinaryTreeDepth(BTNode* root);

// ⼆叉树查找值为x的结点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);

// ⼆叉树销毁
void BinaryTreeDestory(BTNode** root);

//层序遍历
void LevelOrder(BTNode* root);

//判断二叉树是否为完全二叉树
bool BinaryTreeComplete(BTNode* root);

• tree.c

前序遍历

访问顺序为：根结点、左子树、右子树
思路：

1. 若根结点为空，则表示该树为空，直接返回
2. 若不为空则打印根结点
3. 递归根结点的左孩子结点
4. 递归根结点的右孩子结点

#include"tree.h"

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

中序遍历

访问顺序为：左子树、根结点、右子树

思路：

1. 若根结点为空，则表示该树为空，直接返回
2. 若不为空则递归根结点的左孩子结点
3. 打印根结点
4. 递归根结点的右孩子结点

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

后序遍历

访问顺序为：左子树、右子树、根结点

思路：

1. 若根结点为空，则表示该树为空，直接返回
2. 若不为空则递归根结点的左孩子结点
3. 递归根结点的右孩子结点
4. 打印根结点

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

⼆叉树结点个数

思路：

1. 若根结点为空，则表示该树为空，直接返回
2. 若不为空，则返回1+递归根结点的左子树+递归根结点的右子树

int BinaryTreeSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}

⼆叉树叶子结点个数

思路：

1. 若根结点为空，则表示该树为空，直接返回
2. 若该结点的左右孩子都为空，则该结点为叶子结点
3. 返回递归左子树+递归右子树

int BinaryTreeLeafSize(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}
	if (root->left == NULL && root->right == NULL)
	{
		return 1;
	}
	return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}

⼆叉树第k层结点个数

思路：

1. 若根结点为空，则表示该树为空，直接返回0
2. 当k为1时，则表示该结点为第k层，返回1
3. 递归左子树，并将k-1
4. 递归右子树，将k-1
5. 将两个数相加

int BinaryTreeLevelKSize(BTNode* root, int k)
{
	if (root == NULL)
	{
		return 0;
	}
	if (k == 1)
	{
		return 1;
	}
	return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
}

⼆叉树的深度/高度

思路：

1. 若根结点为空，则表示该树为空，直接返回0
2. 递归左右子树，计算深度
3. 比较左右子树的深度大小，将大的深度+1（根结点）

int BinaryTreeDepth(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	int leftDep = BinaryTreeDepth(root->left);
	int rightDep = BinaryTreeDepth(root->right);
	return leftDep > rightDep ? leftDep + 1 : rightDep + 1;
}

⼆叉树查找值为x的结点

思路：

1. 若根结点为空，则表示该树为空，直接返回NULL
2. 若根结点的值与待查找值相同，则返回根结点
3. 不相同则递归根结点的左子树，观察是否相同
4. 递归根结点的右子树，观察是否相同

BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
	{
		return NULL;
	}
	if (root->data == x)
	{
		return root;
	}
	BTNode* leftfind=BinaryTreeFind(root->left, x);
	if (leftfind)
		return leftfind;
	BTNode* rightfind = BinaryTreeFind(root->right, x);
	if (rightfind)
		return rightfind;
	return NULL;
}

⼆叉树销毁

思路：

1. 若根结点为空，则表示该树为空，直接返回
2. 递归销毁根结点的左子树
3. 递归销毁根结点的右子树

void BinaryTreeDestory(BTNode** root)
{
	if (*root == NULL)
	{
		return;
	}
	BinaryTreeDestory(&((*root)->left));
	BinaryTreeDestory(&((*root)->right));
	free(*root);
	*root = NULL;
}

层序遍历

思路：

1. 需要借助队列来实现，因此第一步引用队列的操作
2. 初始化队列，并将根结点插入队列
3. 将根结点出队，并将根结点的左右子树入队，接着循环，直到队列为空
4. 销毁队列

#include"queue.h"
void LevelOrder(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q,root);
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		printf("%d ", front->data);
		QueuePop(&q);
		if (front->left)
			QueuePush(&q, front->left);
		if (front->right)
			QueuePush(&q, front->right);
	}
	QueueDestroy(&q);
}

判断二叉树是否为完全二叉树

思路：

1. 也需要引入队列
2. 初始化队列，并将根结点插入队列
3. 将队列队头出队，当队头为空时退出循环，否则将队头的左右孩子入队
4. 当队头为空时，判断队列是否为空，为空则说明是完全二叉树，否则，不为完全二叉树

bool BinaryTreeComplete(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q,root);
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		if (front == NULL)
		{
			break;
		}
		QueuePush(&q, root->left);
		QueuePush(&q,root->right);
	}
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		if (front != NULL)
		{
			QueueDestroy(&q);
			return false;
		}
	}
	QueueDestroy(&q);
	return true;
}

• test.c

手动创建一棵树：

#include"tree.h"

BTNode* buyNode(BTDataType x)
{
	BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
	if (newnode == NULL)
	{
		perror("malloc fail!");
		exit(1);
	}
	newnode->data = x;
	newnode->left = newnode->right = NULL;
	return newnode;
}

void Test()
{
	BTNode* node1 = buyNode(1);
	BTNode* node2 = buyNode(2);
	BTNode* node3 = buyNode(3);
	BTNode* node4 = buyNode(4);
	node1->left = node2;
	node1->right = node3;
	node2->left = node4;
	PreOrder(node1);
	printf("\n");
	InOrder(node1);
	printf("\n");
	PostOrder(node1);
	printf("\n");
	int size=BinaryTreeSize(node1);
	printf("size : %d\n", size);
	size=BinaryTreeSize(node1);
	printf("size : %d\n", size);
	int leafsize = BinaryTreeLeafSize(node1);
	printf("leafsize : %d\n", leafsize);
	int k = 3;
	int levelsize=BinaryTreeLevelKSize(node1, k);
	printf("levelsize : %d\n", levelsize);
	int high = BinaryTreeDepth(node1);
	printf("high : %d\n", high);
	
	printf("%d\n", BinaryTreeFind(node1,4)->data);

	LevelOrder(node1);
	printf("\n");

	printf("%s\n", BinaryTreeComplete == false ? "不是完全二叉树" : "是完全二叉树");
	BinaryTreeDestory(&node1);
}

int main()
{
	Test();
	return 0;
}