#include<iostream>
#include<cstring>
#include<stack>
#include<queue>
using namespace std;
struct node{
    char c;
    node *lc;
    node *rc;
};
node* rebuild(char pre[],char in[],int len){ //已知前中序重建二叉树 
    if(len==0)    
        return NULL;
    node *root = new node; //注意要new空间！！！ 
    root->c = pre[0];
    int i=0;
    for(;i<len;i++){
        if(in[i]==pre[0]) break;
    }
    root->lc = rebuild(pre+1,in,i);
    root->rc = rebuild(pre+i+1,in+i+1,len-i-1);
    return root;
}
void dfs(node *root){ //栈，先压右节点，再压左节点
    stack<node *> s;
    s.push(root);
    while(!s.empty()){
        root=s.top();
        cout<<root->c<<" ";
        s.pop();
        if(root->rc!=NULL){
            s.push(root->rc);
        }
        if(root->lc!=NULL){
            s.push(root->lc);
        }
    }
}
void bfs(node *root){//队列：先压左节点，再压右节点
    queue<node *> q;
    q.push(root);
    while(!q.empty()){
        root=q.front();
        cout<<root->c<<" ";
        q.pop();
        if(root->lc){
            q.push(root->lc);
        }
        if(root->rc){
            q.push(root->rc);
        }
    }
}
void pre_order(node* root){  //前序遍历 
    if(root != NULL){  
        cout<<root->c<<" ";  
        pre_order(root->lc);  
        pre_order(root->rc);  
    }  
}  
void in_order(node* root){  //中序遍历 
    if(root != NULL){           
        in_order(root->lc); 
        cout<<root->c<<" ";  
        in_order(root->rc);         
    }  
}  
void post_order(node* root){  //后序遍历 
    if(root != NULL){           
        post_order(root->lc);  
        post_order(root->rc);  
        cout<<root->c<<" "; 
    }  
}  
int main(){
    char pre[50] = "ABDHLEKCFG";     //前序序列
      char in[50] = "HLDBEKAFCG";      //中序序列 
    int len=strlen(in);
    node *root = rebuild(pre,in,len);
    pre_order(root);
    cout<<endl;
    post_order(root);
    cout<<endl;
    dfs(root);
    cout<<endl;
    bfs(root);
}