天梯赛练习 L3-016 二叉搜索树的结构 (30分)

题目分析：

用数型结构先建树，一边输入一边建立，根节点的下标为1，所以左孩子为root*2，右孩子为root*2+1，输入的时候可用cin输入字符串也可用scanf不会超时，判断是否在同一层可以判断两个节点位置以2为底的对数向下取整是否相同得知（log(m)/log(2)为以换底公式实现的求以2为底m的对数）

坑点：

查询的整数可能并不出现在建立的树中（第三个测试数据）

本题代码：（菜）

  1 #include<iostream>
  2 #include<stdio.h>
  3 #include<string>
  4 #include<string.h>
  5 #include<algorithm>
  6 #include<map>
  7 #include<cmath>
  8 using namespace std;
  9 
 10 const int N = 10005;
 11 int vis[N]; 
 12 int tree[N];
 13 map<int, int> mp;
 14 int n, m;
 15 
 16 void create(int root, int value){
 17     if(vis[root] == 0){
 18         vis[root] = 1;
 19         tree[root] = value;
 20         mp[value] = root;        //记录每个value在那个点 
 21         return;
 22     }else{
 23         if(value < tree[root]) create(root*2, value);
 24         else create(root*2+1, value);
 25     }
 26 }
 27 
 28 bool judge(int x){
 29     if(mp.find(x) == mp.end()){
 30         printf("No
");
 31         return false;
 32     }
 33     return true;
 34 }
 35 
 36 void isgen(int x){
 37     if(!judge(x)) return;
 38     if(tree[1] == x) printf("Yes
");
 39     else printf("No
");
 40 }
 41 
 42 void iscen(int x, int y){
 43     if(!judge(x) || !judge(y)) return;
 44     x = mp[x]; y = mp[y];
 45     if(int(log(x)/log(2)) == int(log(y)/log(2))) printf("Yes
");
 46     else printf("No
");
 47 }
 48 
 49 void isleft(int x, int y){
 50     if(!judge(x) || !judge(y)) return;
 51     if(mp[y]*2 == mp[x]) printf("Yes
");
 52     else printf("No
"); 
 53 }
 54 
 55 void isright(int x, int y){
 56     if(!judge(x) || !judge(y)) return;
 57     if(mp[y]*2+1 == mp[x]) printf("Yes
");
 58     else printf("No
");
 59 }
 60 
 61 void isborther(int x, int y){
 62     if(!judge(x) || !judge(y)) return;
 63     if(mp[x]/2 == mp[y]/2) printf("Yes
");
 64     else printf("No
");
 65 } 
 66 
 67 void isparent(int x, int y){
 68     if(!judge(x) || !judge(y)) return;
 69     if(mp[y]/2 == mp[x]) printf("Yes
");
 70     else printf("No
");
 71 }
 72 
 73 int main(){
 74     scanf("%d", &n);
 75     memset(vis, 0, sizeof(vis));
 76     for(int i = 1; i <= n; i++){
 77         int x; scanf("%d", &x);
 78         create(1, x);
 79     }
 80     scanf("%d", &m);
 81     for(int i = 1; i <= m; i++){
 82         int x;
 83         cin>>x;
 84         string s1; cin>>s1;
 85         if(s1 == "and"){
 86             int y; cin>>y;
 87             cin>>s1; cin>>s1;
 88             if(s1 == "on"){    //判断是否是同层 
 89                 getline(cin, s1);
 90                 iscen(x, y);
 91             }else{            //判断是否是兄弟 
 92                 getline(cin, s1);
 93                 isborther(x, y);
 94             }
 95         }else{
 96             cin>>s1; cin>>s1;
 97             if(s1 == "root"){//是否为根 
 98                 isgen(x);
 99             }else if(s1 == "parent"){//x是否是y的父亲 
100                 cin>>s1;
101                 int y; cin>>y;
102                 isparent(x, y);
103             }else if(s1 == "left"){//x是否是y的左孩子 
104                 cin>>s1; cin>>s1;
105                 int y; cin>>y;
106                 isleft(x, y);
107             }else{                    //x是否是y的右孩子 
108                 cin>>s1; cin>>s1;
109                 int y; cin>>y;
110                 isright(x, y);
111             }
112         }
113     }
114     return 0;
115 }