题目粗心:
给定一颗二叉查找树的构造和一些待插入数字,要求输入该二叉树的层序遍历序列
算法思路:
道题和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;}