L3-016 二叉搜索树的结构 （30 分）

二叉搜索树或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别为二叉搜索树。（摘自百度百科）

给定一系列互不相等的整数，将它们顺次插入一棵初始为空的二叉搜索树，然后对结果树的结构进行描述。你需要能判断给定的描述是否正确。例如将{ 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，每句占一行。

Solution：

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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
#include<iostream>
#include<vector>
#include<cstring>
#include<cstdio>
using namespace std;

struct TreeNode{
	int val;
	TreeNode* left;
	TreeNode* right;
	TreeNode(int x): val(x), left(NULL), right(NULL){} 
};

int rootval;

void insertNode(TreeNode* root, int val){
	if(!root) return;
	if(root->val > val){
		if(root->left){
			insertNode(root->left,val);
		}else{
			TreeNode* t = new TreeNode(val);
			root->left = t; 
		}
	}else if(root->val < val){
		if(root->right){
			insertNode(root->right,val);
		}else{
			TreeNode* t = new TreeNode(val);
			root->right = t; 
		}
	}
}

bool isContainNode(TreeNode* root, int val){
	if(!root) return false;
	if(root->val == val) return true;
	if(root->val > val) return isContainNode(root->left,val);
	else return isContainNode(root->right,val);
}

void printTree(TreeNode* root){
	if(!root) return;
	cout << root->val <<"";
	printTree(root->left);
	printTree(root->right);
}

bool isRoot(int val){
	return val == rootval;
}

TreeNode* parent(TreeNode *root, int child){
	if(!isContainNode(root,child) || root->val == child) return NULL;
	TreeNode* res = NULL;
	while(1){
		if(!root) return NULL;
		if((root->left && root->left->val == child) || (root->right && root->right->val == child)){
			res = root;
			break;
		}else if(root->val > child){
			root = root->left;
		}else if(root->val < child){
			root = root->right;
		}
	}
	return res;
}

bool isSibling(TreeNode* root, int valA, int valB){
	if(!root) return false;
	if(valA == root->val || valB == root->val) return false;
	//找到A的父亲
	TreeNode* t = parent(root, valA); 
	
	if(t){
		if(t->left && t->left->val == valA ){
			return t->right && t->right->val == valB;
		} 
		else if(t->right && t->right->val == valA ){
			return t->left && t->left->val == valB;
		}else{
			return false;
		}
	}
	return false;
}


int getDepth(TreeNode* root, int val){
	
	if(root->val == val) return 0;
	if(root->val > val) return 1 + getDepth(root->left,val);
	else return 1 + getDepth(root->right,val);
}

bool isSameLevel(TreeNode* root, int A, int B){
//	A != B && 
	return isContainNode(root,A) && isContainNode(root,B) && getDepth(root, A) == getDepth(root, B);
}

void pirntMassage(bool info){
	if(info){
		cout << "Yes" << endl;
	}else{
		cout << "No" <<endl;
	}
}

bool isParent(TreeNode* root, int parentVal, int childVal){
	if(parent(root, childVal) == NULL) return false;
	return parentVal == parent(root, childVal)->val;
}
bool isLeftChild(TreeNode* root, int parentVal, int leftChildVal){
	if(parent(root, leftChildVal) == NULL) return false;
	TreeNode* p = parent(root, leftChildVal);
	return parentVal == p->val && p->left->val == leftChildVal;
}

bool isRightChild(TreeNode* root, int parentVal, int rightChildVal){
	if(parent(root, rightChildVal) == NULL) return false;
	TreeNode* p = parent(root, rightChildVal);
	return parentVal == p->val && p->right->val == rightChildVal;
}

int main(){
	int c;
	cin >> c;
	if(c <= 0) return 0;
	
	cin >> rootval;
	TreeNode* root = new TreeNode(rootval);
	for(int i = 1; i < c; i++){
		int a;
		cin >> a;
		insertNode(root, a);
	}
	
	cin >> c;
	getchar();
	int rootV,siblingA,siblingB, parentv, childv,leftchildv,rightchildv,samelevelA,samelevelB;
 	for(int i = 0 ; i < c; i++){
 		
		char state[100];
		int q = 0;
		char ch;
		while((ch = getchar()) != '\n') state[q++] = ch;
		state[q] = '\0';
		if(strstr(state,"root")){
			sscanf(state,"%d is the root",&rootV);
			pirntMassage(isRoot(rootV));
		}else if(strstr(state,"siblings")){
			sscanf(state,"%d and %d are siblings",&siblingA,&siblingB);
			pirntMassage(isSibling(root,siblingA,siblingB));
		}else if(strstr(state,"same")){
			sscanf(state,"%d and %d are on the same level",&samelevelA,&samelevelB);
			pirntMassage(isSameLevel(root,samelevelA,samelevelB));
		}else if(strstr(state,"parent")){
			sscanf(state,"%d is the parent of %d",&parentv,&childv);
			pirntMassage(isParent(root,parentv,childv));
		}else if(strstr(state,"left")){
			sscanf(state,"%d is the left child of %d",&leftchildv,&parentv);
			pirntMassage(isLeftChild(root,parentv,leftchildv));
		}else if(strstr(state,"right")){
			sscanf(state,"%d is the right child of %d",&rightchildv,&parentv);
			pirntMassage(isRightChild(root,parentv,rightchildv));
		}
	}

//	pirntMassage(isRoot(2));
//	pirntMassage(isSibling(root,1,1));
//	pirntMassage(isSameLevel(root, 0,3));
//	pirntMassage(isParent(root, 3,0));
//	pirntMassage(isLeftChild(root, 2,1));
//	pirntMassage(isRightChild(root, 2,4));
	return 0;
}

第一次写这么多功能的代码，很考验耐力。
没什么大的难点，注意考虑代码的重用性。

第一次用sscanf，还不太熟。

有一坑：它认为 3 and 3 are on the same level。我开始写的时候，直接把这种情况否定掉了。看来盲目做条件判断也不是好事。