HAPPY_2018 Summer_Week03

  1. 7-1 是否同一棵二叉搜索树(25 分)
  2. 7-2 还原二叉树(25 分)
  3. 7-3 树的同构(25 分)
  4. 7-4 朋友圈(25 分)20/25
  5. 7-6 是否完全二叉搜索树(30 分)

7-1 是否同一棵二叉搜索树(25 分)

给定一个插入序列就可以唯一确定一棵二叉搜索树。然而,一棵给定的二叉搜索树却可以由多种不同的插入序列得到。例如分别按照序列{2, 1, 3}和{2, 3, 1}插入初始为空的二叉搜索树,都得到一样的结果。于是对于输入的各种插入序列,你需要判断它们是否能生成一样的二叉搜索树。

输入格式:

输入包含若干组测试数据。每组数据的第1行给出两个正整数N (≤10)和L,分别是每个序列插入元素的个数和需要检查的序列个数。第2行给出N个以空格分隔的正整数,作为初始插入序列。最后L行,每行给出N个插入的元素,属于L个需要检查的序列。

简单起见,我们保证每个插入序列都是1到N的一个排列。当读到N为0时,标志输入结束,这组数据不要处理。

输出格式:

对每一组需要检查的序列,如果其生成的二叉搜索树跟对应的初始序列生成的一样,输出“Yes”,否则输出“No”。

输入样例:

4 2
3 1 4 2
3 4 1 2
3 2 4 1
2 1
2 1
1 2
0

输出样例:

Yes
No
No

我在网上查了发现有三种思路,我自己的思路是最朴素最暴力的一种,就是两个序列分别建树,然后对比是否相同.有一点需要注意的是这个树可能是一棵斜向的搜索树,也就是给定的序列是递增的,所以说在检索时,检索的长度时给定的序列长度n的四倍.

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
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int BST1[1000000];
int BST2[1000000];
long long n;

void Build(int k,int data,int* BST) {
if (data >= BST1[k]) {
if (BST[2 * k + 1] == -1) {
BST[2 * k + 1] = data;
} else {
Build(k * 2 + 1, data,BST);
}
} else {
if(BST[2 * k] == -1) {
BST[2 * k] = data;
} else {
Build(2 * k, data,BST);
}
}
}


int main(int argc, const char * argv[]) {
long long L;
while (scanf("%lld",&n) != EOF && n) {
memset(BST1,-1,sizeof(BST1));
int x;
scanf("%lld",&L);
scanf("%d",BST1 + 1);
for (int i = 2; i <= n; i++) {
scanf("%d",&x);
Build(1, x, BST1);
}
while (L--) {
memset(BST2,-1,sizeof(BST2));
scanf("%d",BST2 + 1);
for(int i = 2; i <= n; i++) {
scanf("%d",&x);
Build(1, x, BST2);
}
int i;
for (i = 1; i <= 4 * n; i++) {
if (BST1[i] != BST2[i]) {
break;
}
}
if (i == 4 * n + 1) {
puts("Yes");
} else {
puts("No");
}
}
}
return 0;
}

第二种思路是根据根节点把序列分为左右两个字树

例如 3 1 2 4 和 3 4 1 2

这里分别划成了 {1, 2} 3 {4} 和 {1, 2} 3 {4}

如果是 3 1 2 4 和 3 2 4 1

则是划成了 {1, 2} 3 {4} 和 {2 , 1} 3 {4}

如此便可以判断是否是同一棵树

第三种是建树然后比较两个树的节点是否一样.

7-2 还原二叉树(25 分)

给定一棵二叉树的先序遍历序列和中序遍历序列,要求计算该二叉树的高度。

输入格式:

输入首先给出正整数N(≤50),为树中结点总数。下面两行先后给出先序和中序遍历序列,均是长度为N的不包含重复英文字母(区别大小写)的字符串。

输出格式:

输出为一个整数,即该二叉树的高度。

输入样例:

9
ABDFGHIEC
FDHGIBEAC

输出样例:

5

这个是上课讲的原题,就是根据先序序列确定树根,然后在中序序列中找到树根的位置就能将中序序列划分为左右子树,然后递归这个过程就能还原这棵树.

确定这棵树的高度就是找左右子树最大高度加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
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>

char pre[10000];
char in[10000];
int n;
typedef struct BST* Tree;

struct BST{
char data;
Tree left;
Tree right;

};


int max (int x,int y) {
return x > y ? x : y;
}
//ABDFGHIEC
//FDHGIBEAC

