二叉樹非遞歸 后序遍歷
1
#include<iostream>
2
#include<stack>
3
using namespace std;
4
5
struct BinTreeNode{
6
int data;
7
BinTreeNode *left;
8
BinTreeNode *right;
9
};
10
enum tagtype{L,R};
11
struct StackElem{
12
BinTreeNode *ptr;
13
tagtype tag;
14
};
15
16
void PostOrder(BinTreeNode *root){
17
stack<StackElem> s;
18
StackElem x;
19
BinTreeNode *tmp = root;
20
while(tmp!=NULL || !s.empty()){
21
while(tmp != NULL){
22
x.ptr = tmp;
23
x.tag = L;
24
s.push(x);
25
tmp = tmp->next;
26
}
27
while(!s.empty() && s.top().tag == R){
28
cout<<s.top().ptr->data<<' ';
29
s.pop();
30
}
31
if(!s.empty()){
32
s.top().tag = R;
33
tmp = s.top().ptr->right;
34
}
35
}
36
}
#include<iostream>2
#include<stack>3
using namespace std;4

5
struct BinTreeNode{6
int data;7
BinTreeNode *left;8
BinTreeNode *right;9
};10
enum tagtype{L,R};11
struct StackElem{12
BinTreeNode *ptr;13
tagtype tag;14
};15

16
void PostOrder(BinTreeNode *root){17
stack<StackElem> s;18
StackElem x;19
BinTreeNode *tmp = root;20
while(tmp!=NULL || !s.empty()){21
while(tmp != NULL){22
x.ptr = tmp;23
x.tag = L;24
s.push(x);25
tmp = tmp->next;26
}27
while(!s.empty() && s.top().tag == R){28
cout<<s.top().ptr->data<<' ';29
s.pop();30
}31
if(!s.empty()){32
s.top().tag = R;33
tmp = s.top().ptr->right;34
}35
}36
}posted on 2011-08-18 15:32 Hsssssss 閱讀(173) 評論(0) 編輯 收藏 引用 所屬分類: C++代碼



