关于算法-数据结构:PAT甲级1099-Build-A-Binary-Search-Tree

题目粗心：

给定一颗二叉查找树的构造和一些待插入数字,要求输入该二叉树的层序遍历序列

算法思路：

道题和1064的思路是一样的,都是紧紧把握一条,就是利用给定的二叉树的信息取得中序遍历的结点的下标序列,对给定的待插入数字进行排序失去中序遍历的结点的数字序列,而后两者一一对应就能够将该二叉查找树结构进去。这里因为输出的是结点的编号,那么用二叉树的动态存储办法比拟不便,应用in数组保留结点中序遍历的编号序列。在输出结束后,对二叉树进行中序遍历,根节点为0,将in数组中的数字依照遍历程序顺次填入到二叉树中，就能够实现二叉树的构建，而后再进行层序遍历并进行输入即可。

提交后果：

AC代码：

#include<cstdio>
#include<queue>
#include<algorithm>

using namespace std;

struct Node{
    int data;
    int left;
    int right;
}node[105];

int N;
int in[105];//中序遍历序列 
int inIndex = 0;//中序序列工作指针 

void preTraverse(int root){
    if(root==-1) return;
    preTraverse(node[root].left);
    node[root].data = in[inIndex++];
    preTraverse(node[root].right);
}

int num=0;//管制空格的输入 
void levelTraverse(int root){
    queue<int> q;
    q.push(root);
    while(!q.empty()){
        int t = q.front();
        q.pop();
        printf("%d",node[t].data);
        if(num<N-1) printf(" ");
        ++num;
        if(node[t].left!=-1){
            q.push(node[t].left);
        }
        if(node[t].right!=-1){
            q.push(node[t].right);
        }
    }
}

int main(){
    scanf("%d",&N);
    for(int i=0;i<N;++i){
        scanf("%d %d",&node[i].left,&node[i].right);
    }
    for(int i=0;i<N;++i){
        scanf("%d",&in[i]);
    }
    sort(in,in+N);
    preTraverse(0);
    levelTraverse(0);
    return 0;
}