//
// Created by littlebear on 2022/5/11.
//

#include <iostream>
#include <queue>

#define DATA_TYPE char

using namespace std;

struct BinTreeNode {
    DATA_TYPE value;
    BinTreeNode *left;
    BinTreeNode *right;
};

typedef struct BinTreeNode *PBinTreeNode;
typedef struct BinTreeNode *BinTree;
typedef BinTree *PBinTree;

PBinTreeNode getTree(PBinTree t) {
    return *t;
}

PBinTreeNode getLeftTree(PBinTreeNode p) {
    return p->left;
}

PBinTreeNode getRightTree(PBinTreeNode p) {
    return p->right;
}

PBinTreeNode createRest_BTree() {
    PBinTreeNode pbnode;
    char ch;
    scanf("%c", &ch);
    if (ch == '@') pbnode = nullptr;
    else {
        pbnode = (PBinTreeNode) malloc(sizeof(struct BinTreeNode));
        if (pbnode == nullptr) {
            printf("Out of space!\n");
            return pbnode;
        }
        pbnode->value = ch;
        pbnode->left = createRest_BTree();
        pbnode->right = createRest_BTree();
    }
    return pbnode;
}


PBinTree create_BTree() {
    PBinTree pbtree = (PBinTree) malloc(sizeof(BinTree));
    if (pbtree != nullptr)
        *pbtree = createRest_BTree();
    return pbtree;
}

void visit(BinTreeNode *p) {
    cout << p->value << " ";
}

void preOrder(BinTreeNode *p) {
    if (p != nullptr) {
        visit(p);
        preOrder(p->left);
        preOrder(p->right);
    }
}

void inOrder(BinTreeNode *p) {
    if (p != nullptr) {
        inOrder(p->left);
        visit(p);
        inOrder(p->right);
    }
}

void postOrder(BinTreeNode *p) {
    if (p != nullptr) {
        postOrder(p->left);
        postOrder(p->right);
        visit(p);
    }
}


void levelOrder(BinTreeNode *p) {
    if (p != nullptr) {
        queue<BinTreeNode *> q;
        q.push(p);
        while (!q.empty()) {
            BinTreeNode *node = q.front();
            q.pop();
            visit(node);
            if (node->left != nullptr) q.push(node->left);
            if (node->right != nullptr) q.push(node->right);
        }
    }
}

int main() {
    PBinTree tree = create_BTree();
    //ABDF@@@E@G@@C@IJ@@K@@

    printf("PreOrder: ");
    preOrder(*tree);

    printf("\nInOrder: ");
    inOrder(*tree);

    printf("\nPostOrder: ");
    postOrder(*tree);

    printf("\nLevelOrder: ");
    levelOrder(*tree);
    return 0;
}