//1 8
Tree Insert(char* _pre,char* _in,int n) {
Tree t;
if (n <= 0) {
t = NULL;
} else {
t = (Tree)malloc(sizeof(struct BST));
t -> data = *_pre;
char *p = _in;
while(*p != *_pre && p){
p++;
}
int len = p - _in;
t -> left = Insert(_pre + 1, _in, len);
t -> right = Insert(_pre + len + 1, p + 1, n - len - 1);
}
return t;
}

int getHeight(Tree t) {
int l = 0,r = 0;
if (t) {
l = getHeight(t -> left);
r = getHeight(t -> right);
return max(l, r) + 1;
} else {
return 0;
}
}

int main(int argc, const char * argv[]) {
Tree t;
scanf("%d",&n);
getchar();
scanf("%s %s",pre,in);
t = Insert(pre, in, n);
printf("%d",getHeight(t));
return 0;
}

7-3 树的同构(25 分)

给定两棵树T1和T2。如果T1可以通过若干次左右孩子互换就变成T2,则我们称两棵树是“同构”的。例如图1给出的两棵树就是同构的,因为我们把其中一棵树的结点A、B、G的左右孩子互换后,就得到另外一棵树。而图2就不是同构的。


图1

图2

现给定两棵树,请你判断它们是否是同构的。

输入格式:

输入给出2棵二叉树树的信息。对于每棵树,首先在一行中给出一个非负整数N (≤10),即该树的结点数(此时假设结点从0到N−1编号);随后N行,第i行对应编号第i个结点,给出该结点中存储的1个英文大写字母、其左孩子结点的编号、右孩子结点的编号。如果孩子结点为空,则在相应位置上给出“-”。给出的数据间用一个空格分隔。注意:题目保证每个结点中存储的字母是不同的。

输出格式:

如果两棵树是同构的,输出“Yes”,否则输出“No”。

输入样例1(对应图1):

8
A 1 2
B 3 4
C 5 -
D - -
E 6 -
G 7 -
F - -
H - -
8
G - 4
B 7 6
F - -
A 5 1
H - -
C 0 -
D - -
E 2 -

输出样例1:

Yes

输入样例2(对应图2):

8
B 5 7
F - -
A 0 3
C 6 -
H - -
D - -
G 4 -
E 1 -
8
D 6 -
B 5 -
E - -
H - -
C 0 2
G - 3
F - -
A 1 4

输出样例2:

No

建树的过程需要两个临时char类型变量接收左右子树的地址,如果左右子树存在(不是’-‘)那么就在数组中标记出来,因为给定的是连续的一串序列,所以没有被标记的就是根节点.

然后是判断同构 这里分为几种情况:

针对最后一种情况,还有两种情况, 如果左子树相同了,那么就可以去判断右子树,如果不同,那么判断一下左右子树交换之后是否相同.

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
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

struct Node {
char data;
int left;
int right;
}t1[100],t2[100];
int TreeNode[100];
int n;
int Build(struct Node* t) {
int n;
memset(TreeNode,0,sizeof(TreeNode));
scanf("%d",&n);
getchar();
char left,right;
for (int i = 0; i < n; i++) {
scanf("%c %c %c",&t[i].data,&left,&right);
getchar();
if (left == '-') {
t[i].left = -1;
} else {
t[i].left = left - '0';
TreeNode[t[i].left] = 1;
}
if (right == '-') {
t[i].right = -1;
} else {
t[i].right = right - '0';
TreeNode[t[i].right] = 1;
}
}
int root = -1;
for (int i = 0; i < n; i++) {
if (TreeNode[i] == 0) {
root = i;
break;
}
}
return root;
}

int judge(int _t1,int _t2) {
if (_t1 == -1 && _t2 == -1) {
return 1;
}
if ((_t1 == -1 && _t2 != -1) || (_t1 != -1 && _t2 == -1)) {
return 0;
}
if (t1[_t1].data != t2[_t2].data) {
return 0;
}
if (t1[_t1].left == -1 && t2[_t2].left == -1) {
return judge(t1[_t1].right, t2[_t2].right);
}
if (t1[_t1].left != -1 && t2[_t2].left != -1 && t1[t1[_t1].left].data == t2[t2[_t2].left].data) {
return judge(t1[_t1].right, t2[_t2].right) && judge(t1[_t1].left, t2[_t2].left);
} else {
return judge(t1[_t1].right, t2[_t2].left) && judge(t1[_t1].left,t2[_t2].right);
}
}

int main(int argc, const char * argv[]) {
int root1,root2;
root1 = Build(t1);
root2 = Build(t2);
if (judge(root1, root2)) {
puts("Yes");
} else {
puts("No");
}
return 0;
}

7-4 朋友圈(25 分)20/25

