二叉树的遍历和创建

#include <cstdio>
#include <queue>
#include <vector>
using namespace std;

struct node{
    node* lchild;
    node* rchild;
    int data;   
};

int n;
vector<int> pre;
vector<int> in;
vector<int> post;
vector<int> layer;

//根据中序和后序，创建二叉树
node* createByPostAndIn(int postL, int postR, int inL, int inR){
    if(postL > postR) return NULL;
    node* root = new node;
    root->data = post[postR];
    int k;
    for(k = inL; k <= inR; k++){
        if(in[k] == post[postR]){
            break;
        }
    }
    int numLeft = k - inL;  //左子树的结点个数
    root->lchild = createByPostAndIn(postL, postL + numLeft - 1, inL, k - 1);
    root->rchild = createByPostAndIn(postL + numLeft, postR - 1, k + 1, inR);
    return root;
}

//根据中序和前序，创建二叉树
node* createByPreAndIn(int preL, int preR, int inL, int inR){
    if(preL > preR) return NULL;
    node* root = new node;
    root->data = pre[preL];
    int k;
    for(k = inL; k <= inR; k++){
        if(in[k] == pre[preL]){
            break;
        }
    }
    int numLeft = k - inL; //左子树的结点个数
    root->lchild = createByPreAndIn(preL + 1, preL + numLeft, inL, k - 1);
    root->rchild = createByPreAndIn(preL + numLeft + 1, preR, k + 1, inR);
    return root;
}

//根据中序和层序创建二叉树
node* createByLayerAndIn(vector<int> layer, vector<int> in, int inL, int inR){
    if(inL > inR || layer.size() == 0) return NULL;
    node* root = new node;
    root->data = layer[0];
    int pos;
    for(pos = inL; pos <= inR; pos++){
        if(in[pos] == layer[0]){
            break;
        }
    }
    vector<int> layerLeft, layerRight; //存放左、右子树的层序序列
    for(int i = 1; i < layer.size(); i++){
        int j;
        for(j = inL; j < pos; j++){
            if(in[j] == layer[i]){
                layerLeft.push_back(layer[i]); //如果在pos前找到，插入左子树
                break;
            }
        }
        //超过pos，j==pos时即为在左子树中没有找到插入右子树（层序遍历保持左右子树层序遍历顺序的一致性）
        if(j == pos) layerRight.push_back(layer[i]); 
    }
    root->lchild = createByLayerAndIn(layerLeft, in, inL, pos - 1);
    root->rchild = createByLayerAndIn(layerRight, in, pos + 1, inR);
    return root;
}



int num = 0;
void BFS(node* root){  //层次遍历
    queue<node*> q;
    q.push(root);
    while(!q.empty()){
        node* now = q.front();
        q.pop();
        printf("%d",now->data);
        num++;
        if(num < n){
            printf(" ");
        }
        if(now->lchild != NULL) q.push(now->lchild);
        if(now->rchild != NULL) q.push(now->rchild);
    }
}

void preOrder(node* root){ //先序遍历
    if(root == NULL){
        return;
    }
    printf("%d",root->data);
    num++;
    if(num < n){
        printf(" ");
    }
    preOrder(root->lchild);
    preOrder(root->rchild);
}

void inOrder(node* root){ //中序遍历
    if(root == NULL){
        return;
    }
    inOrder(root->lchild);
    printf("%d",root->data);
    num++;
    if(num < n){
        printf(" ");
    }
    inOrder(root->rchild);
}

void postOrder(node* root){ //后序遍历
    if(root == NULL){
        return;
    }
    postOrder(root->lchild);
    postOrder(root->rchild);
    printf("%d",root->data);
    num++;
    if(num < n){
        printf(" ");
    }
}

int main(){
    scanf("%d",&n);
    int temp;
    for(int i = 0; i < n; i++){
        scanf("%d",&temp);
        in.push_back(temp);
    }

/*测试数据：中后
7
1 2 3 4 5 6 7
2 3 1 5 7 6 4
*/
    for(int i = 0; i < n; i++){
        scanf("%d",&temp);
        post.push_back(temp);
    }
    node* root = createByPostAndIn(0, n -1, 0, n -1);
/*测试数据：中前
7
1 2 3 4 5 6 7
4 1 3 2 6 5 7
*/
    // for(int i = 0; i < n; i++){
    //     scanf("%d",&temp);
    //     pre.push_back(temp);
    // }
    // node* root = createByPreAndIn(0, n -1, 0, n -1);
/*测试数据：中层
7
1 2 3 4 5 6 7
4 1 6 3 5 7 2
*/
    // for(int i = 0; i < n; i++){
    //     scanf("%d",&temp);
    //     layer.push_back(temp);
    // }
    // node* root = createByLayerAndIn(layer, in, 0, n -1);
    BFS(root);
    return 0;
}