二叉搜索树或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别为二叉搜索树。（摘自百度百科）
给定一系列互不相等的整数，将它们顺次插入一棵初始为空的二叉搜索树，然后对结果树的结构进行描述。你需要能判断给定的描述是否正确。例如将{ 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代码
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.util.HashMap;
import java.util.StringTokenizer;
public class Main{
public static void main(String[] args) throws IOException {
Reader.init(System.in);
int n = Reader.nextInt();
HashMap<Integer, Node> map = new HashMap<Integer, Node>();
Node root = new Node();
root.data = Reader.nextInt();
root.fa = null;
map.put(root.data, root);
for (int i = 1; i < n; i++) {
Node temp = new Node();
temp.data = Reader.nextInt();
map.put(temp.data, temp);
insert(root, temp);
}
int m = Reader.nextInt();
int a,b;
for (int i = 0; i < m; i++) {
String str = Reader.nextLine();
String[] s = str.split(" ");
try {
switch (s.length) {
case 4: // root
a = Integer.valueOf(s[0]);
if(map.get(a).fa == null) {
System.out.println("Yes");
}else {
System.out.println("No");
}
break;
case 5:// siblings
a = Integer.valueOf(s[0]);
b = Integer.valueOf(s[2]);
if(map.get(a).fa == map.get(b).fa) {
System.out.println("Yes");
}else {
System.out.println("No");
}
break;
case 6:
a = Integer.valueOf(s[0]);
b = Integer.valueOf(s[5]);
if(map.get(b).fa.data == a) {
System.out.println("Yes");
}else {
System.out.println("No");
}
break;
case 7:
a = Integer.valueOf(s[0]);
b = Integer.valueOf(s[6]);
if(s[3].equals("left")) {
if(map.get(b).left.data == a) {
System.out.println("Yes");
}else {
System.out.println("No");
}
}else {
if(map.get(b).right.data == a) {
System.out.println("Yes");
}else {
System.out.println("No");
}
}
break;
case 8:
a = Integer.valueOf(s[0]);
b = Integer.valueOf(s[2]);
int count = 0;
Node current = map.get(a);
while(current.fa != null) {
count++;
current = current.fa;
}
current = map.get(b);
while(current.fa != null) {
count--;
current = current.fa;
}
if(count == 0) {
System.out.println("Yes");
}else {
System.out.println("No");
}
break;
default:
break;
}
} catch (Exception e) {
System.out.println("No");
}
}
}
static class Node {
int data;
Node fa = null;
Node left = null;
Node right = null;
}
static void insert(Node root, Node val) {
if (val.data < root.data) {
if (root.left == null) {
root.left = val;
val.fa = root;
} else {
insert(root.left, val);
}
} else {
if (root.right == null) {
root.right = val;
val.fa = root;
} else {
insert(root.right, val);
}
}
}
}
// Class for buffered reading int and double values *//*
class Reader {
static BufferedReader reader;
static StringTokenizer tokenizer;
// ** call this method to initialize reader for InputStream *//*
static void init(InputStream input) {
reader = new BufferedReader(new InputStreamReader(input));
tokenizer = new StringTokenizer("");
}
static void init(File file) {
try {
reader = new BufferedReader(new FileReader(file));
} catch (FileNotFoundException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
tokenizer = new StringTokenizer("");
}
// ** get next word *//*
static String next() throws IOException {
while (!tokenizer.hasMoreTokens()) {
// TODO add check for eof if necessary
tokenizer = new StringTokenizer(reader.readLine());
}
return tokenizer.nextToken();
}
static String nextLine() throws IOException {
return reader.readLine();
}
static int nextInt() throws IOException {
return Integer.parseInt(next());
}
static char nextChar() throws IOException {
return next().toCharArray()[0];
}
static float nextFloat() throws IOException {
return Float.parseFloat(next());
}
}