[PAT解题报告] Build A Binary Search Tree
给定树结构，和一些整数，把这些整数填写到树结构中，恰好形成BST (Binary Search
Tree)。BST的定义已经给定就是左边节点的值都比它小，右边的值都不比它小。
其实也不难，二叉树的形态已经知道了，我们先把二叉树建立起来而不管节点上的值。输入给了每个节点的左右孩子，我们自然就有了树结构。问题是如何生成BST呢？怎么才能把数填进去？
BST的关键是中序遍历之后得到的数是有序的。
那么我们自然可以把所有的树排序，再中序遍历顺便填上这些数——按照由小到大的顺序填就可以，关键是中序遍历告诉我们这些节点访问的顺序了。
另外一种方法就是，统计出每个节点左孩子子树的个数——这样也就变相地知道这个数应该填几了。
构造好树以后，输出是层序遍历的结果。那么一个可以用一个显然的bfs, 用队列就可以一层一层地访问出所有节点，直接输出就可以了。
代码：
#include <cstdio>
#include <cstring>
#include <string>
#include <queue>
#include <algorithm>
using namespace std;
int left[105];
int right[105];
int a[105];
int b[105];
queue<int> q;
void dfs(int now, int &x) {
if (now < 0) {
return;
}
dfs(left[now], x);
b[now] = a[x++];
dfs(right[now], x);
}
int main() {
int n;
scanf("%d", &n);
for (int i = 0; i < n; ++i) {
scanf("%d%d",&left[i], &right[i]);
}
for (int i = 0; i < n; ++i) {
scanf("%d", &a[i]);
}
sort(a, a + n);
dfs(0, n = 0);
bool mark = false;
for (q.push(0); !q.empty(); q.pop()) {
if (mark) {
putchar(' ');
}
else {
mark = true;
}
int x = q.front();
printf("%d", b[x]);
if (left[x] >= 0) {
q.push(left[x]);
}
if (right[x] >= 0) {
q.push(right[x]);
}
}
puts("");
return 0;
}
原题链接： http://www.patest.cn/contests/pat-a-practise/1099
查看10道真题和解析