struct BiNode{
    int data;
    BiNode *left;
    BiNode *right;
    BiNode(int x){
        data = x;
        left = right = NULL;
    }
};

class BiTree {
private:
    BiNode *root;
    static void rpreprint(BiNode*);          //前序遍歷（遞歸）
    static void rinprint(BiNode*);           //中序遍歷（遞歸）
    static void rpostprint(BiNode*);         //后序遍歷（遞歸）
    static void ipreprint(BiNode*);          //前序遍歷（迭代）
    static void iinprint(BiNode*);           //中序遍歷（迭代）
    static void ipostprint(BiNode*);         //后序遍歷（迭代）
    static BiNode* rfind(int, BiNode*);      //尋找節(jié)點(diǎn)（遞歸）
    static void rprint(BiNode*, int);        //簡(jiǎn)易樹形打?。ㄟf歸）
public:
    BiTree();                                //無(wú)參構(gòu)造
    BiTree(int);                             //有參構(gòu)造
    void preprint();                         //前序遍歷
    void inprint();                          //中序遍歷
    void postprint();                        //后序遍歷
    void print();                            //簡(jiǎn)易樹形
    BiNode* find(int);                       //尋找節(jié)點(diǎn)
    bool insert(int, int, int);              //插入節(jié)點(diǎn)
};

void BiTree::rpreprint(BiNode *r){
    if(r == NULL)
        return;
    cout << r->data << " " ;
    rpreprint(r->left);
    rpreprint(r->right);
}

void BiTree::rinprint(BiNode *r){
    if(r == NULL)
        return;
    rinprint(r->left);
    cout << r->data << " " ;
    rinprint(r->right);
}

void BiTree::rpostprint(BiNode *r){
    if(r == NULL)
        return;
    rpostprint(r->left);
    rpostprint(r->right);
    cout << r->data << " ";
}

void BiTree::ipreprint(BiNode *r) {
    stack<BiNode*> st;
    if(r == NULL)
        return;
    while(r){
        cout << r->data << " ";
        st.push(r);
        r = r->left;
        while(r == NULL && !st.empty()){
            r = st.top();
            st.pop();
            r = r->right;
        }
    }
}
void BiTree::iinprint(BiNode *r) {
    stack<BiNode*> st;
    if(r == NULL)
        return;
    while(r){
        st.push(r);
        r = r->left;
        while(r == NULL && !st.empty()){
            r = st.top();
            st.pop();
            cout << r->data << " ";
            r = r->right;
        }
    }
}



BiNode* BiTree::rfind(int x, BiNode *r){
    if(r == NULL)
        return NULL;
    if(r->data == x)
        return r;
    BiNode* found = rfind(x, r->left);
    return found ? found : rfind(x, r->right);
}

void BiTree::rprint(BiNode *r, int deep) {
    for(int i = 0; i < deep; i++)
        cout << "  ";
    if(r == NULL)
        cout << "[/]" << endl;
    else{
        cout << r->data << endl;
        rprint(r->left, deep+1);
        rprint(r->right, deep+1);
    }
}

BiTree::BiTree(){
    root = NULL;
}

BiTree::BiTree(int r){
    root = new BiNode(r);
}

void BiTree::preprint(){
    // rpreprint(root);
    ipreprint(root);
}

void BiTree::inprint() {
    // rinprint(root);
    iinprint(root);
}

void BiTree::postprint() {
    rpostprint(root);
}

void BiTree::print() {
    rprint(root, 0);
}

BiNode* BiTree::find(int x){
    return rfind(x, root);
}

bool BiTree::insert(int r, int LR, int x){
    BiNode* found;
    found = find(r);
    if(found == NULL)
        return false;
    if(LR == 0){
        if(found->left)
            return false;
        found->left = new BiNode(x);
    }
    else{
        if(found->right)
            return false;
        found->right = new BiNode(x);
    }
    return true;
}