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

如何遍历二叉树

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

  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层结点个数等等函数的实现。

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

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