正文
天梯赛练习 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\n");
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\n");
39 else printf("No\n");
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\n");
46 else printf("No\n");
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\n");
52 else printf("No\n");
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\n");
58 else printf("No\n");
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\n");
64 else printf("No\n");
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\n");
70 else printf("No\n");
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 }
