#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
/*定义二叉树的结构*/

typedef struct Node
{
    char data;                    /*数据域*/
    struct Node *lchild, *rchild; /*左子树和右子树*/
} * BiTree, BiNode;
    //实例化BiTree表示指向该结构体的指针（表示一棵树）；BiNode是该结构体类型（表示一个指针）。


/*先需创建二叉树*/
void CreateBiTree(BiTree &T) //Bitree &T：&表示取地址(C++)，也可以写作C的指针 Bitree *T。
                             //总之T是指向指针BiTree的指针，定义T是因为我们要修改BiTree，通过其指针修改。(?)
{
    char ch;
    cin >> ch;
    if (ch == '#')
        T = NULL;
    else
    {
        T = new BiNode; /*创建一个新节点*/   //但是T不是node的指针的指针吗？？
        T->data = ch;
        CreateBiTree(T->lchild);
        CreateBiTree(T->rchild);  //递归，输入先序遍历，创建出一个树。(递归！！)
    }
}
void InOrderTraverse(BiTree T)  //这时T是node的指针。
{
    /*中序遍历*/
    if (T)   //当指针非空，即有子树的时候
    {
        InOrderTraverse(T->lchild); //访问左子
        cout << T->data;            //输出 无左子树的结点
        InOrderTraverse(T->rchild); //访问右子
    }
}
void PreOrderTraverse(BiTree T)
{
    /*先序遍历*/
    if (T)
    {
        cout << T->data;
        PreOrderTraverse(T->lchild);
        PreOrderTraverse(T->rchild);
    }
}



int main()
{
    while(cin){
	BiTree T;
    cout << "先序遍历输入(以#结束)：";
    CreateBiTree(T);
    cout << "中序遍历输出：";
    InOrderTraverse(T);
    cout << endl;}
    return 0;
}