题目粗心:

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

算法思路:

道题和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;}