二叉排序树 SDUTOJ 2482

发表于 | 分类于
字数统计: 605 word | 阅读时长 ≈ 3 min
problem:

点击跳转到题目

understand:

学了二叉树，得知先序和中序遍历或者后序和中序遍历都可以唯一确定一颗二叉树，所以这里我们采用求先序序列进行比较的方法。因为二叉排序树的中序遍历一定是递增序列都一样，所以此题只需比较每棵树的先序序列即可。

code:
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
 #include<iostream>
 #include<algorithm>
 #include<string>
using namespace std;
typedef struct node{
	int data;
	struct node* left;
	struct node* right;
}*tree;
int z[11];
int ccount;
void Inserttree(tree &t, int key){
	tree f, p = t;
	//寻找待插入的节点的位置，用f记录待插入节点的父结点
	while (p){
		if (p->data == key){
			return;
		}
		else{
			f = p;
			if (p->data > key){
				p = p->left;
			}
			else{
				p = p->right;
			}
		}
	}
	//创建新结点，插入
	p = (tree)malloc(sizeof(node));
	p->data = key;
	p->left = p->right = NULL;
	if (t == NULL){
		t = p;
	}
	else{
		if (f->data > key){
			f->left = p;
		}
		else{
			f->right = p;
		}
	}
}
//创建二叉排序树
tree CreateTree(int a[]){
	tree t = NULL;
	int key;
	for (int i = 0; i < 9; i++){
		Inserttree(t, a[i]);
	}
	return t;
}
//先序遍历
void traveltree(tree t){
	if (t != NULL){
		z[ccount++] = t->data;
		traveltree(t->left);
		traveltree(t->right);
	}
}
int main(){
	tree t = NULL;
	int n;
	while (cin >> n&&n != 0){
		ccount = 0;
		string s = "";
		cin >> s;
		int b[11],c[11],d[11];
		//下面是 输入的第一串字符 构建二叉排序树并先序遍历后 得到的数组 c
		for (int i = 0; i <s.length();i++){
			b[i] = s[i] - '0';
		}
		t=CreateTree(b);
		traveltree(t);
		for (int i = 0; i < s.length(); i++){
			c[i] = z[i];   //前序遍历
		}
		//
		for (int i = 0; i < n; i++){
			t = NULL;
			ccount = 0;
			cin >> s;
			//下面是 输入的要进行比较的字符串 构建二叉排序树并先序遍历后 得到的数组 d
			for (int i = 0; i <s.length(); i++){
				b[i] = s[i] - '0';
			}
			t = CreateTree(b);
			traveltree(t);
			for (int i = 0; i < s.length(); i++){
				d[i] = z[i];   //前序遍历
			}
			//下面是比较两个树 先序遍历的结果 c和d ，相同则YES ，不同则NO
			int flag = 0;
			for (int i = 0; i < s.length(); i++){
				if (c[i] != d[i]){
					cout << "NO" << endl;
					flag = 1;
					break;
				}
			}
			if (!flag){
				cout << "YES" << endl;
			}
		}
	}
	cout << endl;
}
0%