0%

二叉树的后续遍历(非递归)

读前福利:几百本互联网技术书籍送给大家https://mp.weixin.qq.com/s/dFqVQ2qJxvQ0YrIlPISJuw


二叉树后序遍历

二叉树的遍历方式主要由先序遍历、中序遍历和后续遍历,还后就是层次遍历

感受完前两篇的遍历方式,本节来看看后序遍历

后序遍历过程

a. 先序遍历其左子树

b. 先序遍历其右子树

c. 访问根节点

然后就是一直递归下去,在访问到节点的时候,可以进行节点的相关处理,比如说简单的访问节点值

下图是一棵二叉树,我们来手动模拟一下后序遍历过程


按照上述后序遍历的过程,得到后序遍历序列:

1
H I D E B F G C A

递归实现

二叉树的后序遍历利用上述的递归思想进行C语言代码实现:

树形结构按照上述树形结构进行初始化

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
# include <stdio.h>
# include <string.h>
# include <stdlib.h>
# define ElementType char

//结点结构体
typedef struct BinTNode{
ElementType data;
struct BinTNode * left;
struct BinTNode * right;
}BinTNode, *BinTree;

// 初始化树形结构
BinTNode * CreateBiTree(BinTNode *T){
T=(BinTNode*)malloc(sizeof(BinTNode));
T->data='A';
T->left=(BinTNode*)malloc(sizeof(BinTNode));
T->left->data='B';
T->right=(BinTNode*)malloc(sizeof(BinTNode));
T->right->data='C';

T->left->left=(BinTNode*)malloc(sizeof(BinTNode));
T->left->left->data='D';
T->left->right=(BinTNode*)malloc(sizeof(BinTNode));
T->left->right->data='E';
T->left->right->left=NULL;
T->left->right->right=NULL;
T->left->left->left=(BinTNode*)malloc(sizeof(BinTNode));
T->left->left->left->data='H';
T->left->left->left->left=NULL;
T->left->left->left->right=NULL;
T->left->left->right=(BinTNode*)malloc(sizeof(BinTNode));
T->left->left->right->data='I';
T->left->left->right->left=NULL;
T->left->left->right->right=NULL;

T->right->left=(BinTNode*)malloc(sizeof(BinTNode));
T->right->left->data='F';
T->right->left->left=NULL;
T->right->left->right=NULL;
T->right->right=(BinTNode*)malloc(sizeof(BinTNode));
T->right->right->data='G';
T->right->right->left=NULL;
T->right->right->right=NULL;

return T;
}

// 遍历过程中,输出节点值
void printElement(BinTNode * T){
printf("%c ",T->data);
}

//先序遍历
void PostOrderTraverse(BinTNode * T){
if (T) {
PostOrderTraverse(T->left); //递归访问左孩子
PostOrderTraverse(T->right); //递归访问右孩子
printElement(T); //输出节点值
}
// 当节点为空的时候,返回
return;
}

int main() {
BinTNode * Tree;
Tree = CreateBiTree(Tree); // 初始化树形结构
printf("后序遍历: ");
PostOrderTraverse(Tree); // 先序递归进行
printf("\n"); // 最后换行
return 0;
}

运行结果:

1
后序遍历: H I D E B F G C A

非递归实现

相比于之前的先序遍历和中序遍历非递归实现,后序遍历的非递归算法与之前有所不同,后续遍历需要先访问左右子结点后,才能访问该结点,而这也是非递归的难点所在。

考虑了几种实现的方案,这里我给出我认为比较清晰的一个方案供大家参考:借助两个栈(S1和S2)来进行操作

看下面伪代码:

1
2
3
4
5
6
7
8
初始化S1的top元素是树的根结点;
while(top1 != -1) {
将栈顶元素push到S2;
if(栈顶元素有孩子结点){
按照孩子结点的左右顺序push进S1;
}
}
循环逐个弹出S2的栈顶元素

伪代码可能看了之后有些不太好懂,但是还算看着清晰吧,下面借助图,一定会思路清晰的(长图发放):


