#include <iostream>
#include <string>
using namespace std;
typedef char ElemType;
typedef struct TNode{
    string data = "";
    TNode *lchild;
    TNode *rchild;
}TreeNode, *BiTree;

void createBiTree(BiTree *T){
    string ch;
    cin >> ch;
    if (ch == "#"){
        *T = NULL;
        return;
    }
    *T = new TreeNode;
    (*T)->data = ch;
    createBiTree(&(*T)->lchild);
    createBiTree(&(*T)->rchild);
}
int isEmpty(BiTree T){
    if (T == NULL)
        return 1;
    else
        return 0;
}
void traverseBiTree(BiTree T){
    if (isEmpty(T))
        return;
    cout << T->data << " ";
    traverseBiTree(T->lchild);
    traverseBiTree(T->rchild);
}
void inOrderBiTree(BiTree T){
    if (isEmpty(T))
        return;
    inOrderBiTree(T->lchild);
    cout << T->data << " ";
    inOrderBiTree(T->rchild);
}
void PostOrderBiTree(BiTree T){
    if (isEmpty(T))
        return;
    PostOrderBiTree(T->lchild);
    PostOrderBiTree(T->rchild);
    cout << T->data << " ";
}
int treeDeep(BiTree T){
    int deep = 0;
    if (isEmpty(T))
        return deep;
    int leftDeep = treeDeep(T->lchild);
    int rightDeep = treeDeep(T->rchild);
    deep = leftDeep > rightDeep ? leftDeep + 1 : rightDeep + 1;
    return deep;
}
int main(){
    BiTree T;
    createBiTree(&T);
    traverseBiTree(T);
    cout << endl;
    inOrderBiTree(T);
    cout << endl;
    PostOrderBiTree(T);
    cout << endl;
    cout << "树深：" << treeDeep(T) << endl;
    system("pause");
}