[数据结构](9)二叉树的遍历

文章目录


二叉树不同于我们先前学的数据结构，我们不讲它的增删查改，如果只是单纯的存储数据，不如线性表。

如何遍历二叉树

二叉树主要有两种遍历方式：

  1. 深度优先遍历（DFS）：先往深处走，遇到叶子结点再往回走。
    • 前序遍历（先序遍历/先根遍历）：根左右
    • 中序遍历（中根遍历）：左根右
    • 后序遍历（后根遍历）：左右根
  2. 广度优先遍历（BFS）：一层一层的去遍历。
    • 层序遍历

前中后序指的就是根的遍历顺序，

前序遍历就是先访问根，再遍历左子树，最后遍历右子树。

中序遍历就是先遍历左子树，再访问根，最后遍历右子树。

后序遍历就是先遍历左子树，再遍历右子树，最后访问根。

LtE4fS.jpg

以这棵二叉树为例，这里也列出访问到NULL的位置。

前序遍历：1 2 3 NULL NULL NULL 4 5 NULL NULL 6 NULL NULL

中序遍历：NULL 3 NULL 2 NULL 1 NULL 5 NULL 4 NULL 6 NULL

后序遍历：NULL NULL 3 NULL 2 NULL NULL 5 NULL NULL 6 4 1

以下文字解释前序和中序是怎样遍历的（我觉得文字更适合理解，如果你有耐心看完的话。动图无论看多少遍也只是知道个顺序，对递归的思想理解不够深刻）：

（荧光笔记号表示记录）

前序遍历：先访问根1，再访问左子树，子树依然要按照根左右的方式遍历，那么先访问根2，再访问左子树，左子树的根是3，访问完根3，再访问它的左子树，左子树是NULL，就回退，再访问右子树，右子树也是NULL，继续回退，那么3这棵树访问完毕，3是2的左子树，接下来回退，访问2的右子树，2的右子树是NULL，此时2这棵树也访问完毕，回退，访问根的右子树，先访问根4，再访问左子树5，5的左子树是NULL，右子树也是NULL，回退，访问根4的右子树6，6的左子树是NULL右子树是NULL，回退，这样4这棵子树访问完毕，整棵树就访问完毕。

中序遍历：要遍历整棵树，先遍历左子树，1的左子树是2，2的左子树是3，3的左子树NULL，回退，记录3，然后记录3的右子树NULL，这样以3为根的子树遍历完毕，它是2的左子树，回退，接下来记录2，再记录2的右子树NULL，2这棵树就遍历完毕，回退，接下来记录1，然后遍历1的右子树，右子树依然要保证左根右的顺序，先遍历4的左子树5，5的左子树NULL，回退，根5，右子树NULL，这样5这棵树遍历完毕，它是4的左子树，回退，记录根4，然后遍历右子树6，6的左子树NULL，回退，根6，右子树NULL，这样6这棵树遍历完毕，4这棵树也就遍历完毕，整棵树就遍历完毕。

后序也是一样的道理。

可以发现，中序和后序不是走到一个结点就一定会把这个结点记录下来，因为它必须先遍历这个结点的左子树，

注意体会其中的递归思想，把遍历一棵树，化为遍历它的各个子树。

前序就像绕外围逆时针跑一圈，中序就是向下投影，后序就像是剪葡萄。这种虽然很好理解，但是抛弃了递归思想，适合人脑，不适合电脑。想写好代码还是要多多理解递归思想。

层序遍历：

从左往右从上往下一层一层地遍历，顺序就和二叉树的顺序存储一样。如上图，层序遍历结果为124356

练习：

1.已知某二叉树的中序遍历序列为JGDHKBAELIMCF，后序遍历序列为JGKHDBLMIEFCA，则其前序遍历序列为（ ）

A. ABDGHJKCEFILM

B. ABDGJHKCEILMF

C. ABDHKGJCEILMF

D. ABDGJHKCEIMLF

答案：B

结合中序和后序，我们可以构造出这棵二叉树：

后序遍历序列从右往左看，A一定是根。C在A的左边还是右边呢，结合中序遍历序列，C在A的右边，所以C是A的右孩子。F在C的右边，F是C的右孩子。E在A的右边，C的左边，所以是C的左孩子。I在E的右边，C的左边，所以是E的右孩子。M在I的右边C的左边，所以是I的右孩子。L在E的右边，I的左边，所以是I的左孩子。B在A的左边，所以是A的左孩子，D在B的左边，所以是B的左孩子，H在B的左边，D的右边，所以是D的右孩子。K在H的右边B的左边，所以是H的右孩子。G在D的左边，所以是D的左孩子。J在G的左边，所以是G的左孩子。

