二叉树的创建与三种遍历方式（带图文详解）_二叉树的三种遍历例题带图

二叉树是由多节点组成的，每个节点最多链接两个节点，这两个节点就称为根节点的左树和右树。
每个节点的由数据区，左树，右树组成。

typedef struct node {
	int data;
	struct node *left;
	struct node *right;
}Node, *Tree;
1
2
3
4
5

二叉树的创建
从键盘中输入值，构成二叉树。

Tree create_tree(void)
{
	Tree root;

	int a;
	scanf("%d", &a);
	if (a == 0) {  //当输入0时，结束
		root = NULL;
		return;
	}
	else {
		root = (Tree)malloc(sizeof(Node));
		root->data = a;
		root->left = create_tree();
		root->right = create_tree();
	}
	
	return root;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

二叉树遍历的三种方法
二叉树有三种遍历方法，前序遍历（preorder）、中序遍历（inorder）、后续遍历（postorder）,
前序遍历：先访问根节点，再遍历左子树，再遍历右子树（根->左->右）。
借用《大话数据结构中的图》
顺序为 ABDGHCEIF

用代码进行实现

void preorder(Tree root)
{
	if (root != NULL) {
		printf("data is %d\n", root->data);
		preorder(root->left);
		preorder(root->right);
	}
}
1
2
3
4
5
6
7
8

中序遍历：先遍历左子树，再遍历根节点，最后遍历右子树（左->根->右）。
顺序为GDHBAEICF

用代码进行实现

void inorder(Tree root)
{
	if (root != NULL) {
		inorder(root->left);
		printf("data is %d\n",root->data);
		inorder(root->right);
	}
}
1
2
3
4
5
6
7
8

后续遍历：先访问左子树，再访问右子树，最后访问根（左->右->根）。
顺序为：GHDBIEFCA

用代码进行实现

void postorder(Tree root)
{
	if (root != NULL) {
		postorder(root->left);
		postorder(root->right);
		printf("data is %d\n",root->data);
	}
}
1
2
3
4
5
6
7
8

总的代码

#include <stdio.h>
#include <stdlib.h>

typedef struct node {
	int data;
	struct node *left;
	struct node *right;
}Node, *Tree;

Tree create_tree(void)
{
	Tree root;

	int a;
	scanf("%d", &a);
	if (a == 0) {
		root = NULL;
		return;
	}
	else {
		root = (Tree)malloc(sizeof(Node));
		root->data = a;
		root->left = create_tree();
		root->right = create_tree();
	}
	
	return root;
}

void preorder(Tree root)
{
	if (root != NULL) {
		printf("data is %d\n", root->data);
		preorder(root->left);
		preorder(root->right);
	}
}

void inorder(Tree root)
{
	if (root != NULL) {
		inorder(root->left);
		printf("data is %d\n",root->data);
		inorder(root->right);
	}
}

void postorder(Tree root)
{
	if (root != NULL) {
		postorder(root->left);
		postorder(root->right);
		printf("data is %d\n",root->data);
	}
}

int main(int argc, char **argv)
{
	Tree root;
	root = create_tree();
	printf("preorder:\n");
	preorder(root);
	printf("inorder:\n");
	inorder(root);
	printf("postorder:\n");
	postorder(root);
	
	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