数据结构——二叉树

目录

前言

一、二叉树链式结构

二、二叉树的遍历

2.1 前序遍历

2.2 中序遍历

2.3 后序遍历

2.4 层序遍历

三、二叉树的节点

​编辑

3.1 二叉树节点个数

3.2 二叉树的深度

3.3 二叉树叶子节点个数

3.4 二叉树第k层节点个数

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

四、二叉树的创建和销毁

4.1 二叉树的创建

4.2 二叉树的销毁

4.3 是否为完全二叉树

总结

前言

我们之前讲了二叉树的顺序存储的一种——堆，今天我们来了解二叉树的链式存储。了解二叉树的遍历，和二叉树的节点。通过递归分治的思想来实现二叉树的功能。

一、二叉树链式结构

为了先了解到二叉树的基本操作，我们先手动创造一个二叉树(与后面的二叉树的创建无关)。等二叉树结构了解的差不多时，我们反过头再来研究二叉树真正的创建方式。

二叉树的节点：

typedef int BTDataType;
typedef struct BTDataType {
	BTDataType val;
	struct BTDataType* left;//左子树
	struct BTDataType* right;//右子树
 
}BTNode;

创建一个节点：

// 创建节点
BTNode* BuyNode(BTDataType x) {
	BTNode* n = (BTNode*)malloc(sizeof(BTNode));
	if (n == NULL)
	{
		perror("malloc fail");
	}
	n->val = x;
	n->right = n->left = NULL;
	return n;
}

现在我们可以手动创建一个二叉树了

//手动创建树
BTNode* CreatBinaryTree()
{
	BTNode* n1 = BuyNode(1);
	BTNode* n2 = BuyNode(2);
	BTNode* n3 = BuyNode(3);
	BTNode* n4 = BuyNode(4);
	BTNode* n5 = BuyNode(5);
	BTNode* n6 = BuyNode(6);
 
	n1->left = n2;
	n1->right = n4;
	n2->left = n3;
	n4->left = n5;
	n4->right = n6;
 
	return n1;
}

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

二、二叉树的遍历

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

2.1 前序遍历

// 二叉树前序遍历
void PreOrder(BTNode* root) {
	if (root == NULL)
	{
		printf("N ");
		return;
	}
	printf("%d ", root->val);
	PreOrder(root->left);
	PreOrder(root->right);
 
}

前序遍历的遍历顺序为：根   左子树   右子树

2.2 中序遍历

//二叉树中序遍历
void InOrder(BTNode* root) {
	if (root == NULL)
	{
		printf("N ");
		return;
	}
	InOrder(root->left);
	printf("%d ", root->val);
	InOrder(root->right);
}

中序遍历的遍历顺序为：左子树  根   右子树

2.3 后序遍历

// 二叉树后序遍历
void PostOrder(BTNode* root) {
	if (root == NULL)
	{
		printf("N ");
		return;
	}
	PostOrder(root->left);
	PostOrder(root->right);
	printf("%d ", root->val);
}

后序遍历的遍历顺序为：左子树   右子树  根

三种遍历的运行结果为(其中N代表节点为空)：

2.4 层序遍历

除了先序遍历、中序遍历、后序遍历外，还可以对二叉树进行层序遍历。设二叉树的根节点所在 层数为1，层序遍历就是从所在二叉树的根节点出发，首先访问第一层的树根节点，然后从左到右访问第2层上的节点，接着是第三层的节点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历。

与上面三种通过递归来遍历二叉树的不同，层序遍历使用的循环来遍历二叉树。

为了实现二叉树的层序遍历，我们通过之前学到的队列先进先出的特性来实现。

//层序遍历
void BinaryTreeLevelOrder(BTNode* root) {
 
	Queue pq;//创建队列
	QueueInit(&pq);
 
	if (root != NULL)
		QueuePush(&pq, root);
 
	while (!QueueEmpty(&pq))
	{
		BTNode* foront = QueueFront(&pq);//保存根节点
		QueuePop(&pq);
 
		if (foront != NULL)
		{
			printf("%d ", foront->val);//根节点出队列它的左右子树入队列
			QueuePush(&pq, foront->left);
			QueuePush(&pq, foront->right);
		}
		else
		{
			printf("N ");
		}
	}
	QueueDestroy(&pq);
 
}

运行结果：

三、二叉树的节点

了解到二叉树的遍历后，我们来求二叉树节点个数以及高度等，实现这些我们需要理解递归分治。

找到递归子问题和返回条件(最小子问题)

以下图为例：

3.1 二叉树节点个数

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

递归子问题：找根的左右子树的节点数

返回条件：当节点为空时

3.2 二叉树的深度

int BinaryTreedepth(BTNode* root)
{
	if (root == NULL)
		return 0;
 
	int leftdepth = BinaryTreedepth(root->left);
	int rightdepth = BinaryTreedepth(root->right);
 
	return leftdepth > rightdepth ? leftdepth + 1 : rightdepth + 1;
 
}

递归子问题：找左右子树的深度最大的

返回条件：当节点为空时

注意：返回时本节点深度也要算，即返回深度要加1。

3.3 二叉树叶子节点个数

// 二叉树叶子节点个数
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);
}

递归子问题：左右子树的叶子节点数的和

返回条件：当节点为空时和左右子树同时为空

3.4 二叉树第k层节点个数

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

递归子问题：在k-1层左右子树的节点

返回条件：当节点为空时和k等于1

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

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

递归子问题：在左和右子树分别寻找

返回条件：当节点为空时和当节点找到

四、二叉树的创建和销毁

我们之前是通过手动来创建一个二叉树的，现在我们来实现二叉树真正的创建。

4.1 二叉树的创建

//其中a[]="abc##de#g##f###",pi为下标
 
 
BTNode* BinaryTreeCreate(BTDataType* a, int* pi){
    if(a[*pi]=='#')
    {
        (*pi)++;
        return NULL;
    }
 
    BTNode* root=(BTNode*)malloc(sizeof(BTNode));
    root->val=a[(*pi)++];
    //创建左子树
    root->left=BinaryTreeCreate(a,pi);
 
    //创建右子树
    root->right=BinaryTreeCreate(a,pi);
 
    return root;
}

// 二叉树销毁
void BinaryTreeDestory(BTNode** root) {
	if (root == NULL)
		return;
 
    //分别销毁节点的左右子树
	BinaryTreeDestory(&(*root)->left);
	BinaryTreeDestory(&(*root)->right);
 
	free(*root);
	*root = NULL;
}

我们这里使用二级指针来销毁二叉树，也可以用一级指针，只不过需要在函数外面将根节点手动置空。

4.3 是否为完全二叉树

//是否为完全二叉树
bool BinaryTreeComplete(BTNode* root) {
	Queue pq;
	QueueInit(&pq);
 
	if (root != NULL)
		QueuePush(&pq, root);
 
	while (!QueueEmpty(&pq))
	{
		BTNode* foront = QueueFront(&pq);
		QueuePop(&pq);
 
		if (foront == NULL)
			break;
 
		QueuePush(&pq, foront->left);
		QueuePush(&pq, foront->right);
 
	}
 
	while (!QueueEmpty(&pq))
	{
		BTNode* foront = QueueFront(&pq);
		QueuePop(&pq);
 
		if (foront != NULL)
			return false;
	}
	return true;
	QueueDestroy(&pq);
}

我们运用层序遍历来解决这个问题，只要遇到空结点，判断后面节点是否为空，只要有一个不为空，就不是完全二叉树。

总结

以上文章，我们讲了二叉树的链式结构的遍历和实现，希望对你有所帮助。