二叉搜索树或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别为二叉搜索树。（摘自百度百科）
给定一系列互不相等的整数，将它们顺次插入一棵初始为空的二叉搜索树，然后对结果树的结构进行描述。你需要能判断给定的描述是否正确。例如将{ 2 4 1 3 0 }插入后，得到一棵二叉搜索树，则陈述句如“2是树的根”、“1和4是兄弟结点”、“3和0在同一层上”（指自顶向下的深度相同）、“2是4的双亲结点”、“3是4的左孩子”都是正确的；而“4是2的左孩子”、“1和3是兄弟结点”都是不正确的。
输入在第一行给出一个正整数N（≤），随后一行给出N个互不相同的整数，数字间以空格分隔，要求将之顺次插入一棵初始为空的二叉搜索树。之后给出一个正整数M（≤），随后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，每句占一行。
#include <cstdio>#include <cstring>#include <string>#include <vector>#include <cstdlib>#include <algorithm>#include <iostream>using namespace std;const int maxn = 220;int BST[maxn];int n,m;typedef struct TNode{ int data; struct TNode *left,*right;}TNode,*BiTree;void buildtree(BiTree &T,int x)//建树{ if(T==NULL) { T=(BiTree)malloc(sizeof(BiTree)); T->data=x; T->left=NULL; T->right=NULL; } else if(x<T->data) { buildtree(T->left,x) ; } else if(x>T->data) { buildtree(T->right,x); }}bool Search_BST(BiTree &T,int x){ if(T==NULL||T->data==x) return true; if(T->data>x) return Search_BST(T->left,x); else return Search_BST(T->right,x);}int Get_value(BiTree &T){ if(T==NULL) return -1; return T->data;}bool Judge_Parent(BiTree T,int x,int y){ if(T==NULL) { return false; } if(T->data==x) { if(Get_value(T->left)==y||Get_value(T->right)==y) return true; } return (Judge_Parent(T->left,x,y)||Judge_Parent(T->right,x,y));}bool Judge_LChild(BiTree T,int x,int y){ if(T==NULL) { return false; } if(T->data==y) { if(Get_value(T->left)==x) return true; } return (Judge_LChild(T->left,x,y)||Judge_LChild(T->right,x,y));}bool Judge_RChild(BiTree T,int x,int y){ if(T==NULL) { return false; } if(T->data==y) { if(Get_value(T->right)==x) return true; } return (Judge_RChild(T->left,x,y)||Judge_RChild(T->right,x,y));}void Height(BiTree& T,int e,int h,int &c){ if(T==NULL) return; if(T->data==e) c=h; Height(T->left,e,h+1,c); Height(T->right,e,h+1,c);}bool Judge_Same(BiTree T,int x,int y){ int f1 , f2; Height(T,x,0,f1); Height(T,y,0,f2); if(f1==f2) return true; return false;}bool Judge_Bother(BiTree T,int x,int y){ if(T==NULL) return false; if(T->left!=NULL&&T->right!=NULL) { if(T->left->data==x&&T->right->data==y) return true; if(T->left->data==x&&T->right->data==y) return true; } Judge_Bother(T->left,x,y); Judge_Bother(T->right,x,y);}int main(){ scanf("%d",&n); BiTree T=NULL; for(int i=0;i<n;i++) scanf("%d",&BST[i]); for(int i=0;i<n;i++) buildtree(T,BST[i]); scanf("%d",&m); int _a,_b,_c; string a,b,c; while(m--) { scanf("%d",&_a); cin>>a; if(a=="is") { cin>>a>>b; if(b=="parent") { cin>>c>>_b; if(Judge_Parent(T,_a,_b)) printf("Yes\n"); else printf("No\n"); continue; } else if(b=="left") { cin>>b>>c; cin>>_b; if(Judge_LChild(T,_a,_b)) printf("Yes\n"); else printf("No\n"); continue; } else if(b=="right") { cin>>b>>c; cin>>_b; if(Judge_RChild(T,_a,_b)) printf("Yes\n"); else printf("No\n"); continue; } else if(b=="root") { if(T!=NULL&&T->data==_a) printf("Yes\n"); else printf("No\n"); continue; } } else if(a=="and") { cin>>_b; cin>>b>>c; if(c=="siblings") { if(Judge_Bother(T,_a,_b)) printf("Yes\n"); else printf("No\n"); continue; } else { getline(cin,b); if(Judge_Same(T,_a,_b)) // 层数相同 printf("Yes\n"); else printf("No\n"); continue; } } }}
转载于:https://www.cnblogs.com/linguiquan/p/9049993.html
