当前位置：首页 > news >正文

L3-016 二叉搜索树的结构

news 来源：原创 2024/4/28 8:29:55

二叉搜索树或者是一棵空树，或者是具有下列性质的二叉树：若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别为二叉搜索树。（摘自百度百科）

给定一系列互不相等的整数，将它们顺次插入一棵初始为空的二叉搜索树，然后对结果树的结构进行描述。你需要能判断给定的描述是否正确。例如将{ 2 4 1 3 0 }插入后，得到一棵二叉搜索树，则陈述句如“2是树的根”、“1和4是兄弟结点”、“3和0在同一层上”（指自顶向下的深度相同）、“2是4的双亲结点”、“3是4的左孩子”都是正确的；而“4是2的左孩子”、“1和3是兄弟结点”都是不正确的。

输入格式：

输入在第一行给出一个正整数N（≤100），随后一行给出N个互不相同的整数，数字间以空格分隔，要求将之顺次插入一棵初始为空的二叉搜索树。之后给出一个正整数M（≤100），随后M行，每行给出一句待判断的陈述句。陈述句有以下6种：

A is the root，即"A是树的根"；
A and B are siblings，即"A和B是兄弟结点"；
A is the parent of B，即"A是B的双亲结点"；
A is the left child of B，即"A是B的左孩子"；
A is the right child of B，即"A是B的右孩子"；
A and B are on the same level，即"A和B在同一层上"。

题目保证所有给定的整数都在整型范围内。

输出格式：

对每句陈述，如果正确则输出Yes，否则输出No，每句占一行。

输入样例：

5
2 4 1 3 0
8
2 is the root
1 and 4 are siblings
3 and 0 are on the same level
2 is the parent of 4
3 is the left child of 4
1 is the right child of 2
4 and 0 are on the same level
100 is the right child of 3

输出样例：

Yes
Yes
Yes
Yes
Yes
No
No
No

做法（写了特别多的函数去判断）：

测试点1有负数。

测试点2中在找同层次的时候，a和b可能都不在树中。

代码：

1.建树

2.判断所给陈述句

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <map>
using namespace std;const int N = 110;
struct Node
{int val;Node* lchild;Node* rchild;
}space[N];
map<int,int> ha;
int idx = 0;void insert(Node* root,int v)
{if(v < root->val){if(root->lchild == NULL){root->lchild = &space[idx++];root->lchild->val = v;}else insert(root->lchild,v);}else if(v > root->val){if(root->rchild == NULL){root->rchild = &space[idx++];root->rchild->val = v;}else insert(root->rchild,v);}
}
void test(Node* root)
{cout << root->val << " ";if(root->lchild) test(root->lchild);if(root->rchild) test(root->rchild);
}
int convert(string& str,int id)
{int flag = 1;if(str[id] == '-')id++,flag = 0;int res = 0;for(int i = id;i < str.size() && '0' <= str[i] && str[i] <= '9';i++)res = res * 10 + str[i] - '0';if(!flag) res = 0 - res;return res;
}
bool check_sibling(Node* root,int a,int b)
{if(root == NULL) return false;if(root->lchild && root->rchild){if(root->lchild->val == a && root->rchild->val == b)return true;}if(check_sibling(root->lchild,a,b)) return true;if(check_sibling(root->rchild,a,b)) return true;return false;
}
bool check_parent(Node* root,int a,int b)
{if(root == NULL) return false;if(root->lchild){if(root->val == a && root->lchild->val == b) return true;}if(root->rchild){if(root->val == a && root->rchild->val == b) return true;}if(check_parent(root->lchild,a,b)) return true;if(check_parent(root->rchild,a,b)) return true;return false;
}
int dep(Node* root,int t,int cnt)
{if(root == NULL) return 0;if(root->val == t) return cnt;int tmp = dep(root->lchild,t,cnt + 1);if(tmp) return tmp;tmp = dep(root->rchild,t,cnt + 1);if(tmp) return tmp;return 0;
}
bool check_child(Node* root,int a,int b,char st)
{if(root == NULL) return false;if(st == 'l' && root->lchild && root->val == b && root->lchild->val == a)return true;if(st == 'r' && root->rchild && root->val == b && root->rchild->val == a)return true;if(check_child(root->lchild,a,b,st)) return true;if(check_child(root->rchild,a,b,st)) return true;return false;
}
signed main()
{int n = 0;cin >> n;Node* root = &space[idx++];for(int i = 0;i < n;i++){int t = 0;cin >> t;ha[t] = 1;if(!i) root->val = t;else insert(root,t);}cin >> n;string str;getline(cin,str);//test(root);cout << endl;while(n--){getline(cin,str);int a = 0,b= 0;bool flag = false;if(str.find("root") != -1){a = convert(str,0);if(root->val == a) flag = true;}else if(str.find("siblings") != -1){a = convert(str,0);b = convert(str,str.find("and") + 4);if(a > b) swap(a,b);if(check_sibling(root,a,b)) flag = true;}else if(str.find("parent") != -1){a = convert(str,0);b = convert(str,str.find("of") + 3);if(check_parent(root,a,b)) flag = true;}else if(str.find("level") != -1)//测试点1有负数，测试点2存在不在树中的数{a = convert(str,0);b = convert(str,str.find("and") + 4);// cout << dep(root,a,1) << " " << dep(root,b,1) << endl;// cout << a << " " << ha[a] << " " << b << " " << ha[b] << endl;if(ha[a] && ha[b] && dep(root,a,1) == dep(root,b,1)) flag = true;}else if(str.find("child")){a = convert(str,0);b = convert(str,str.find("of") + 3);char st = ' ';if(str.find("left") != -1) st = 'l';else st = 'r';if(check_child(root,a,b,st)) flag = true;}if(flag) puts("Yes");else puts("No");}return 0;
}