#include<iostream>
#include<queue>
#include<stack>
using namespace std;
typedef struct tree {
char data;
tree* lchild;
tree* rchild;
}tree;
//递归实现创建树
void creatTree(tree*& root)
{
char ch;
cin >> ch;
if (ch == '0')
{
root = NULL;
}
else {
root = new tree;
root->data = ch;
creatTree(root->lchild);
creatTree(root->rchild);
}
}
//树的前中后序 非递归遍历
//前序遍历 根左右
void front_print(tree* root)
{
stack<tree*> l;
l.push(root);
while (!l.empty())
{
tree* tmp = l.top();
cout << tmp->data;
if (tmp->lchild)
{
l.push(tmp->lchild);
}
else {
l.pop();
if (!l.empty())
{
tree* tmp = l.top();
l.pop();
if (tmp->rchild)
{
l.push(tmp->rchild);
}
}
}
}
}
//中序遍历 左根右
void mid_print(tree* root)
{
stack<tree*> l;
l.push(root);
while (!l.empty())
{
tree* tmp = l.top();
if (tmp->lchild)
l.push(tmp->lchild);
else {
cout << tmp->data;
l.pop();
if (!l.empty())
{
tree* tmp = l.top();
cout << tmp->data;
l.pop();
if (tmp->rchild)
{
l.push(tmp->rchild);
}
}
}
}
}
void judgeLeftOrRight(stack<tree*>& l,tree* tmp2)
{
if (!l.empty())
{
if (l.top()->lchild == tmp2)
{
l.push(l.top()->rchild);
return;
}
else if (l.top()->rchild == tmp2)
{
tree* tmp = l.top();
l.pop();
cout << tmp->data;
judgeLeftOrRight(l, tmp);
}
}
}
//后序遍历 左右根
void back_print(tree* root)
{
stack<tree*> l;
l.push(root);
while (!l.empty())
{
tree* tmp = l.top();
if (tmp->lchild)
{
l.push(tmp->lchild);
}
else
{
l.pop();
cout << tmp->data;
if (!l.empty())
{
judgeLeftOrRight(l, tmp);
}
}
}
}
int main()
{
//a b d 0 0 e 0 0 c f 0 0 g 0 0
tree* root;
creatTree(root);
print_tree(root);
cout << endl << "________" << endl;
front_print(root);
cout << endl << "_________" << endl;
mid_print(root);
cout << endl << "_________" << endl;
back_print(root);
return 0;
}