二叉树后序遍历的非递归算法(C语言)(转)
这篇随笔开启我的博客进程，成为万千程序员中的一员，坚持走到更远！
折磨了我一下午的后序遍历中午得到解决，关键在于标记右子树是否被访问过，考虑过修改二叉树结点的数据结构，增加一个visit域，或者建一个栈存储已访问的结点。都比较麻烦没有调试成功。若将右子树也入栈，如果没有访问标记的话，会改变访问的次序，甚至出现死循环，这是比较危险的情况。从借鉴的博文里，摘录并改写为C的代码，基本上没有改动。后续问题努力写出自己的原创代码。
二叉树存储的数据类型为int型，用数字0表示子树为空
输入：1 2 3 0 8 0 0 4 0 0 5 6 0 0 7 0 0
得到后序遍历结果：83426751
1
#include <stdio.h>
2
#include <stdlib.h>
3
4
#define
OK 1
5
#define
ERROR 0
6
#define
MaxSize 100
7
8
typedef
int ElemType;
9
typedef
int Status;
10
11
typedef
struct BTNode{
12
ElemType data;
13
struct
BTNode *lchild,*
rchild;
14
}BTree;
15
16
typedef
struct St{
17
struct
BTNode*
data[MaxSize];
18
int top;
19
}Stack;
20
//1.按先序次序生成二叉树
21
BTree*
CreateT(){
22
BTree *
BT;
23
ElemType ch;
24
scanf(
"%d"
,&
ch);
25
if
(ch==
0)
26
BT=
NULL;
27
else{
28
BT=(BTree*)malloc(
sizeof(BTree));
29
if
(!
BT){exit(OVERFLOW);}
30
BT->data=
ch;
31
BT->lchild=
CreateT();
32
BT->rchild=
CreateT();
33
}
34
return BT;
35
}
36
37
//4.后序遍历
38
Status PostOrder(BTree *
BT) {
39
if(BT){
40
PostOrder(BT->
lchild);
41
PostOrder(BT->
rchild);
42
printf(
"%3d"
,BT->
data);
43
return OK;
44
}
45
else
return ERROR;
46
}
47
//4.后序遍历-非递归
48
Status PostOrder2(BTree *
BT) {
49
Stack s,s2;
50
BTree *
T;
51
int flag[MaxSize];
52
s.top=
0;
53
T=
BT;
54
while
(s.top!=
0
||
T){
55
while(T)
56
{
57
s.data[s.top++]=
T;
58
flag[s.top-
1
]=
0;
59
T=T->
lchild;
60
}
61
while
(s.top!=
0
&&flag[s.top-
1
]==
1){
62
T=s.data[--
s.top];
63
printf(
"%3d"
,T->
data);
64
}
65
if
(s.top!=
0){
66
flag[s.top-
1
]=
1;
67
T=s.data[s.top-
1];
68
T=T->
rchild;
69
}
70
else
break;
71
}
72
return OK;
73
}
74
int main(){
75
BTree *
BT;
76
BT=
CreateT();
77
if(PostOrder(BT)){
78
printf(
"\n后序遍历完成！\n");
79
}
80
if(PostOrder2(BT)){
81
printf(
"\n非递归后序遍历完成！\n");
82
}
83
}