#include<iostream>
#define N 7
using namespace std;
 
//定义节点
class node
{
public:
    int data;
    node *leftChild;//指针
    node *rightChild;
};
typedef node BiTreeNode;
typedef node *BiTree;//等价
 
node *createNode(int value)//创建节点，返回类型指针型，所以加*
{
    node * q = new node;
    q->leftChild = NULL;//leftChild指针为空
    q->rightChild = NULL;
    q->data = value;
 
    return q;
}
 
void createBiTree(BiTree &T)
{
    char c;
    cin >> c;
    if (c=='#')
        T = NULL;
    else
    {
        T = new BiTreeNode;
        T->data = c;
        createBiTree(T->leftChild);
        createBiTree(T->rightChild);
    }
}
//访问节点中的数据
char visit(BiTree tree)
{
    return tree->data;
}
// 先序遍历
void preorderTreeWalk(BiTree tree)
{
    if(tree)
    {
        cout << visit(tree) << " ";
        preorderTreeWalk(tree->leftChild);
        preorderTreeWalk(tree->rightChild);
    }
}
// 中序遍历
void inorderTreeWalk(BiTree tree)
{
    if(tree)
    {
        inorderTreeWalk(tree->leftChild);
        cout << visit(tree) << " ";
        inorderTreeWalk(tree->rightChild);
    }
}
// 后序遍历
void postorderTreeWalk(BiTree tree)
{
    if(tree)
    {
        postorderTreeWalk(tree->leftChild);
        postorderTreeWalk(tree->rightChild);
        cout << visit(tree) << " ";
    }
}
 
int main()
{
    BiTree tree;
    createBiTree(tree);
    cout << "先序遍历结果为:";
    preorderTreeWalk(tree);
    cout << endl;
    cout << "中序遍历结果为:";
    inorderTreeWalk(tree);
    cout << endl;
    cout << "后序遍历结果为:";
    postorderTreeWalk(tree);
    cout << endl;
 
    return 0;
}