最终构建的二叉树如图。

LNaGH1.jpg

前序遍历就像绕着外围逆时针走一圈，序列为ABDGJHKCEILMF，选B

2.已知某二叉树的前序遍历序列为ABDEC，中序遍历序列为BDEAC，则该二叉树（ ）

A. 是满二叉树

B. 是完全二叉树，不是满二叉树

C. 不是完全二叉树

D. 是所有的结点都没有右子树的二叉树

前序遍历从左往右看，A一定是根。B在A的左边，B是A的左孩子。D在B的右边，A的左边，D是B的右孩子。E在D的右边，A的左边，E是D的右孩子。C在A的右边，C是A的右孩子。

最终构建的二叉树如图

LNaO8U.jpg

很明显，选C。

代码实现

构建

二叉树的递归构建放到后面讲。先从最简单的遍历开始。

这里手动构建一棵二叉树。

LtE4fS.jpg

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

BTNode* BuyBTNode(BTDataType x)
{
	BTNode* node = (BTNode*)malloc(sizeof(BTNode));
	if (node == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}

	node->data = x;
	node->left = node->right = NULL;
	return node;
}

BTNode* CreatBinaryTree()
{
	BTNode* node1 = BuyBTNode(1);
	BTNode* node2 = BuyBTNode(2);
	BTNode* node3 = BuyBTNode(3);
	BTNode* node4 = BuyBTNode(4);
	BTNode* node5 = BuyBTNode(5);
	BTNode* node6 = BuyBTNode(6);

	node1->left = node2;
	node1->right = node4;
	node2->left = node3;
	node4->left = node5;
	node4->right = node6;

	return node1;
}

前中后序递归遍历

以下就是递归遍历，写递归要注意三要素：

  • 确定参数和返回类型
  • 确定终止条件（最小子问题）
  • 确定单层递归的逻辑

前序遍历

void PrevOrder(BTNode* root) { // 确定参数和返回类型
	if (root == NULL) return;  //遇到NULL就回退，也就是遇到NULL就终止这一层递归
	printf("%d ", root->data); //前序是根左右，逻辑就是先打印根结点的值，再去遍历左子树，最后遍历右子树
	PrevOrder(root->left);
	PrevOrder(root->right);
}

中序和后序同理

中序遍历

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

后序遍历

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

结点个数

不难写出如下代码：

void BTreeSize(BTNode* root, int* count)
{
	if (root == NULL) return;
	(*count)++;
	BTreeSize(root->left, count);
	BTreeSize(root->right, count);
}

遍历+递归计数，先定义一个局部变量count = 0，传地址进去。也可以直接把count定义为全局变量；

注意：不要把局部变量定义在递归函数内部，否则每一层递归都会重新创建一个新的局部变量，每次回退都会自动销毁这个局部变量。

就算是static定义的静态局部变量也不行，因为无法重新初始化，多次调用计数只会叠加。

优化（分治）：

先把大问题转换为小的子问题：一棵树的结点数就是它的左子树的结点数+右子树的结点数+根结点数1，

这种做法叫做分治，字面意思就是“分而治之”，把大问题转化为两个或多个相似的子问题，再把子问题分成更小的子问题，直到最后的子问题简单到可以直接求解。

重新思考递归三要素：

  1. 确定参数和返回类型：每一层递归表示以root为根的树有多少结点。所以参数为BTNode* root，返回类型为int
  2. 确定终止条件：root为NULL，返回0
  3. 每一层的递归逻辑：左子树结点数+右子树结点数+1，就是这棵树的结点数。
int BTreeSize(BTNode* root) {
	return root == NULL ? 0 : BTreeSize(root->left) + BTreeSize(root->right) + 1;
}

叶子结点个数

也可以采用遍历+计数的方法。只要在计数前加if判断左右子树是否满足都为空的条件即可。

我们重点讲分治：一棵树的叶子结点树就是它的左子树的叶子结点数+右子树的叶子结点数

递归三要素：

  1. 确定参数和返回类型：每一层递归表示以root为根的树有多少叶子节点。
  2. 确定终止条件：root为NULL，返回0，root的左右子树都为NULL，返回1。
  3. 每一层的递归逻辑：左子树叶子结点数+右子树叶子结点数，就是这棵树的叶子结点数。
int BTreeLeafSize(BTNode* root)
{
	if (root == NULL) return 0;
	if (root->left == NULL && root->right == NULL) return 1;
	return BTreeLeafSize(root->left) + BTreeLeafSize(root->right);
}

第k层的结点个数

