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

数据结构-链式二叉树-四种遍历

article 2024/11/11 5:02:06

博客主页：【夜泉_ly】
本文专栏：【数据结构】
欢迎点赞👍收藏⭐关注❤️

数据结构-链式二叉树-四种遍历

1.前言
2.前、中、后序遍历
- 2.1前序遍历
- 2.1中、后序遍历
3.层序遍历
- 3.1递归实现
- 3.2队列实现
- - 关于在`Pop`之后为什么还能用`tmp`访问节点？
  - 关于都已经把队列`Pop`为空了为什么还要`QueueDestroy`？
4.浅谈DFS与BFS

1.前言

在我之前的文章数据结构-堆-详解中，我对堆这种特殊的完全二叉树做了详细介绍。
完全二叉树非常适合用数组存储，但一般的二叉树呢？如下图所示：
在这里插入图片描述
可以发现，普通二叉树若使用数组存储，会浪费大量空间，这时，链式存储结构成为更好的选择。
在这种结构中，每个节点应包含自身所存储的数据，以及指向左右子树的指针。
可以通过以下结构体定义二叉树节点：

typedef char BTDataType;

typedef struct TreeNode
{
	BTDataType val;
	struct TreeNode* left;
	struct TreeNode* right;
}TreeNode;

为了便于理解，我手搓了一个简单的二叉树：
在这里插入图片描述
代码如下：

TreeNode* BuyTreeNode(BTDataType x)
{
	TreeNode* tmp = (TreeNode*)malloc(sizeof(TreeNode));
	if (!tmp)
	{
		perror("BuyTreeNode::malloc");
		return NULL;
	}
	tmp->val = x;
	tmp->left = NULL;
	tmp->right = NULL;
	return tmp;
}
TreeNode* CreatBinaryTree()
{
	TreeNode* root = BuyTreeNode('a');
	TreeNode* n1 = BuyTreeNode('b');
	TreeNode* n2 = BuyTreeNode('c');
	TreeNode* n3 = BuyTreeNode('d');
	TreeNode* n4 = BuyTreeNode('e');
	TreeNode* n5 = BuyTreeNode('f');
	TreeNode* n6 = BuyTreeNode('g');
	root->left = n1;
	root->right = n2;
	n1->left = n3;
	n1->right = n4;
	n2->left = n5;
	n2->right = n6;
	return root;
}

注意：这并不是二叉树真正的创建方法，等对于二叉树的结构有更深入的了解后，再讲创建。

在对二叉树进行各项操作时，应对其结构有明确的认识：
在这里插入图片描述
对任意一个二叉树，都由 根、左子树、右子树 组成。
而左右子树，也是二叉树，也有对应的 根、左子树、右子树。
因此，二叉树的定义是递归的，在对二叉树进行处理时也常常使用递归。
而对二叉树的递归操作也应以 根、左子树、右子树 为基础展开。

2.前、中、后序遍历

2.1前序遍历

二叉树的前序遍历：先访问根，再遍历左子树，最后遍历右子树。

void BinaryTreePrevOrder(TreeNode* root)
{
	if (!root)
	{
		printf("NULL ");
		return;
	}
	printf("%c ", root->val);
	BinaryTreePrevOrder(root->left);
	BinaryTreePrevOrder(root->right);
}

先判断根，如果为空，就打印NULL并返回；
若不为空，则先打印根的值，再遍历左子树，最后遍历右子树。

在二叉树这块，可以先画画逻辑结构图：
在这里插入图片描述
虽然画的不全，但大概就是这么个意思。
如果难以理解时可以再画画递归展开图：把代码是怎么一行行执行的给画出来。
经过分析，可知打印结果应该是：a b d NULL NULL e NULL NULL c f NULL NULL g NULL NULL。
在这里插入图片描述

也可以选择不打印空，结果是：a b d e c f g。
在这里插入图片描述

在画过图后，应对二叉树的遍历有更清楚的认识：
在打印d后为什么直接打印e?
并非是从d的节点直接到e的节点，
而是先访问d的两个空的左右子树，d结束了左右子树的遍历，返回到b。
此时b结束了它的左子树的遍历，于是开始遍历右子树，然后才到了e处。

2.1中、后序遍历

二叉树的中序遍历：先遍历左子树，再访问根，最后遍历右子树。

void BinaryTreeInOrder(TreeNode* root)
{
	if (!root)
	{
		printf("NULL ");
		return;
	}
	BinaryTreeInOrder(root->left);
	printf("%c ", root->val);
	BinaryTreeInOrder(root->right);
}

二叉树的后序遍历：先遍历左子树，再遍历右子树，最后访问根。

void BinaryTreePostOrder(TreeNode* root)
{
	if (!root)
	{
		printf("NULL ");
		return;
	}
	BinaryTreePostOrder(root->left);
	BinaryTreePostOrder(root->right);
	printf("%c ", root->val);
}

此时，可以写个代码测试一下：

int main()
{
	TreeNode* root = CreatBinaryTree();
	printf("BinaryTreePrevOrder:");
	BinaryTreePrevOrder(root);
	printf("\nBinaryTreeInOrder:");
	BinaryTreeInOrder(root);
	printf("\nBinaryTreePostOrder:");
	BinaryTreePostOrder(root);
	return 0;
}

运行结果：
在这里插入图片描述
也可以不打印NULL：

3.层序遍历

就是从上至下从左至右的遍历：
在这里插入图片描述

3.1递归实现

此实现方法并不重要，所以略讲。
先求个高度：

int TreeHeight(TreeNode* root)
{
	if (!root)
		return 0;
	int leftheight = TreeHeight(root->left);
	int rightheight = TreeHeight(root->right);
	return leftheight > rightheight ? 1 + leftheight : 1 + rightheight;
}

再写个打印第k层元素的函数：

void BinaryTreeLevelPrint(TreeNode* root, int level)
{
	if (!root)
		return;
	if (level == 1)
		printf("%c ", root->val);
	else
	{
		BinaryTreeLevelPrint(root->left, level - 1);
		BinaryTreeLevelPrint(root->right, level - 1);
	}
}

最后组合起来，即一层一层的打印：

void BinaryTreeLevelOrder(TreeNode* root)
{
	int level = TreeHeight(root);
	for (int i = 1; i < level; i++)
	{
		BinaryTreeLevelPrint(root, i);
	}
}

测试一下：

int main()
{
	TreeNode* root = CreatBinaryTree();
	printf("BinaryTreeLevelOrder:");
	BinaryTreeLevelOrder(root);
	return 0;
}

结果：
在这里插入图片描述

3.2队列实现

二叉树层序遍历使用递归比较麻烦，且不太直观，因此，通常使用另一种方法，即队列：

先将根节点入队列
将队首的节点出队列，并带入当前节点的两个非空子节点
重复
再重复
队列为空，停止

其中，有关队列的函数可直接CV --> 数据结构-栈、队列-详解。

需注意的是，存入队列的是指向节点的指针，因此，需改变一下队列存储的数据类型：

//typedef int QDatatype;
typedef TreeNode* QDatatype;

代码实现：

void BinaryTreeLevelOrder(TreeNode* root)
{
	Queue q;
	QueueInit(&q);
	if (!root);
	QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		TreeNode* tmp = QueueFront(&q);
		QueuePop(&q);
		printf("%c ", tmp->val);
		if (tmp->left)
			QueuePush(&q, tmp->left);
		if (tmp->right)
			QueuePush(&q, tmp->right);
	}
	printf("\n");
	QueueDestroy(&q);
}