二叉树的遍历

发表于   |   分类于

本文介绍二叉树的先、中、后序遍历。

一、先序遍历

理解语句执行顺序

无论是哪种遍历方式，都是从一个节点出发。

先序遍历就是从一个节点出发，首先打印当前节点（也就是访问当前节点），如果当前节点有左子树，就访问左子树，如果没有左子树就去访问右子树，如果右子树也没有就返回。

访问左右子树的方式和之前一样，先打印（访问）当前节点，然后访问左右子树。

调用一个函数就会在栈顶分配一块内存，函数里面在调用其他函数会继续在栈顶分配内存，而且执行的永远是在栈顶的那个函数，栈顶的执行完毕之后就是释放当前的内存，执行到下一个函数。

假设现在从根节点开始先序遍历，首先访问根节点，然后是访问左右子树，访问右子树之前会先访问左子树。尽管访问左子树和右子树的两条语句很近，但实际上访问左子树的时候在栈顶分配了内存，然后访问左子树的左子树又分配内存（别忘了执行的永远是栈顶这个函数），即便是释放栈顶的内存之后，也是轮到左子树的右子树…再然后才是访问到右子树。

所以说理解了函数调用的方式，就会知道先序遍历究竟是怎么执行的。

构造一个树

已经忘记书上是怎么写的了，我的写法可能比较笨。

先定义结构体，每个节点由左右指针域和数据域组成。

1
2
3
4
5
6
typedef struct node
{
	struct node * left_ptr;
	struct node * right_ptr;
	char ch;
}Tree, *PTree;

然后创建节点并把节点连起来。（这里只是列举一部分代码）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
PTree one_1 = malloc(sizeof(Tree));
PTree two_1 = malloc(sizeof(Tree));
PTree two_2 = malloc(sizeof(Tree));
PTree thr_1 = malloc(sizeof(Tree));
PTree thr_2 = malloc(sizeof(Tree));
PTree thr_3 = malloc(sizeof(Tree));
PTree thr_4 = malloc(sizeof(Tree));

one_1->ch = 'A';
one_1->left_ptr = two_1;
one_1->right_ptr = two_2;

two_1->ch = 'B';
two_1->left_ptr = thr_1;
two_1->right_ptr = thr_2;
......

先序遍历二叉树

  • 先序遍历的顺序
    1. 先访问根节点
    2. 再访问左子树
    3. 再访问右子树

遍历二叉树要从一个节点开始，所以函数的形参是一个节点的指针。

具体的做法是，访问当前节点，判断是否有左子树，有的话就访问左子树（也就是递归调用这个函数，把左子树的地址作为形参传递过去）。再判断有无右子树，与左子树同理。

具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void XianXuBianLi(PTree tree)
{
	printf("%c ", tree->ch);

	if(tree->left_ptr != NULL)
	{
		XianXuBianLi(tree->left_ptr);
	}

	if(tree->right_ptr != NULL)
	{
		XianXuBianLi(tree->right_ptr);
	}

	return;
}

完整代码

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
#include <stdio.h>
#include <malloc.h>

typedef struct node
{
	struct node * left_ptr;
	struct node * right_ptr;
	char ch;
}Tree, *PTree;

void XianXuBianLi(PTree);

int main(void)
{

	PTree one_1 = malloc(sizeof(Tree));
	PTree two_1 = malloc(sizeof(Tree));
	PTree two_2 = malloc(sizeof(Tree));
	PTree thr_1 = malloc(sizeof(Tree));
	PTree thr_2 = malloc(sizeof(Tree));
	PTree thr_3 = malloc(sizeof(Tree));
	PTree thr_4 = malloc(sizeof(Tree));

	one_1->ch = 'A';
	one_1->left_ptr = two_1;
	one_1->right_ptr = two_2;

	two_1->ch = 'B';
	two_1->left_ptr = thr_1;
	two_1->right_ptr = thr_2;

	two_2->ch = 'C';
	two_2->left_ptr = thr_3;
	two_2->right_ptr = thr_4;

	thr_1->ch = 'D';
	thr_1->left_ptr = NULL;
	thr_1->right_ptr = NULL;

	thr_2->ch = 'E';
	thr_2->left_ptr = NULL;
	thr_2->right_ptr = NULL;

	thr_3->ch = 'F';
	thr_3->left_ptr = NULL;
	thr_3->right_ptr = NULL;

	thr_4->ch = 'G';
	thr_4->left_ptr = NULL;
	thr_4->right_ptr = NULL;

	XianXuBianLi(one_1);

	return 0;
}

void XianXuBianLi(PTree tree)
{
	printf("%c ", tree->ch);
	if(tree->left_ptr != NULL)
	{
		XianXuBianLi(tree->left_ptr);
	}
	if(tree->right_ptr != NULL)
	{
		XianXuBianLi(tree->right_ptr);
	}

	return;
}

输出结果

1
A B D E C F G Press any key to continue

二、中序遍历

中序遍历和先序遍历无非就是访问根节点的时机不同罢了。

  • 中序遍历的顺序
    1. 先访问左子树
    2. 再访问根节点
    3. 再访问右子树

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void ZhongXuBianLi(PTree tree)
{
	if(tree->left_ptr != NULL)
	{
		XianXuBianLi(tree->left_ptr);
	}

	printf("%c ", tree->ch);

	if(tree->right_ptr != NULL)
	{
		XianXuBianLi(tree->right_ptr);
	}

	return;
}

输出结果

1
D B E A F C G Press any key to continue

三、后序遍历

  • 后序遍历的顺序
    1. 先访问左子树
    2. 再访问右子树
    3. 再访问根节点

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void HouXuBianLi(PTree tree)
{
	if(tree->left_ptr != NULL)
	{
		XianXuBianLi(tree->left_ptr);
	}

	if(tree->right_ptr != NULL)
	{
		XianXuBianLi(tree->right_ptr);
	}

    printf("%c ", tree->ch);

	return;
}

输出结果

1
D E B F G C A Press any key to continue