【数据结构与算法分析】树上漫步之探究前序、中序、后序、广度优先遍历算法的实现与优化

前言

  二叉树是数据结构中最基本的数据结构之一，它在计算机科学中有着非常重要的应用。二叉树的遍历是指按照一定的顺序遍历二叉树中的所有节点，是二叉树的最基本操作之一。

二叉树的遍历方式

构建二叉树

  函数createNode创建一个新的二叉树节点并返回该节点的指针。该函数接收一个整数类型的参数 val，该参数用于表示新节点的值，节点中的两个指针都为NULL。

// 创建新节点的函数
struct TreeNode *createNode(int val) {
	struct TreeNode *node = (struct TreeNode*) malloc(sizeof(struct TreeNode));
	node->val = val;
	node->left = NULL;
	node->right = NULL;
	return node;
}
1
2
3
4
5
6
7
8

  函数buildTree作用是构建一棵具有固定结构的二叉树并返回根节点的指针。在函数内部，先创建一个根节点 root，其值为 1，然后通过createNode函数创建了该二叉树的所有节点，并设置它们的值和相应的子树指针。

// 构建一棵二叉树
struct TreeNode *buildTree() 
{
	struct TreeNode *root = createNode(1);
	root->left = createNode(2);
	root->right = createNode(3);
	root->left->left = createNode(4);
	root->left->right = createNode(5);
	root->right->left = createNode(6);
	root->right->right = createNode(7);
	root->left->left->left = createNode(8);
	root->left->left->right = createNode(9);
	return root;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

  在经过buildTree函数后得到二叉树：

递归遍历二叉树

  递归遍历具体思路步骤如下：

• 首先判断当前节点 node 是否为空，如果为空则直接返回。
• 递归遍历当前节点 node 的左子树，即调用 inOrder(node->left)。【1】
• 遍历当前节点，即输出节点 node 的值 node->val。【2】
• 递归遍历当前节点 node 的右子树，即调用 inOrder(node->right)。【3】

  那么，中序遍历的代码详细代码如下：

// 递归中序遍历
void inOrder(struct TreeNode*node)
{
	// 判断节点是否为空
	if (node == NULL) return;
	// 先访问左孩子
	inOrder(node->left);
	// 访问自己
	printf(" %d ",node->val);
	// 访问右孩子
	inOrder(node->right);
}
1
2
3
4
5
6
7
8
9
10
11
12

  注意： 将思路步骤【2】移动到【1】前就为前序遍历。 将思路步骤【2】移动到【3】后就为前序遍历。

非递归遍历二叉树

  函数 inOrder2作用是对二叉树进行非递归中序遍历，这里使用栈来模拟递归中序遍历操作。函数的思路为：

• 函数接受两个参数 root（二叉树的根节点） 和 nodeCount（节点总数），其中 nodeCount 用于初始化遍历栈的大小。

• 首先使用 malloc 函数分配一个大小为 nodeCount 的指针数组 data，用于存储节点指针（模拟栈结构）。

• 其次，定义一个栈顶指针 dataLen 并初始化为 0，同时初始化一个指针 p，用于存储当前节点的指针。

• 之后，进入遍历循环。判断当前节点 p 是否为空，如果不为空，则将其入栈，并将 p 更新为其左子节点。否则，从栈中弹出一个节点 p，输出其值，将 p 更新为其右子节点。 循环执行直到栈为空且当前节点 p 为 NULL。

• 最后，释放动态分配的栈空间 data。

// 非递归中序遍历
void inOrder2(struct TreeNode*root,int nodeCount)
{
	// 初始化顺序栈
	struct TreeNode* *data = (struct TreeNode**)malloc(sizeof(struct TreeNode*)*nodeCount);
	// 栈顶指针
	char dataLen = 0;
	struct TreeNode*p = root;

	// 遍历
	while (p || dataLen)
	{
		// 节点不为空
		if (p)
		{
			// 先入栈再访问下一个左孩子
			data[dataLen++] = p;
			p = p->left;
		}
		else
		{
			// 到达叶子节点后 应该先访问叶子节点再回溯到父节点最后访问兄弟
			p = data[--dataLen];
			printf(" %d ",p->val);
			p = p->right;
		}
	}

	// 注销栈空间
	free(data);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

  由于该函数的思路是用栈模拟递归的操作，因此较递归方法更加节省内存，也能更好地控制函数执行顺序。

层次遍历

  函数 levelOrder作用是对二叉树进行层次遍历，即按照每层从左到右的顺序遍历节点并输出节点的值。函数接受两个参数：二叉树的根节点 root 和节点总数 nodeCount。其中，nodeCount 用于初始化顺序队列的大小。

• 函数内部，首先使用 malloc 函数动态分配一个大小为 nodeCount 的指针数组 queue，用于存储节点指针（模拟队列结构）。函数中还定义一个队头指针 front，一个队尾指针 rear，同时将指针 p 初始化为根节点 root。

• 首先，将根节点加入队列，也就是指针p。

• 再判断队列的队尾指针是否在队头指针前（队列为空）。如果条件成立，则进入遍历循环，从队头弹出一个节点 p，判断当前节点 p 是否为空。

• 循环内部，首先输出节点 p 的值，即访问节点。之后，如果节点 p 的左子节点存在，则将其左子节点入队列。如果节点 p 的右子节点存在，则将其右子节点入队列。

• 最后，进入下一轮循环并重复以上步骤。

// 层次遍历二叉树
void levelOrder(struct TreeNode*root,int nodeCount)
{
	// 定义一个顺序队列用于辅助层序遍历
	struct TreeNode* *queue = (struct TreeNode**)malloc(sizeof(struct TreeNode*)*nodeCount);
	//  队头       队尾
	int front = 0,rear = 0;
	struct TreeNode*p = root;
	
	// 将根节点加入队列
	queue[rear++] = p;
	// 遍历
	while ((rear != 0 && rear > front))
	{
		// [1] 出队列 
		p = queue[front++];
		// [2] 访问节点
		if (p)
			printf(" %d ",p->val);
		// [3] 将左节点入队列
		if (p->left)
			queue[rear++] = p->left;
		// [4] 将右节点入队列
		if (p->right)
			queue[rear++] = p->right;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

  注意：此处给出的是一个自上而下、从左往右的层析遍历的算法设计，如果需要将其改成自上而下、从右往左的层次遍历，那么只需要将while循环中的第[3]与第[4]步骤交换即可。
  该函数利用队列先进先出的特性，按层次顺序遍历二叉树，相对比较简单容易理解，且适用于任何类型的二叉树。

示例二叉树结果

  理论上结果：

  代码运行结果：

总结

  本文介绍二叉树的四种遍历方式：前序遍历、中序遍历、后序遍历和层次遍历。其中，前序遍历、中序遍历和后序遍历统称为深度优先遍历，而层次遍历为广度优先遍历。

  深度优先遍历和广度优先遍历均有其特点，常常用于解决不同的问题。深度遍历比较适用于需要遍历整棵树来获取全局信息的场合，例如求解树的深度、路径问题和节点的最长直径等。广度遍历则比较适用于在树的同一层节点之间寻找目标节点的场合，例如按层遍历二叉树、求解二叉树的最小深度等。