当前位置：首页 > article >正文

【数据结构】二叉树的前中后序遍历以及层序遍历（全解）

article 2025/1/25 2:21:03

在这里插入图片描述

文章目录

前言
1. 前中后序遍历
- 1.1 遍历规则
- 1.2 代码实现
- 1.3 图解遍历
2. 层序遍历
3.结点个数以及高度等
4. 判断是否为完全二叉树
5. 结语

前言

在前面学习完链式结构的二叉树之后，我们就可以进一步了解二叉树的几种遍历方式了，注意这里就可以深刻的体会到递归的思想了。

1. 前中后序遍历

二叉树的操作离不开树的遍历，我们先来看看二叉树的遍历有哪些方式

在这里插入图片描述

1.1 遍历规则

按照规则，二叉树的遍历有：前序/中序/后序的递归结构遍历：

（1）前序遍历(Preorder Traversal 亦称先序遍历)：访问根结点的操作发生在遍历其左右子树之前

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

（2）中序遍历(Inorder Traversal)：访问根结点的操作发生在遍历其左右子树之中（间）

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

（3）后序遍历(Postorder Traversal)：访问根结点的操作发生在遍历其左右子树之后

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

1.2 代码实现

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

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

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

1.3 图解遍历

以前序遍历为例：

在这里插入图片描述

函数递归栈帧图：

在这里插入图片描述

前序遍历结果：1 2 3 4 5 6

中序遍历结果：3 2 1 5 4 6

后序遍历结果：3 1 5 6 4 1

2. 层序遍历

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

在层序遍历这个地方就不可以和前面实现前中后序遍历一样使用递归的思想了。

实现层序遍历需要额外借助数据结构：队列

在这里插入图片描述

画图分析：在这里我们先让根节点（1）入队列，然后开始出队列。在出队列的同时，将它的左右孩子（2）、（3）分别入队列，以此类推，然后在（2）开始出队列的时候，将（2）的左右孩子分别入队列。这样就可以依次得到每一层结点了

在这里插入图片描述

// 层序遍历
void LevelOrder(BTNode * root)
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		BTNode * top = QueueFront(&q);
		printf("%c ", top->data);
		QueuePop(&q);
		if (top->_left)
		{
			QueuePush(&q, top->_left);
		}
		if (top->_right)
		{
			QueuePush(&q, top->_right);
		}
	}
	QueueDesTroy(&q);
}

3.结点个数以及高度等

下面这些方法的实现都是基于上面遍历的思想，请读者自行去完成这些方法，深刻领会遍历的递归美学。如果有不明白的地方可以在讨论区发起讨论❤️❤️❤️

// 二叉树结点个数
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);

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

// 判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTNode * root)
{
	Queue q;
	QueueInit(&q);
	QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		BTNode * top = QueueFront(&q);
		QueuePop(&q);
		if (top == NULL)
		{
			break;
		}
		QueuePush(&q, top->_left);
		QueuePush(&q, top->_right);
	}
	while (!QueueEmpty(&q))
	{
		BTNode * top = QueueFront(&q);
		QueuePop(&q);
		if (top != NULL)
		{
			QueueDesTroy(&q);
			return false;
		}
	}
	QueueDesTroy(&q);
	return true;
}