#include <iostream>
#include <stack>
#include <map>
using namespace std;
struct Node {
int v;
Node *lchild;
Node *rchild;
};
struct StackNode {
Node *ptr;
int flag; // 1 means the right sub-tree has been travelled
};
void visit(Node *p)
{
cout << p->v << ' ';
}
void preorder_travel(Node *root)
{
if(root == NULL)
return;
stack<Node*> s;
Node *p = root;
while (p || !s.empty())
{
while (p)
{
s.push(p);
visit(p);
p = p->lchild;
}
if (!s.empty())
{
p = s.top();
s.pop();
p = p->rchild;
}
}
}
void inorder_travel(Node *root)
{
if(root == NULL)
return;
stack<Node*> s;
Node *p = root;
while (p || !s.empty())
{
while (p)
{
s.push(p);
p = p->lchild;
}
if (!s.empty())
{
p = s.top();
s.pop();
visit(p);
p = p->rchild;
}
}
}
void postorder_travel(Node *root)
{
if(root == NULL)
return;
stack<StackNode> s;
StackNode x;
Node *p = root;
while (p || !s.empty())
{
while (p)
{
x.ptr = p;
x.flag = 0;
s.push(x);
p = p->lchild;
}
while (!s.empty() && s.top().flag)
{
visit(s.top().ptr);
s.pop();
}
if (!s.empty())
{
s.top().flag = 1;
p = s.top().ptr->rchild;
}
}
}
int main()
{
int i, j;
map<int, Node*> m;
int a[][3] = {
{1,2,3},
{2,4,5},
{3,6,7},
{4,-1,-1},
{5,-1,-1},
{6,8,-1},
{7,-1,9},
{8,-1,-1},
{9,-1,-1},
-1
};
for (i=0; a[i][0]!=-1; i++) {
Node *n = new Node;
n->v = a[i][0];
m[n->v] = n;
}
for (i=0; a[i][0]!=-1; i++) {
int s = a[i][0];
int l = a[i][1];
int r = a[i][2];
Node *n = m[s];
n->lchild = (l==-1 ? NULL : m[l]);
n->rchild = (r==-1 ? NULL : m[r]);
}
Node *root = m[a[0][0]];
preorder_travel(root);
cout << endl;
inorder_travel(root);
cout << endl;
postorder_travel(root);
cout << endl;
return 0;
}