Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1436445
  • 博文数量: 241
  • 博客积分: 10
  • 博客等级: 民兵
  • 技术积分: 2253
  • 用 户 组: 普通用户
  • 注册时间: 2012-04-11 22:27
个人简介

--

文章分类

全部博文(241)

文章存档

2021年(3)

2019年(6)

2018年(1)

2017年(9)

2016年(21)

2015年(50)

2014年(125)

2013年(26)

我的朋友

分类: C/C++

2014-03-22 13:19:26

题目描述:
判断两序列是否为同一二叉搜索树序列
Input
开始一个数n,(1<=n<=20) 表示有n个需要判断,n= 0 的时候输入结束。 接下去一行是一个序列,序列长度小于10,包含(0~9)的数字,没有重复数字,根据这个序列可以构造出一颗二叉搜索树。 接下去的n行有n个序列,每个序列格式跟第一个序列一样,请判断这两个序列是否能组成同一颗二叉搜索树。
Output
如果序列相同则输出YES,否则输出NO
Sample Input
2
567432
543267
576342
0
Sample Output
YES
NO
代码

点击(此处)折叠或打开

  1. #include <iostream>
  2. #include <string.h>
  3. using namespace std;
  4. int main()
  5. {
  6.     char l1[10];
  7.     int n;
  8.     int num;
  9.     int j;
  10.     int tree[1025];
  11.     char l2[10];
  12.     int tree2[1025];
  13.     int i;
  14.     while(cin>>n)
  15.     {
  16.         if(n==0)
  17.             break;
  18.         cin>>l1;
  19.         memset(tree,-1,sizeof(tree));
  20.         for(i=0;l1[i];i++)
  21.         { //构造二叉搜索树
  22.             num = l1[i] - '0';
  23.             j = 1;
  24.             while(tree[j]!=-1)
  25.             {
  26.                 if(num <= tree[j])
  27.                     j = j*2;
  28.                 else
  29.                     j = j*2 + 1;
  30.             }
  31.             tree[j] = num;
  32.         }
  33.         while(n--)
  34.         { //输入n个序列
  35.             cin>>l2;
  36.             memset(tree2,-1,sizeof(tree2));
  37.             for(i=0;l2[i];i++)
  38.             { //构造比较二叉搜索树
  39.                 num = l2[i] - '0';
  40.                 j = 1;
  41.                 while(tree2[j]!=-1)
  42.                 {
  43.                     if(num <= tree2[j])
  44.                         j = j*2;
  45.                     else
  46.                         j = j*2 + 1;
  47.                 }
  48.                 tree2[j] = num;
  49.             }

  50.             for(i=0;i<=1024&&tree[i]==tree2[i];i++)
  51.                 ; //比较
  52.             if(i>1024)
  53.                 cout<<"YES"<<endl;
  54.             else
  55.                 cout<<"NO"<<endl;
  56.         }
  57.     }
  58.     return 0;
  59. }
http://blog.csdn.net/sjf0115/article/details/8682973
http://www.cnblogs.com/yym2013/p/3552800.html
http://www.cnblogs.com/yuyixingkong/p/3286077.html
阅读(1241) | 评论(0) | 转发(0) |
0

上一篇:OJ-密码验证合格程序

下一篇:OJ-坐标移动

给主人留下些什么吧!~~