也可以采用遍历+计数的方法。但是如果树很大，k很小，难道也要全部遍历一遍吗？

可能你会想到层序遍历，那当然也可以，我们放到后面讲。

分治：一棵二叉树第k层的结点个数就是左子树第k-1层的结点数+右子树第k-1层的结点数。

递归三要素：

  1. 确定参数和返回类型：每一层递归表示以root为根的树的第k层有多少个结点。参数为BTNode* root, int k，返回类型为int
  2. 确定终止条件：root为NULL，返回0。k=1，说明这个root就是第k层的一个结点，返回1
  3. 每一层的递归逻辑：左子树第k-1层结点数+右子树第k-1层结点数，就是这棵树的第k层的结点数。
int BTreeKLevelSize(BTNode* root, int k)
{
	assert(k >= 1);

	if (root == NULL) return 0;
	if (k == 1) return 1;
	return BTreeKLevelSize(root->left, k - 1) + BTreeKLevelSize(root->right, k - 1);
}

二叉树的深度（高度）

分治：一棵二叉树的深度就是左子树的深度和右子树的深度中大的那个+1，+1是因为根结点自己算一个深度。

递归三要素：

  1. 确定参数和返回类型：每一层递归表示以root为根的树的深度。参数为BTNode* root，返回类型为int
  2. 确定终止条件：root为NULL，返回0。
  3. 每一层的递归逻辑：找出左右子树深度大的+1
int BTreeDepth(BTNode* root)
{
	if (root == NULL) return 0;

	int leftDepth = BTreeDepth(root->left);
	int rightDepth = BTreeDepth(root->right);

	return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}

找值为x的结点

分治：一棵二叉树中值为x的结点就是左子树中值为x的结点或者右子树中值为x的结点或者根结点。

递归三要素：

  1. 确定参数和返回类型：每一层递归表示以root为根的树中，值为x的结点的位置。参数为BTNode* root, BTDataType x，返回类型BTNode*
  2. 确定终止条件：root为NULL，返回NULL。root的值为x，返回root。注意：root的值不是x时，不要返回NULL，因为它的左右子树还有可能有x
  3. 每一层的递归逻辑：如果左子树或右子树有x，就返回x结点。都没有就返回NULL。注意：不要使用&& 和||，除非返回类型是bool。而这里是要具体地返回一个地址。
BTNode* BTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL) return NULL;
	if (root->data == x) return root;

	BTNode* ret1 = BTreeFind(root->left, x);
	if (ret1) return ret1;

	BTNode* ret2 = BTreeFind(root->right, x);
	if (ret2) return ret2;

	return NULL;
}

最后三行可以简化成一行return BTreeFind(root->right, x)，为了保证可读性，建议还是像上面那样写。

二叉树销毁

采用后序遍历的方式，保证根最后释放。

void BTreeDestory(BTNode* root)
{
	if (root == NULL) return;

	BTreeDestory(root->left);
	BTreeDestory(root->right);
	free(root);
}

二叉树的递归创建

本文一开始手动创建二叉树，然后先讲了三种遍历。

现在我们来试着采用前序遍历的方法递归创建。

给定前序遍历序列，比如ABC##DE#G##F###，其中“#”表示空格，空格表示空树。

以此建立二叉树。

递归三要素：

  1. 确定参数和返回类型：每一层递归表示字符串a中以下标为i的值为根节点创建的二叉树。所以参数为char* a, int* i返回类型为BTNode*
  2. 确定终止条件：#表示空树，不用继续向下递归，return NULL。注意：数组仍然要继续遍历，不要忘了(*i)++
  3. 确定每一层递归的逻辑：能走到终止条件之后，说明肯定不是空树，就先申请一块空间，然后赋值。此时根已经创建完成，按照前序遍历的顺序，接下来创建左树，然后创建右数，最后返回根root。
BTNode* CreateTree(char* a, int* i)
{
    if (a[*i] == '#')
    {
        (*i)++;
        return NULL;
    }
    BTNode* root = (BTNode*)malloc(sizeof(BTNode));
    root->val = a[(*i)++];
    root->left = CreateTree(a, i);
    root->right = CreateTree(a, i);
    return root;
}

这道题可以用这种方法创建二叉树?二叉树遍历_牛客题霸_牛客网 (nowcoder.com)

完整代码

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

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

BTNode* BuyBTNode(BTDataType x)
{
	BTNode* node = (BTNode*)malloc(sizeof(BTNode));
	if (node == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}

	node->data = x;
	node->left = node->right = NULL;
	return node;
}

