二叉树链式结构的前，中，后序真的很难理解吗？有这几张图教你轻松理解。

所属专栏：初始数据结构❤️
🚀 >博主首页：初阳785❤️
🚀 >代码托管：chuyang785❤️
🚀 >感谢大家的支持，您的点赞和关注是对我最大的支持！！！❤️
🚀 >博主也会更加的努力，创作出更优质的博文！！❤️
🚀 >关注我，关注我，关注我，重要的事情说三遍！！！！！！！！❤️

1.二叉树链式结构的实现

• 在学习二叉树的基本操作前，需先要创建一棵二叉树，然后才能学习其相关的基本操作。由于现在大家对二叉树结构掌握还不够深入并且我们现在是初始数据结构，后期还会有更深入的学习，所以为了降低大家学习成本，此处手动快速创建一棵简单的二叉树，快速进入二叉树操作学习，等二叉树结构了解的差不多时，我们反过头再来研究二叉树真正的创建方式.

• 我们以以下这张完全二叉树进行构造。
  

1.1二叉树链式结构

• 从上图我们可以看到一颗完全二叉树（满二叉树）的每个每个节点（除了叶子节点）都有两个分支，从这个思路我们想到了之前学带头双向循环链表，以此作对比不难想到我们也应该创建一个结构体节点，并且结构体成员应该包含了两个指针，一个做左指针，一个右指针。

typedef char BTDataType;

typedef struct BinaryTreeNode
{
	BTDataType _data; 				 //存放树的数据
	struct BinaryTreeNode* _left;	 //链接左孩子
	struct BinaryTreeNode* _right;   //链接右孩子
}BTNode;
1
2
3
4
5
6
7
8

• 于是我们根据图中的模型创建一颗树

BTNode* SetNode(int x)
{
	BTNode* ret = (BTNode*)malloc(sizeof(BTNode));
	if (ret == NULL)
	{
		perror("malloc");
		exit(-1);
	}
	ret->_data = x;
	ret->_left = NULL;
	ret->_right = NULL;

	return ret;
}

void text01()
{
	//先给树中每个节点开辟一块空间
	BTNode* node1 = SetNode(1);
	BTNode* node2 = SetNode(2);
	BTNode* node3 = SetNode(3);
	BTNode* node4 = SetNode(4);
	BTNode* node5 = SetNode(5);
	BTNode* node6 = SetNode(6);
	BTNode* node7 = SetNode(7);
	
	//把所有节点链接起来，形成一颗完全二叉树。
	node1->_left = node2;
	node1->_right = node3;
	node2->_left = node4;
	node2->_right = node5;
	node3->_left = node6;
	node3->_right = node7;
}
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
32
33
34

• 这样我们的树就手动创建成了。

2.链式二叉树的遍历

• 我们二叉树的一个重要使用场景就是递归也就是分治的思想，递归会贯彻我们整个有关使用二叉树的场景，这是因为二叉树的特殊结构，使用递归实现一些有关二叉树的问题会很轻松的解决，但是好用伴随着难理解，所以这一章节的学习会我会使用大量递归展开图来帮助小伙伴门的学习，将代码和图形结合起来理解将事半功倍。好了废话不多说，直接上干货。

2.1二叉树前序遍历

• 前序我们就抓住一点就行，就是分治思想，我们递归的的顺序就是，根，左，右。
  我们用代码实现是很简单的。

