本文实例为大家分享了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
|
#include<stdio.h>
#include<stdlib.h>
typedef struct TreeNode{
char element;
struct TreeNode *left,*right;
}Tree,*BTree;
typedef struct StackNode{
BTree data;
struct StackNode *next;
}Stack,*PStack;
typedef struct {
PStack top;
}LinkStack,*PLinkStack;
//初始化空栈
PLinkStack Init_Stack( void ){
PLinkStack S;
S=(PLinkStack) malloc ( sizeof (LinkStack));
if (S){
S->top=NULL;
}
return S;
}
//压栈
void Push_Stack(PLinkStack S,BTree T){
PStack p;
p=(PStack) malloc ( sizeof (Stack));
p->data=T;
p->next=S->top;
S->top=p;
}
//判空
int empty_Stack(PLinkStack S){
if (S->top){
return 0;
} else {
return 1;
}
}
//出栈
PStack Pop_Stack(PLinkStack S){
PStack q;
if (empty_Stack(S)){
return S->top;
} else {
q=S->top;
S->top=S->top->next;
}
return q;
}
//销毁栈
void DestroyStack(PLinkStack S){
PStack del;
while (S->top!=NULL){
del=S->top;
S->top=S->top->next;
free (del);
}
free (S);
}
BTree BuildTree( void ){
char ch;
BTree node;
ch= getchar ();
if (ch== '#' ){
node=NULL;
} else {
node=(BTree) malloc ( sizeof (Tree));
node->element=ch;
node->left=BuildTree();
node->right=BuildTree();
}
return node;
}
void NotRecursionPostOrder(BTree T){
PLinkStack S,CS;
S=Init_Stack();
CS=Init_Stack();
while (T || !empty_Stack(S)){
if (T){
Push_Stack(S,T);
Push_Stack(CS,T);
T=T->right;
} else {
T=Pop_Stack(S)->data;
T=T->left;
}
}
while (CS->top!=NULL){
printf ( "%c" ,CS->top->data->element);
CS->top=CS->top->next;
}
DestroyStack(CS);
}
int main( void ){
BTree T;
T=BuildTree();
NotRecursionPostOrder(T);
return 0;
}
|
法二:实现思路。按先序遍历访问每一个结点。存入栈中,当为空时,就出立即栈(第一次出栈)。出栈后应该立即进栈,去访问进栈结点的右结点,这样可以保证先输出左、右结点,再输出根结点。二次进栈利用flag标记。
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
|
#include<stdio.h>
#include<stdlib.h>
typedef struct TreeNode {
char element;
int flag;
struct TreeNode *left, *right;
}Tree, *BTree;
typedef struct StackNode {
BTree data;
struct StackNode *next;
}Stack, *PStack;
typedef struct {
PStack top;
}LinkStack, *PLinkStack;
//初始化空栈
PLinkStack Init_Stack( void ) {
PLinkStack S = (PLinkStack) malloc ( sizeof (LinkStack));
if (S) {
S->top = NULL;
}
return S;
}
//压栈
void Push_Stack(PLinkStack S, BTree T) {
PStack p;
p = (PStack) malloc ( sizeof (Stack));
p->data = T;
p->next = S->top;
S->top = p;
}
//判空
int empty_Stack(PLinkStack S) {
if (S->top) {
return 0;
}
else {
return 1;
}
}
//出栈
PStack Pop_Stack(PLinkStack S) {
PStack q = S->top;
S->top = S->top->next;
return q;
}
BTree BuildTree( void ) {
BTree t;
char ch;
ch = getchar ();
if (ch == '#' ) {
t = NULL;
}
else {
t = (BTree) malloc ( sizeof (Tree));
t->element = ch;
t->left = BuildTree();
t->right = BuildTree();
}
return t;
}
void DestroyStack(PLinkStack S){
PStack p;
while (S->top){
p=S->top;
free (p);
S->top=S->top->next;
}
}
void NotRecursionPostOrder(BTree T) {
PLinkStack S;
S = Init_Stack();
while (T || !empty_Stack(S)) {
if (T) {
T->flag = 0;
Push_Stack(S, T);
T = T->left;
}
else {
T = Pop_Stack(S)->data;
if (T->flag == 0) {
T->flag = 1;
Push_Stack(S, T);
T = T->right;
}
else {
if (T->flag == 1) {
printf ( "%c" , T->element);
T = NULL;
}
}
}
}
DestroyStack(S); //销毁栈
}
int main( void ) {
BTree T;
T = BuildTree();
NotRecursionPostOrder(T);
return 0;
}
|
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持服务器之家。
原文链接:http://blog.csdn.net/chendongqaq/article/details/70832303