PTA 天梯赛练习 7-10 树的遍历（25 分）_7-10 满树的遍历

PTA 天梯赛练习 7-10 树的遍历（25 分）

由树的后序遍历序列和中序遍历序列建立一颗二叉树并输出其层次遍历结果
题目连接
7-10 树的遍历（25 分）
给定一棵二叉树的后序遍历和中序遍历，请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。
输入格式：

输入第一行给出一个正整数N（≤30），是二叉树中结点的个数。第二行给出其后序遍历序列。第三行给出其中序遍历序列。数字间以空格分隔。
输出格式：

在一行中输出该树的层序遍历的序列。数字间以1个空格分隔，行首尾不得有多余空格。
输入样例：

7
2 3 1 5 7 6 4
1 2 3 4 5 6 7
输出样例：

4 1 6 3 5 7 2

解题思路
1.树的建立，遍历以及其他操作普遍用到递归的方法（树的定义就是递归定义的，所以性质决定方法）
2.层次遍历显然用广搜
3.前中序建立则从前向后【由前序序列从前向后确定树的每个节点】（先左子树后右子树）
注：由先序序列和中序序列建立方法见下一篇博客。
4.中后序建立则从后向前【由后序序列从后向前确定树的每个节点】（先右子树后左子树）
5.最重要的有两点：一是左右子树的长度，二是每次加入树的结点数组下标
在中后序建立时直接通过下标计算长度即可，而前中序建立时添加一个变量来记录

#include<iostream>
#include<cstring>
#include<string>
#include<memory.h>
#include<queue>
#include<cstdlib>
#include<cstdio>
using namespace std;
int a[40];
int b[40];
typedef struct Node {
    int data;
    struct Node *l,*r;
} node,*tree;
int n;
queue<tree>q;
void creat(tree &t,int pre,int last,int len) {
    int inx;
    int lenf,lenr;
    if(len<=0) {
        t=NULL;
        return;
    }
    else {
        t=(tree)malloc(sizeof(node));
        t->data=a[last];
        for(int i=0; i<n; i++) {
            if(b[i]==a[last]) {
                inx=i;
                break;
            }
        }
        lenr=len-(inx-pre)-1;
        creat(t->r,inx+1,last-1,lenr);
        lenf=inx-pre;
        creat(t->l,pre,last-lenr-1,lenf);
    }
    return ;
}
void ceng(tree t) {
    tree tt=t;
    q.push(tt);
    while(!q.empty()) {
        tt=q.front();
        cout<<tt->data;
        if(tt->l!=NULL) {
            q.push(tt->l);
        }
        if(tt->r!=NULL) {
            q.push(tt->r);
        }
        q.pop();
        if(!q.empty()){
            cout<<" ";
        }
        else{
            cout<<endl;
        }
    }
    return ;
}
int main() {
    tree t=NULL;
    cin>>n;
    memset(a,0,sizeof(a));
    memset(b,0,sizeof(b));
    for(int i=0; i<n; i++) {
        cin>>a[i];
    }
    for(int i=0; i<n; i++) {
        cin>>b[i];
    }
    creat(t,0,n-1,n);
    ceng(t);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76