某学校有N个学生,形成M个俱乐部。每个俱乐部里的学生有着一定相似的兴趣爱好,形成一个朋友圈。一个学生可以同时属于若干个不同的俱乐部。根据“我的朋友的朋友也是我的朋友”这个推论可以得出,如果A和B是朋友,且B和C是朋友,则A和C也是朋友。请编写程序计算最大朋友圈中有多少人。

输入格式:

输入的第一行包含两个正整数N(≤30000)和M(≤1000),分别代表学校的学生总数和俱乐部的个数。后面的M行每行按以下格式给出1个俱乐部的信息,其中学生从1~N编号:

第i个俱乐部的人数Mi(空格)学生1(空格)学生2 … 学生Mi

输出格式:

输出给出一个整数,表示在最大朋友圈中有多少人。

输入样例:

7 4
3 1 2 3
2 1 4
3 5 6 7
1 6

输出样例:

4

一道并查集的题.

将每个团队的第一个人设为参照,其余的人都是他的子节点,然后遍历查找1——N的每个人的头节点,例如i是一名同学,那么find(i)也就是i的朋友的那个代表,每找到一个find(i)就在数组里对这个下标所在的位置加1,也就是这个圈子的人数加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
#include <stdio.h>

int pre[30010];
int sum[30010];

void init() {
for (int i = 0; i < 30010; i++) {
pre[i] = i;
}
}

int _find(int x) {
if (pre[x] != x) {
pre[x] = _find(pre[x]);
}
return pre[x];
}

void join(int x,int y) {
int fx = _find(x);
int fy = _find(y);
if(fx != fy) {
pre[fx] = fy;
}
}

int main() {

int ans = 0;
int n,k;
scanf("%d%d",&n,&k);
init ();
int x;
for(int i = 0; i < k; i++) {
scanf("%d",&x);
for(int j = 0; j < x; j++) {
scanf("%d",&pre[i]);
}
for(int k = 1; k < x; k++) {
join(pre[0],pre[k]);
}
}
for(int i = 1; i <= n; i++) {
int t = _find(i);
sum[t]++;
if(ans < sum[t]) {
ans = sum[t];
}
}
printf("%d\n",ans);
return 0;
}

7-6 是否完全二叉搜索树(30 分)

将一系列给定数字顺序插入一个初始为空的二叉搜索树(定义为左子树键值大,右子树键值小),你需要判断最后的树是否一棵完全二叉树,并且给出其层序遍历的结果。

输入格式:

输入第一行给出一个不超过20的正整数N;第二行给出N个互不相同的正整数,其间以空格分隔。

输出格式:

将输入的N个正整数顺序插入一个初始为空的二叉搜索树。在第一行中输出结果树的层序遍历结果,数字间以1个空格分隔,行的首尾不得有多余空格。第二行输出YES,如果该树是完全二叉树;否则输出NO。

输入样例1:

9
38 45 42 24 58 30 67 12 51

输出样例1:

38 45 24 58 42 30 12 67 51
YES

输入样例2:

8
38 24 12 45 58 67 42 51

输出样例2:

38 45 24 58 42 12 67 51
NO

做了一部分题,发现BST的题目有时候是不需要真正的用指针去建树的,用数组模拟即可.

完全二叉树的定义: 若设二叉树的深度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第 h 层所有的结点都连续集中在最左边,这就是完全二叉树。

叶子结点只可能在最大的两层上出现,对任意结点,若其右分支下的子孙最大层次为L,则其左分支下的子孙的最大层次必为L 或 L+1;

那么判断思路就是:

那么这道题就是在建完树之后,进行n次循环来输出层序遍历(建好的树的数据的存放顺序就是层序遍历).遇到-1(空节点)计数,理想情况(完全二叉树)正好等于节点数 + 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
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int n;
int tree[1000];
void insert(int index,int data) {

if(tree[index] == -1) {
tree[index] = data;
return;
}
if (data > tree[index]) {
insert(index * 2, data);
} else {
insert(index * 2 + 1, data);
}
}

int main(int argc, const char * argv[]) {
int data;
scanf("%d",&n);
memset(tree, -1, sizeof(tree));
for (int i = 0; i < n; i++) {
scanf("%d",&data);
insert(1, data);
}
int k = 0,i = 0;
while(1)
{
while(tree[i] == -1) i++;
if(k == 0) {
printf("%d",tree[i]);
}
else {
printf(" %d",tree[i]);
}
i++;
k++;
if (k == n) {
break;
}
}

printf("\n");
if (i == n + 1) {
printf("YES\n");
} else {
printf("NO\n");
}
return 0;
}
script>