文化馆网站建设,长沙网络营销外包哪家好,昆明做网站方案,重庆seo网站策划二叉搜索树或者是一棵空树#xff0c;或者是具有下列性质的二叉树#xff1a; 若它的左子树不空#xff0c;则左子树上所有结点的值均小于它的根结点的值#xff1b;若它的右子树不空#xff0c;则右子树上所有结点的值均大于它的根结点的值#xff1b;它的左、右子树也分… 二叉搜索树或者是一棵空树或者是具有下列性质的二叉树 若它的左子树不空则左子树上所有结点的值均小于它的根结点的值若它的右子树不空则右子树上所有结点的值均大于它的根结点的值它的左、右子树也分别为二叉搜索树。摘自百度百科 给定一系列互不相等的整数将它们顺次插入一棵初始为空的二叉搜索树然后对结果树的结构进行描述。你需要能判断给定的描述是否正确。例如将{ 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 #include iostream
#include string
#include string.h
#include map
using namespace std;const int MAX 1e7 10;
int tree[MAX]; //二叉搜索树
int deepth[MAX]; //结点深度
int tem;
mapint, int num; //键值对应的结点编号void creatTree(int x, int d) //建立二叉搜索树
{if (tree[x] 0x3f3f3f3f){tree[x] tem;num.insert(make_pair(tem, x));deepth[x] d;}else{if (tem tree[x])creatTree(x * 2, d 1);elsecreatTree(x * 2 1, d 1);}return;
}int main()
{int n; cin n;memset(tree, 0x3f, sizeof(tree)); //将每个元素初始化为0x3f3f3f3ffor (int i 0; i n; i){cin tem;creatTree(1, 1);}int k; cin k;while (k--){string str;int a, b;cin a str;if (str and){cin b str str;if (str siblings){if (num.find(a) num.end() || num.find(b) num.end())cout No endl;else if (num[a] / 2 num[b] / 2)cout Yes endl;elsecout No endl;}else{getline(cin, str);if (num.find(a) num.end() || num.find(b) num.end())cout No endl;else if (deepth[num[a]] deepth[num[b]])cout Yes endl;elsecout No endl;}}else{cin str str;if (str root){if (num.find(a) num.end())cout No endl;else if (num[a] 1)cout Yes endl;elsecout No endl;}else if (str parent){cin str b;if (num.find(a) num.end() || num.find(b) num.end())cout No endl;else if (num[a] num[b] / 2)cout Yes endl;elsecout No endl;}else if (str left){cin str str b;if (num.find(a) num.end() || num.find(b) num.end())cout No endl;else if (num[b] * 2 num[a])cout Yes endl;elsecout No endl;}else{cin str str b;if (num.find(a) num.end() || num.find(b) num.end())cout No endl;else if (num[b] * 2 1 num[a])cout Yes endl;elsecout No endl;}}}return 0;
} 注意事项 需要判断被询问的数据是否在树上否则测试点2答案错误。 如有问题欢迎提出。