// 二叉树前序遍历 
void BinaryTreePrevOrder(BTNode* root)
{
	//根，左，右
	if (root == NULL)
	{
		return;
	}

	printf("%d ", root->_data);

	BinaryTreePrevOrder(root->_left);

	BinaryTreePrevOrder(root->_right);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

2.1.1递归图解析

🚨🚨🚨🚨🚨🚨由于这个图片面积过大，可能在这里会有看不清楚的情况，所以这里建议先保存图片到手机或者电脑上，再打开这样就可以清楚的看到图片上的步骤了。 🚨🚨🚨🚨🚨🚨

2.2二叉树中序遍历

• 有了前序的基础，我们中序其实也差不多，就是遍历的循序不同，我们的中序遍历的顺序是，左，根，右。
  代码实现起来也很简单，就是在前序的基础上稍微改变一下。

// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root)
{
	//左，根，右
	if (root == NULL)
	{
		return;
	}

	BinaryTreeInOrder(root->_left);

	printf("%d ", root->_data);

	BinaryTreeInOrder(root->_right);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

2.2.1递归图解析

🚨🚨🚨🚨🚨🚨由于这个图片面积过大，可能在这里会有看不清楚的情况，所以这里建议先保存图片到手机或者电脑上，再打开这样就可以清楚的看到图片上的步骤了。 🚨🚨🚨🚨🚨🚨

2.3二叉树后序遍历

• 相信看到这里的小伙伴们也发现了规律，不妨最后一个自己在画板上试着自己画一画，看一下自己时候掌握了，自己画完后再来跟我的对比一下看一下是否画对了。后序遍历的顺序是，左，右，根

// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root)
{
	//左，右,根
	if (root == NULL)
	{
		return;
	}

	BinaryTreePostOrder(root->_left);

	BinaryTreePostOrder(root->_right);

	printf("%d ", root->_data);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

2.3.1递归图解析

🚨🚨🚨🚨🚨🚨由于这个图片面积过大，可能在这里会有看不清楚的情况，所以这里建议先保存图片到手机或者电脑上，再打开这样就可以清楚的看到图片上的步骤了。 🚨🚨🚨🚨🚨🚨

3.前，中，后序的应用

3.1计算二叉树的节点个数

• 既然是计算节点的个数，一般我们的思路是，直接顺序遍历树，每遍历一个几点size++。但是既然是前，中，后序的应用，那当然得用分治递归的思路。我们用一张图来清晰的理解以下思路。

• 通过上图的分析，我们不难发现，该题用到的遍历方法是后序。

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

	return BinaryTreeSize(root->_left) + BinaryTreeSize(root->_right) + 1;
1
2
3
4
5
6
7
8

3.2计算二叉树叶子节点的个数

• 这个计算叶子节点的个数和计算树节点的个数非常相似
  

• 通过上图分析，我们可以发现，这题用到的遍历方法是后序

// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}

	if (root->_left == NULL && root->_right == NULL)
		return 1;

	return BinaryTreeLeafSize(root->_left) + 
		BinaryTreeLeafSize(root->_right);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

3.3计算第k层的节点个数

• 计算第k层的节点个数同样的我们可以参考一下计算叶子节点的个数。既然是计算第k层的节点个数，那我们就可以想办法把第k层的节点看成是叶子节点，这样我们就可以很好的利用计算叶子节点个数的方法了。

• 通过上图分析，我们可以发现，这题用到的遍历方法是后序。

int BinaryTreeLevelKSize(BTNode* root, int k)
{
	if (k == 1)
		return 1;
	return BinaryTreeLevelKSize(root->_left, k - 1) + BinaryTreeLevelKSize(root->_right, k - 1);
}
1
2
3
4
5
6

3.4查找二叉树值为x的节点

• 既然要查找x的节点，那避免不了要遍历整棵树。同样的用分治，递归法。
  
• 通过上图分析，我们可以发现，这题用到的遍历方法是前序。

BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
	if (root == NULL)
		return NULL;

	if (root->_data == x)
		return root;

	BTNode* ret = BinaryTreeFind(root->_left, x);
	if (ret)
		return ret;

	ret = BinaryTreeFind(root->_right, x);
	if (ret)
		return ret;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

• 这里大家可以思考一下为什么我们递归的时候要 定义一个BTNode* ret 变量来接收🤔，如果不定义直接 BinaryTreeFind(root->_left, x);会则会么样呢？🤔大家可以自己动手画一画图。