BTNode* CreatBinaryTree()
{
	BTNode* node1 = BuyBTNode(1);
	BTNode* node2 = BuyBTNode(2);
	BTNode* node3 = BuyBTNode(3);
	BTNode* node4 = BuyBTNode(4);
	BTNode* node5 = BuyBTNode(5);
	BTNode* node6 = BuyBTNode(6);

	node1->left = node2;
	node1->right = node4;
	node2->left = node3;
	node4->left = node5;
	node4->right = node6;

	return node1;
}

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

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

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

//void BTreeSize(BTNode* root, int* count)
//{
//	if (root == NULL) return;
//	(*count)++;
//	BTreeSize(root->left, count);
//	BTreeSize(root->right, count);
//}

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

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

int BTreeKLevelSize(BTNode* root, int k)
{
	assert(k >= 1);

	if (root == NULL) return 0;
	if (k == 1) return 1;
	return BTreeKLevelSize(root->left, k - 1) + BTreeKLevelSize(root->right, k - 1);
}

int BTreeDepth(BTNode* root)
{
	if (root == NULL) return 0;

	int leftDepth = BTreeDepth(root->left);
	int rightDepth = BTreeDepth(root->right);

	return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}

BTNode* BTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL) return NULL;
	if (root->data == x) return root;

	BTNode* ret1 = BTreeFind(root->left, x);
	if (ret1) return ret1;

	//return BTreeFind(root->right, x);
	BTNode* ret2 = BTreeFind(root->right, x);
	if (ret2) return ret2;

	return NULL;
}

void BTreeDestory(BTNode* root)
{
	if (root == NULL) return;

	BTreeDestory(root->left);
	BTreeDestory(root->right);
	free(root);
}

建议刷题：

965. 单值二叉树 - 力扣（LeetCode） (leetcode-cn.com)

100. 相同的树 - 力扣（LeetCode） (leetcode-cn.com)

101. 对称二叉树 - 力扣（LeetCode） (leetcode-cn.com)

144. 二叉树的前序遍历 - 力扣（LeetCode） (leetcode-cn.com)

94. 二叉树的中序遍历 - 力扣（LeetCode） (leetcode-cn.com)

145. 二叉树的后序遍历 - 力扣（LeetCode） (leetcode-cn.com)

572. 另一棵树的子树 - 力扣（LeetCode） (leetcode-cn.com)

层序遍历

队列实现

队列先进先出，适合层序遍历。栈先进后出，适合递归。

  • 先让根结点进队列，根结点出去之后让自己的孩子结点进队列。
  • 孩子结点出去之后也让下一层自己的孩子进队列。
  • 重复直到队列为空。

LUGOSJ.gif

就像生孩子一样，前赴后继。

纯c需要先实现队列。?[数据结构](6)栈和队列，已经写好的直接导入即可。

代码如下：

void LevelOrder(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	if (root) QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		printf("%d ", front->data);
		if (front->left) QueuePush(&q, front->left);
		if (front->right) QueuePush(&q, front->right);
	}
	printf("\n");
	QueueDestory(&q);
}

判断完全二叉树

判断一棵二叉树是否是完全二叉树。

通过完全二叉树的顺序存储可以发现，完全二叉树的中间没有NULL

L9l9VU.jpg

思路：

  • 通过层序遍历，把二叉树变成顺序存储的形式。与一般层序遍历不同的是，NULL也要进入队列。
  • 判断中间有没有NULL，如果有，则不是完全二叉树。

代码实现并不需要额外创建一个数组，只要队列中第一个队头为NULL时，看队列中是否有非空即可。

代码如下：

bool BTreeComplete(BTNode* root)
{
	Queue q;
	QueueInit(&q);

	if (root) QueuePush(&q, root);

	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		if (front == NULL) break; // 遇到队头为NULL，就退出循环
		QueuePush(&q, front->left); // 不论是否为NULL，都进入队列
		QueuePush(&q, front->right);
	}
	// 找队列中是否有非空，有则return false
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);
		QueuePop(&q);
		if (front) 
		{
			QueueDestory(&q);
			return false;
		}
	}

	QueueDestory(&q); // 不要忘记销毁队列
	return true;
}

总结

本节学习了二叉树前中后序遍历的递归写法。这让我对递归有了进一步的理解，比如如何理解分治，大问题化为子问题，递归三要素。

围绕这三种遍历，还完成了结点个数，叶子结点个数，第k层结点个数等等函数的实现。

然后就是非递归的层序遍历，并用它判断了完全二叉树。

初阶数据结构的学习已经接近尾声，期待后面的知识?

版权声明：本文为CegghnnoR原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接和本声明。