C语言创建二叉树以及三种遍历详解（你一定能看明白的超简单代码）

1.二叉树的创建

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
//创建结构体
typedef struct TreeNode {
	int data;//数据域
	struct TreeNode* left;//指向当前结点左子树的指针
	struct TreeNode* right;//指向当前结点右子树的指针
}TreeNode;
1
2
3
4
5
6
7
8
9

这里我采取的是链式存储

有了树的数据结构，我们就可以来定义数的每个结点了，并且给每个结点进行赋值操作，以下代码均在main函数中书写

TreeNode n1;
	TreeNode n2;
	TreeNode n3;
	TreeNode n4;
	n1.data = 1;
	n2.data = 3;
	n3.data = 5;
	n4.data = 7;
1
2
3
4
5
6
7
8

此时的结点状态如图所示

每个节点都是独立的存在，我们需要利用上述定义的指针进行连接（大家想怎么连接就怎么连接，毕竟喜欢的对象要自己挑）

	n1.left = &n2;
	n1.right = &n3;
	n2.left = &n4;
	n2.right = NULL;
	n3.left = NULL;
	n3.right = NULL;
	n4.left = NULL;
	n4.right = NULL;
1
2
3
4
5
6
7
8

连接完成后，就变成了这个亚子

注意两个问题
1.n1.left指向n3的地址，原因何在？

left是个指针哇，指的可不就是地址嘛，指个结点，那直接重开吧
2.为啥有的指针没有左右子节点还要指向NULL呢？
其实这个主要是体现代码的严谨，指针如果啥都不指，有时候是会出问题的
也就是咋们俗称的野指针

三种遍历

1.先序遍历（根左右）
其实就是先遍历根节点，在遍历左子树，最后遍历右子树

中序遍历（左根右）
先找到最左的结点，依次往上找例如左： 7 根： 3 右：9，接下来把在7 3 9作为1的左也就是左：7 3 9 根： 1 右： 5
后续遍历（左右根）
先找到最左的结点，依次往上找例如左： 7 右： 9 根：3，接下来把在7 9 3作为1的左也就是左：7 9 3 右： 5 根： 1

//先序遍历
PreOrder(TreeNode* T) {
	//递归条件
	if (T == NULL)
		return;
	else {
		//先处理根节点
		printf("%d ", T->data);
		//当前结点的左子树也是树，同样可以使用先序遍历，故左递归
		PreOrder(T->left);
		//当前结点的右子树也是树，同样可以使用先序遍历，故右递归
		PreOrder(T->right);
	}
}

//中序遍历
InOrder(TreeNode* T) {
	//递归条件
	if (T == NULL)
		return;
	else {
		//当前结点的左子树也是树，同样可以使用中序遍历，故左递归
		InOrder(T->left);
		//处理根节点
		printf("%d ", T->data);
		//当前结点的右子树也是树，同样可以使用中序遍历，故右递归
		InOrder(T->right);
	}
}

//后序遍历
PostOrder(TreeNode* T) {
	//递归条件
	if (T == NULL)
		return;
	else {
		//当前结点的左子树也是树，同样可以使用后序遍历，故左递归
		PostOrder(T->left);
		//当前结点的右子树也是树，同样可以使用后序遍历，故右递归
		PostOrder(T->right);
		//处理根节点
		printf("%d ", T->data);
	}
}
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

三者大体相同，就是执行的顺序不一致
如何理解递归，以及递归的实际运用有哪些，我们下回分解
附上全部代码

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
//创建结构体
typedef struct TreeNode {
	int data;//数据域
	struct TreeNode* left;//指向当前结点左子树的指针
	struct TreeNode* right;//指向当前结点右子树的指针
}TreeNode;

//先序遍历
PreOrder(TreeNode* T) {
	//递归条件
	if (T == NULL)
		return;
	else {
		//先处理根节点
		printf("%d ", T->data);
		//当前结点的左子树也是树，同样可以使用先序遍历，故左递归
		PreOrder(T->left);
		//当前结点的右子树也是树，同样可以使用先序遍历，故右递归
		PreOrder(T->right);
	}
}

//中序遍历
InOrder(TreeNode* T) {
	//递归条件
	if (T == NULL)
		return;
	else {
		//当前结点的左子树也是树，同样可以使用中序遍历，故左递归
		InOrder(T->left);
		//处理根节点
		printf("%d ", T->data);
		//当前结点的右子树也是树，同样可以使用中序遍历，故右递归
		InOrder(T->right);
	}
}

//后序遍历
PostOrder(TreeNode* T) {
	//递归条件
	if (T == NULL)
		return;
	else {
		//当前结点的左子树也是树，同样可以使用后序遍历，故左递归
		PostOrder(T->left);
		//当前结点的右子树也是树，同样可以使用后序遍历，故右递归
		PostOrder(T->right);
		//处理根节点
		printf("%d ", T->data);
	}
}
int main() {
	TreeNode n1;
	TreeNode n2;
	TreeNode n3;
	TreeNode n4;
	n1.data = 1;
	n2.data = 3;
	n3.data = 5;
	n4.data = 7;
	n1.left = &n2;
	n1.right = &n3;
	n2.left = &n4;
	n2.right = NULL;
	n3.left = NULL;
	n3.right = NULL;
	n4.left = NULL;
	n4.right = NULL;
	printf("先序遍历为：");
	PreOrder(&n1);
	printf("\n");
	printf("中序遍历为：");
	InOrder(&n1);
	printf("\n");
	printf("后序遍历为：");
	PostOrder(&n1);
	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