【数据结构】二叉树的遍历：前序，中序，后序的递归结构遍历
【数据结构】二叉树的遍历：前序，中序，后序的递归结构遍历文章目录
前言
1.二叉树的遍历方式
2.二叉树的遍历及相关函数（代码实现）
2.1前序/中序/后序的遍历
2.2计算二叉树的大小
2.3计算二叉树叶子结点的个数
2.4计算二叉树的高度
2.5计算第K层结点的个数
2.6二叉树查找
前言
在学习二叉树的遍历之前，我们需要先创建一棵二叉树，然后才能学习其相关的基本操作，由于现在我们对二叉树结构的掌握还在初阶部分，为了降低大家的学习成本，我们先手动快速创建一棵简单的二叉树，快速进入二叉树的操作学习，这个方法在我们调试程序代码的时候，也非常适用。等二叉树结构了解的差不多时，我们再继续研究二叉树真正的创建方式。
1.二叉树的遍历方式
按照规则，二叉树的遍历有：前序/中序/后序的递归结构遍历访问顺序：
1. 前序遍历（先序，先根):根——左子树——右子树
2. 中序遍历（中根）：左子树——根——右子树
3. 后序遍历（后根）：左子树——右子树——根
2.二叉树的遍历及相关函数（代码实现）
思路：分而治之
1.首先我们要用简单的方式先创建出一棵二叉树，并赋予数据；
2.采用递归的方式，分别实现前序/中序/后序遍历这棵二叉树；
3.尝试计算这个二叉树的大小（利用递归）；
4.尝试计算叶子结点的个数（利用递归）；
5.尝试计算二叉树的高度（利用递归）；
6.尝试写出计算第K层结点的个数的函数（利用递归）；
7.尝试写出二叉树查找的函数（利用递归）。
2.1前序/中序/后序的遍历
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
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;
}
————————————————
版权声明：本文为CSDN博主「SouLinya」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/weixin_63449996/article/details/126841212
页:
[1]