二叉搜索树或者是一棵空树,或者是具有下列性质的二叉树: 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值;若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值;它的左、右子树也分别为二叉搜索树。(摘自百度百科)
给定一系列互不相等的整数,将它们顺次插入一棵初始为空的二叉搜索树,然后对结果树的结构进行描述。你需要能判断给定的描述是否正确。例如将{ 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
,每句占一行。
输入样例: 1 2 3 4 5 6 7 8 9 10 11 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
输出样例: 1 2 3 4 5 6 7 8 Yes Yes Yes Yes Yes No No No
思路 建立结构体Tree中存储每个节点的信息(左右子树、双亲、下标和深度)。root为树的根,mp查询节点数值对应的下标。
设insert()为插入新节点进入二叉搜索树的函数,按照规则判断左右孩子是否为空(用-1表示),是的话就当成新节点的位置插入。
代码 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 #include <iostream> #include <math.h> #include <algorithm> #include <string.h> #include <map> using namespace std ;const int N=1e3 +5 ;struct stu { int num,parent=-1 ,level,l=-1 ,r=-1 ; }Tree[N]; int root=1 ;map <int ,int > mp;void insert (int x,int i) { int now=root; while (Tree[now].num!=x){ if (x<Tree[now].num){ if (Tree[now].l==-1 ){ Tree[now].l=i; Tree[i].num=x; Tree[i].parent=now; Tree[i].level=Tree[now].level+1 ; } now=Tree[now].l; } else { if (Tree[now].r==-1 ){ Tree[now].r=i; Tree[i].num=x; Tree[i].parent=now; Tree[i].level=Tree[now].level+1 ; } now=Tree[now].r; } } } int main () { int n,m,x; cin >>n>>x; Tree[1 ].num=x; mp[x]=1 ; for (int i=2 ;i<=n;i++){ cin >>x; mp[x]=i; insert(x,i); } cin >>m; int a,b; string s; while (m--){ int flag=0 ; cin >>a>>s; if (s=="is" ){ cin >>s>>s; if (s=="root" ){ if (mp[a]==root) flag=1 ; } else if (s=="parent" ){ cin >>s>>b; if (Tree[mp[b]].parent==mp[a]) flag=1 ; } else if (s=="left" ){ cin >>s>>s>>b; if (Tree[mp[b]].l==mp[a]) flag=1 ; } else if (s=="right" ){ cin >>s>>s>>b; if (Tree[mp[b]].r==mp[a]) flag=1 ; } } else { cin >>b>>s>>s; if (s=="siblings" ){ if (mp[a]&&mp[b]&&Tree[mp[a]].parent==Tree[mp[b]].parent) flag=1 ; } else if (s=="on" ){ cin >>s>>s>>s; if (mp[a]&&mp[b]&&Tree[mp[a]].level==Tree[mp[b]].level) flag=1 ; } } if (flag) cout <<"Yes" <<endl ; else cout <<"No" <<endl ; } return 0 ; }