L3-016. 二叉搜索树的结构
二叉搜索树或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别为二叉搜索树。（摘自百度百科）
给定一系列互不相等的整数，将它们顺次插入一棵初始为空的二叉搜索树，然后对结果树的结构进行描述。你需要能判断给定的描述是否正确。例如将{ 2 4 1 3 0 }插入后，得到一棵二叉搜索树，则陈述句如“2是树的根”、“1和4是兄弟结点”、“3和0在同一层上”（指自顶向下的深度相同）、“2是4的双亲结点”、“3是4的左孩子”都是正确的；而“4是2的左孩子”、“1和3是兄弟结点”都是不正确的。
输入格式：
输入在第一行给出一个正整数N（<= 100）【根据Time的先后次序进行建树，可以将数组大小大大压缩到200即可，Time表示其建立时的时间次序，lson和rson表示其左右节点建立的时间】，随后一行给出N个互不相同的整数，数字间以空格分隔，要求将之顺次插入一棵初始为空的二叉搜索树。之后给出一个正整数M（<= 100），随后M行，每行给出一句待判断的陈述句。陈述句有以下6种：
- 1、"A is the root"，即"A是树的根"；
- 2、"A and B are siblings"，即"A和B是兄弟结点"；
- 3、"A is the parent of B"，即"A是B的双亲结点"；
- 4、"A is the left child of B"，即"A是B的左孩子"；
- 5、"A is the right child of B"，即"A是B的右孩子"；
- 6、"A and B are on the same level"，即"A和B在同一层上"。
- 【注意观察，其实是有规律的！只有2和4的第二个单词是“and”——第二个单词开头不同；排除2和4后，1/3/4/5的第四个单词都不相同，值得注意的是“root”和“right”的第一个单词相同，所以需要判断两位！】
题目保证所有给定的整数都在整型范围内。
输出格式：
对每句陈述，如果正确则输出“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 【这个100需要特别关注一下！！题目说的数据要求在整形范围内，所以需要考虑这种不在二叉搜索树中的超大数据的特殊情况，需要加以特殊判断！！】
AC题解：
其实跟二叉树也没啥区别，就是在建树时按照左小右大的顺序来建立的！链表其实更好，有必要学学！
#include<iostream> #include<stdio.h> #include<string.h> #include<math.h> #include<algorithm> #include<queue> #include<set> #include<vector> #include<string> #include<stack> #define inf 0x3f3f3f3f using namespace std; #define N 308 //需要多开一倍，在出现斜二叉树的情况下 #define ll long long struct node{ int data; int level; int lson,rson; node(int data=inf,int level=-1,int lson=-inf,int rson=-inf):data(data),level(level),lson(lson),rson(rson){} }a[N]; int Time; void BST_insert(int i,int val,int level){//i表示需要插入的节点的编号 if(a[i].data==inf){//表示当前数据需要插入的位置 a[i]=node(val,level,1+Time,2+Time); Time+=2; return ; } if(val>a[i].data){//大的向右边 BST_insert(a[i].rson,val,level+1); }else if(val<a[i].data){//小的向左边 BST_insert(a[i].lson,val,level+1); } } int fact_siblings(int i,int x,int y){//判断x，y是否是兄弟节点 if(a[i].data!=inf){ if(a[a[i].lson ].data!=inf){//保证当前节点i 一定有两个子节点 if( a[a[i].lson ].data==x&&a[a[i].rson].data==y) return 1; if( a[a[i].lson ].data==y&&a[a[i].rson].data==x) return 1; } return fact_siblings(a[i].lson,x,y)||fact_siblings(a[i].rson,x,y); } return 0; } int fact_level(int i,int x){ if(a[i].data==inf)return -1; if(a[i].data!=x){ int ans1,ans2; if(ans1=fact_level(a[i].rson,x),ans1!=-1) return ans1; if(ans2=fact_level(a[i].lson,x),ans2!=-1) return ans2; } else{ return a[i].level; } return -1;//找不到的情况 } int fact_pa(int i,int x,int y){//枚举每个双亲节点，判断x是y的双亲节点 if(a[i].data==inf) return 0; if(a[i].data!=x){ return fact_pa(a[i].lson,x,y)||fact_pa(a[i].rson,x,y); } else{ int l=a[i].lson,r=a[i].rson; if(a[l].data==y||a[r].data==y)return 1; else return 0; } return 0; } int fact_left(int i,int x,int y){//枚举每个双亲节点，判断x是y的左节点？ if(a[i].data==inf)return 0; if(a[i].data==y){ if(a[a[i].lson].data==x)return 1; else return 0; }else{ return fact_left(a[i].lson,x,y)||fact_left(a[i].rson,x,y); } return 0; } int fact_right(int i,int x,int y){//判断x是y的右节点否？ if(a[i].data==inf)return 0; if(a[i].data==y){ if(a[a[i].rson].data==x)return 1; else return 0; }else{ return fact_right(a[i].lson,x,y)||fact_right(a[i].rson,x,y); } return 0; } void solve(int m){ int x,y; char ch[15]; for(int i=1;i<=m;i++){ scanf("%d",&x); scanf("%s",ch); if(ch[0]=='a'){//兄弟节点或者在同一层上 scanf("%d%*s%s",&y,ch); if(ch[0]=='s'){ if(fact_siblings(1,x,y))printf("Yes "); else printf("No "); }else{ scanf("%s%*s%*s",ch); if(fact_level(1,x)==-1||fact_level(1,y)==-1) printf("No "); else if(fact_level(1,x)==fact_level(1,y))printf("Yes "); else printf("No "); } } else{ scanf("%*s%s",ch); if(ch[0]=='r'&&ch[1]=='o'){ if(a[1].data==x)printf("Yes "); else printf("No "); } else if(ch[0]=='p'){ scanf("%*s%d",&y); if(fact_pa(1,x,y))printf("Yes "); else printf("No "); } else if(ch[0]=='l'){ scanf("%*s%*s%d",&y); if(fact_left(1,x,y))printf("Yes "); else printf("No "); } else if(ch[0]=='r'){ scanf("%*s%*s%d",&y); if(fact_right(1,x,y))printf("Yes "); else printf("No "); } } } } void debug(int i){ if(a[i].data==inf)return ; printf("i=%d level=%d val=%d ",i,a[i].level,a[i].data); debug(a[i].lson); debug(a[i].rson); } int main(){ int n,m,val; Time=1; scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d",&val); BST_insert(1,val,1); } // debug(1); scanf("%d",&m); solve(m); return 0; }