L2-006 树的遍历 (25 分)

#include 
#include 
using namespace std;
const int N = 40;
struct node {
    int data;
    node *lchild;
    node *rchild;
};
int last[N], in[N];
int n;

node *creat_tree(int lastl, int lastr, int inl, int inr) {
    if(lastl > lastr) return NULL;
    node *root = new node;
    root->data = last[lastr];
    int i;
    for(i = inl; i <= inr; i++) {
        if(in[i] == last[lastr]) break;
    }
    int numleft = i - inl;
    root->lchild = creat_tree(lastl, lastl + numleft - 1, inl, i-1);
    root->rchild = creat_tree(lastl+numleft, lastr-1, i+1, inr);
    return root;
}
void level_print(node *root) {
    queueq;
    q.push(root);
    int cnt = 0;
    while(q.size()) {
        node *t = q.front(); q.pop();
        cout << t->data;
        cnt++;
        if(cnt != n) cout << ' ';
        if(t->lchild!=NULL) q.push(t->lchild);
        if(t->rchild!=NULL) q.push(t->rchild);
    }
}
int main() {
    cin >> n;
    for(int i = 0; i < n; i++) cin >> last[i];
    for(int i = 0; i < n; i++) cin >> in[i];
    node *root = creat_tree(0, n-1, 0, n-1);
    level_print(root);
    return 0;
}