有了这个思路就应该会很清晰了,下面按照上述思路用C语言实现:

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
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define ElementType char
int top_S1 = -1; //定义栈S1 top下标
int top_S2 = -1; //定义栈S2 top下标

// 结点结构体
typedef struct BinTNode{
ElementType data;
struct BinTNode * left;
struct BinTNode * right;
}BinTNode, *BinTree;

// 初始化树形结构
BinTNode * CreateBiTree(BinTNode *T) {
T=(BinTNode*)malloc(sizeof(BinTNode));
T->data='A';
T->left=(BinTNode*)malloc(sizeof(BinTNode));
T->left->data='B';
T->right=(BinTNode*)malloc(sizeof(BinTNode));
T->right->data='C';

T->left->left=(BinTNode*)malloc(sizeof(BinTNode));
T->left->left->data='D';
T->left->right=(BinTNode*)malloc(sizeof(BinTNode));
T->left->right->data='E';
T->left->right->left=NULL;
T->left->right->right=NULL;
T->left->left->left=(BinTNode*)malloc(sizeof(BinTNode));
T->left->left->left->data='H';
T->left->left->left->left=NULL;
T->left->left->left->right=NULL;
T->left->left->right=(BinTNode*)malloc(sizeof(BinTNode));
T->left->left->right->data='I';
T->left->left->right->left=NULL;
T->left->left->right->right=NULL;

T->right->left=(BinTNode*)malloc(sizeof(BinTNode));
T->right->left->data='F';
T->right->left->left=NULL;
T->right->left->right=NULL;
T->right->right=(BinTNode*)malloc(sizeof(BinTNode));
T->right->right->data='G';
T->right->right->left=NULL;
T->right->right->right=NULL;

return T;
}

// 栈S1 - 进栈push
void push_S1(BinTNode** stack,BinTNode * elem) {
stack[++top_S1] = elem;
}

// 栈S2 - 进栈push
void push_S2(BinTNode** stack,BinTNode * elem) {
stack[++top_S2] = elem;
}

//栈S1 - 弹栈pop
void pop_S1(){
if (top_S1 == -1) {
return ;
}
top_S1--;
}

//栈S2 - 弹栈pop
void pop_S2(){
if (top_S2 == -1) {
return ;
}
top_S2--;
}

// 遍历过程中,输出结点值
void printElement(BinTNode* elem) {
printf("%c ",elem->data);
}

//获取栈顶元素
BinTNode * getTop_S1(BinTNode** stack){
return stack[top_S1];
}

//获取栈顶元素
BinTNode * getTop_S2(BinTNode** stack){
return stack[top_S2];
}

//非递归遍历 - 左右根
void PostOrderTraverse(BinTNode * Tree) {
BinTNode * S1[30]; // 辅助栈
BinTNode * S2[30];
BinTNode * T = Tree; // 定义临时指针
BinTNode * Temp;
push_S1(S1, T); // 初始化S1的top元素是树的根结点
while(top_S1 != -1) {
T = getTop_S1(S1); // S1的栈顶元素弹出
pop_S1(); // 栈顶元素弹栈
push_S2(S2, T);

if(T->left != NULL || T->right != NULL) { // 栈顶元素有孩子结点
if(T->left != NULL)
push_S1(S1, T->left);
if(T->right != NULL)
push_S1(S1, T->right);
}
}
// 逐个弹出S2的元素
while(top_S2 != -1) {
printElement(getTop_S2(S2));
pop_S2();
}
}

int main() {
BinTNode * Tree;
Tree = CreateBiTree(Tree);
printf("看到这样就对了: H I D E B F G C A\n");
printf("后序遍历:\t");
PostOrderTraverse(Tree);
printf("\n");
return 0;
}

运行结果

1
2
看到这样就对了: H D I B E A F C G
中序遍历: H D I B E A F C G

最后

在这里给大家准备了几百本的互联网技术类书籍,需要的来下载吧!点击获取
有任何问题,欢迎随时交流!!!

------ 全文结束------