共计 1024 个字符,预计需要花费 3 分钟才能阅读完成。
题目粗心:
给定一颗二叉查找树的构造和一些待插入数字, 要求输入该二叉树的层序遍历序列
算法思路:
道题和 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;
}
正文完