【数据结构】二叉树的遍历：前序，中序，后序的递归结构遍历

---

前言

在学习二叉树的遍历之前，我们需要先创建一棵二叉树，然后才能学习其相关的基本操作，由于现在我们对二叉树结构的掌握还在初阶部分，为了降低大家的学习成本，我们先手动快速创建一棵简单的二叉树，快速进入二叉树的操作学习，这个方法在我们调试程序代码的时候，也非常适用。等二叉树结构了解的差不多时，我们再继续研究二叉树真正的创建方式。

1.二叉树的遍历方式

按照规则，二叉树的遍历有：前序/中序/后序的递归结构遍历访问顺序：

1. 前序遍历（先序，先根):根——左子树——右子树

2. 中序遍历（中根）：左子树——根——右子树

3. 后序遍历（后根）：左子树——右子树——根

2.二叉树的遍历及相关函数（代码实现）

思路：分而治之
1.首先我们要用简单的方式先创建出一棵二叉树，并赋予数据；
2.采用递归的方式，分别实现前序/中序/后序遍历这棵二叉树；
3.尝试计算这个二叉树的大小（利用递归）；
4.尝试计算叶子结点的个数（利用递归）；
5.尝试计算二叉树的高度（利用递归）；
6.尝试写出计算第K层结点的个数的函数（利用递归）；
7.尝试写出二叉树查找的函数（利用递归）。

2.1前序/中序/后序的遍历

#define _CRT_SECURE_NO_WARNINGS 1
#include
#include
#include

typedef int BTDataType;

//定义二叉树结点的结构体
typedef struct BinaryTreeNode
{
	BTDataType data;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
}BTNode;

//前序遍历
void PreOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	printf("%d ", root->data);
	PreOrder(root->left);
	PreOrder(root->right);
}
//中序遍历
void InOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	InOrder(root->left);
	printf("%d ", root->data);
	InOrder(root->right);
}
//后序遍历
void PostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	PostOrder(root->left);
	PostOrder(root->right);
	printf("%d ", root->data);
}
//先创建一个简单的二叉树结构
BTNode* CreateTree()
{
	//先动态开辟6个结点的空间
	BTNode* n1 = (BTNode*)malloc(sizeof(BTNode));
	assert(n1);
	BTNode* n2 = (BTNode*)malloc(sizeof(BTNode));
	assert(n2);
	BTNode* n3 = (BTNode*)malloc(sizeof(BTNode));
	assert(n3);
	BTNode* n4 = (BTNode*)malloc(sizeof(BTNode));
	assert(n4);
	BTNode* n5 = (BTNode*)malloc(sizeof(BTNode));
	assert(n5);
	BTNode* n6 = (BTNode*)malloc(sizeof(BTNode));
	assert(n6);

	n1->data = 1;
	n2->data = 2;
	n3->data = 3;
	n4->data = 4;
	n5->data = 5;
	n6->data = 6;

	n1->left = n2;
	n1->right = n4;
	n2->left = n3;
	n2->right = NULL;
	n3->left = NULL;
	n3->right = NULL;
	n4->left = n5;
	n4->right = n6;
	n5->left = NULL;
	n5->right = NULL;
	n6->left = NULL;
	n6->right = NULL;

	return n1;
}

int main()
{
	//先创建一个简单的二叉树结构
	BTNode* root = CreateTree();

	//二叉树前序遍历
	printf("二叉树前序遍历:");
	PreOrder(root);
	printf("\n");
	//二叉树中序遍历
	printf("二叉树中序序遍历:");
	InOrder(root);
	printf("\n");
	//二叉树后序遍历
	printf("二叉树后序遍历:");
	PostOrder(root);
	printf("\n");

	return 0;
}
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111

测试结果：

2.2计算二叉树的大小

时间复杂度为O(N)

//二叉树的大小
//法一：全局变量
//int count = 0;
//void TreeSize(BTNode* root)
//{
//	if (root == NULL)
//	{
//		return;
//	}
//	count++;
//	TreeSize(root->left);
//	TreeSize(root->right);
//
//	return;//函数栈帧层层返回，最后回到根节点1，结束了1的右子树函数，什么都不返回，因为count是全局变量
//}
//法二：子问题思路：分而治之
int TreeSize(BTNode* root)
{
	return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

2.3计算二叉树叶子结点的个数

//计算二叉树叶子结点的个数
int TreeLeafSize(BTNode* root)
{
	if (root == NULL)//首先得考虑空树的情况,0个叶子结点
	{
		return 0;
	}
	//叶子结点的特征就是左右子树为空
	if (root->left == NULL && root->right == NULL)
	{
		return 1;
	}
	return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

2.4计算二叉树的高度

int TreeHeight(BTNode* root)
{
	//空树高度为0
	if (root == NULL)
	{
		return 0;
	}
	//树的高度是较高的那棵子树
	int lh = TreeHeight(root->left);//左子树的高度
	int rh = TreeHeight(root->right);//右子树的高度

	return lh > rh ? lh + 1 : rh + 1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

2.5计算第K层结点的个数

求第K层的结点个数，转换成求子树第K-1层的结点个数。举个栗子：如果我们要求这棵二叉树第3层的结点个数（为3），就转换成求左子树根结点2的第2层的结点个数+右子树4第二层的结点个数。。。

//计算第K层结点的个数
int TreeLevel(BTNode* root,int K)
{
	assert(K > 0);
	if (root == NULL)
	{
		return 0;
	}
	//如果是第一层(递归出口)
	if (K == 1)
	{
		return 1;
	}
	//转换成子树的第K-1层
	return TreeLevel(root->left,K-1) + TreeLevel(root->right,K-1);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

2.6二叉树查找

//二叉树查找
BTNode* TreeFind(BTNode* root, BTDataType data)
{
	if (root == NULL)
	{
		return NULL;
	}
	if (root->data == data)
	{
		return root;
	}
	//先查找左子树
	BTNode* lret = TreeFind(root->left, data);
	if (lret)
		return lret;
	//再查找右子树
	BTNode* rret = TreeFind(root->right, data);
	if (rret)
		return rret;
	return NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

3.二叉树的深度与广度优先遍历

二叉树的深度优先遍历：前序，中序，后序
二叉树的广度优先遍历：后序