找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 1666|回复: 0
收起左侧

[米群网刷题小分队] [PAT-B] 1099 Build A Binary Search Tree

[复制链接]
发表于 5-3-2015 11:32 PM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
1099 Build A Binary Search Tree

给定树,把二叉搜索树构造出来,再给出层序遍历…… 就直接模拟就行,二叉树的结构是给定的,按中序遍历的顺序由小到大填数即可。

  1. #include <cstdio>
  2. #include <cstring>
  3. #include <string>
  4. #include <queue>
  5. #include <algorithm>

  6. using namespace std;


  7. int left[105];
  8. int right[105];
  9. int a[105];
  10. int b[105];
  11. queue<int> q;

  12. void dfs(int now, int &x) {
  13.         if (now < 0) {
  14.                 return;
  15.         }
  16.         dfs(left[now], x);
  17.         b[now] = a[x++];
  18.         dfs(right[now], x);
  19. }

  20. int main() {
  21. int n;
  22.         scanf("%d", &n);
  23.         for (int i = 0; i < n; ++i) {
  24.                 scanf("%d%d",&left【i】, &right【i】);
  25.         }
  26.         for (int i = 0; i < n; ++i) {
  27.                 scanf("%d", &a【i】);
  28.         }
  29.         sort(a, a + n);
  30.         dfs(0, n = 0);               
  31.         bool mark = false;
  32.         for (q.push(0); !q.empty(); q.pop()) {
  33.                 if (mark) {
  34.                         putchar(' ');
  35.                 }
  36.                 else {
  37.                         mark = true;
  38.                 }
  39.                 int x = q.front();
  40.                 printf("%d", b[x]);
  41.                 if (left[x] >= 0) {
  42.                         q.push(left[x]);
  43.                 }
  44.                 if (right[x] >= 0) {
  45.                         q.push(right[x]);
  46.                 }
  47.         }
  48.         puts("");
  49.         return 0;
  50. }
复制代码


本帖被以下淘专辑推荐:

我们始终相信IT会持续改造甚至创新传统行业,我们始终全面看好咱们的CS专业!
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表