问题描述
给你两个相同结点个数的树,判断这两颗树是否同构。
题目链接:
https://pintia.cn/problem-sets/15/problems/711
数据范围:N <= 10
样例:
Input:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| 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 -
|
Output:
知识点
同构：
题目描述：
两颗树A, B 若A能够通过若干次左右孩子的互换得到B，则称A B 两棵树同构。
离散数学描述：
若两个树A, B 同构，当且仅当存在一个从A的结点到B的结点的 一对一 映上函数
映上函数：从A到B的函数f称为映上的或满射的，当且仅当对每个b∈B，有元素a∈A使得f（a）=b。如果函数f是映上的，就说它是满射函数。
即:A B为同构树，在A中，结点V和结点W相邻，则在B中，结点f(V)和结点f(W)也相邻。
一般对于多叉树而言,同构的判断就是计算出各个结点的度，并记录后，对可能同构的树做比较，若一一对应，则互为同构树。
此题目为二叉树 需要从题目描述的方式去考虑
切入点：根节点
从根节点出发,依次按结点序号判断当前结点的左右子树是否相同 直到结点全部遍历完全
思想：层序遍历 考虑按照结点->左子树->右子树即可 递归遍历
树的遍历存储经典题目！！！
题目做法
存储树的结构
N<=10 可以直接结构体数组存储 结构体成员变量有三个：当前结点 左孩子结点 右孩子结点
1
2
3
4
5
6
| struct bintree
{
char ch;
int lchild;
int rchild;
};
|
寻找根节点
采用一种边建树边标记的做法。
根节点：该结点不作为子结点在其他子树中出现 所以我么只需要判断某一个结点是否在其他结点的左右孩子结点中出现即可。
具体做法：
读入时，用一个vis数组存储当前结点是否存在孩子结点。首先初始化为0。
每次读入样例存储再遍历时，判断其左右孩子结点是否为 ‘-’ ，若不为空，则在结构体数组中存储元素的ch信息，并将vis数组中对于该节点的值标记为1。
最后遍历vis数组，按照结点的序号开始遍历，当vis为0时，该节点即为根节点。
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
| int build(bintree T[])
{
int root = -1;
int n;
char i1, i2;
scanf("%d", &n);
if(n)
{
int vis[maxn];
for(int i = 0; i < n; i++)
vis[i] = 0;
for(int i = 0; i < n; i++)
{
getchar();
scanf("%c %c %c", &T[i].ch, &i1, &i2);
if(i1 != '-')
{
T[i].lchild = i1 - '0';
vis[T[i].lchild] = 1;
}
else
T[i].lchild = -1;
if(i2 != '-')
{
T[i].rchild = i2 - '0';
vis[T[i].rchild] = 1;
}
else
T[i].rchild = -1;
}
for(int i = 0; i < n ; i++)
{
if(vis[i] == 0)
{
root = i;
break;
}
}
}
return root;
}
|
判断两课树是否同构
树空的情况
0.若两个树均为空树时，显然同构。
1.若一棵树为空，另一棵树不为空，则显然不同构。
树不为空的情况
0.两棵树根节点的值不同，显然不同构。
1.两个树的根节点的值相等，则继续比较左左孩子和右右孩子。（若都同构，则树同构）
2.两个树的根节点的值相等，但左左孩子和右右孩子不同构，则继续比较左右孩子和右左孩子。（若都同构，则树同构）
3.两个树的根节点的值相等，但左左孩子和右右孩子不同构，而左右孩子和右左孩子亦不同构，则显然不同构。
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
| bool is_isomorphic(int tree1, int tree2)
{
if(tree1 == -1 && tree2 == -1)
{
return true;
}
else if(tree1 == -1 && tree2 != -1)
{
return false;
}
else if(tree1 != -1 && tree2 == -1)
{
return false;
}
else if(T1[tree1].ch != T2[tree2].ch)
{
return false;
}
else if((is_isomorphic(T1[tree1].lchild, T2[tree2].lchild) && is_isomorphic(T1[tree1].rchild, T2[tree2].rchild)))
{
return true;
}
else if((is_isomorphic(T1[tree1].lchild, T2[tree2].rchild) && is_isomorphic(T1[tree1].rchild, T2[tree2].lchild)))
{
return true;
}
return false;
}
|
总结点
[ ] 0. 样例递归建树中，getchar的插入位置(在不用cin读入的情况下)
[ ] 1. vis数组中找到第一个后，直接break。（因为是按照结点的序号来查找的）
[ ] 2. 对于该题来说，题目表明序号简便后，可以将结构体中的左右孩子定义成int类型不必采用传统的递归定义。
[ ] 4. 判断同构时，不要忘记空树的情况。（建树时可直接判断然后返回-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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
| #include <bits/stdc++.h>
#define debug(ch,a,b) {printf("Data: %c Lchild: %c Rchild: %c\n", ch, a, b);}
using namespace std;
const int maxn = 10 + 5;
struct bintree
{
char ch;
int lchild;
int rchild;
}T1[maxn], T2[maxn];
int build(bintree T[])
{
int root = -1;
int n;
char i1, i2;
scanf("%d", &n);
if(n)
{
int vis[maxn];
for(int i = 0; i < n; i++)
vis[i] = 0;
for(int i = 0; i < n; i++)
{
getchar();
scanf("%c %c %c", &T[i].ch, &i1, &i2);
if(i1 != '-')
{
T[i].lchild = i1 - '0';
vis[T[i].lchild] = 1;
}
else
T[i].lchild = -1;
if(i2 != '-')
{
T[i].rchild = i2 - '0';
vis[T[i].rchild] = 1;
}
else
T[i].rchild = -1;
}
for(int i = 0; i < n ; i++)
{
if(vis[i] == 0)
{
root = i;
break;
}
}
}
return root;
}
bool is_isomorphic(int tree1, int tree2)
{
if(tree1 == -1 && tree2 == -1)
{
return true;
}
else if(tree1 == -1 && tree2 != -1)
{
return false;
}
else if(tree1 != -1 && tree2 == -1)
{
return false;
}
else if(T1[tree1].ch != T2[tree2].ch)
{
return false;
}
else if((is_isomorphic(T1[tree1].lchild, T2[tree2].lchild) && is_isomorphic(T1[tree1].rchild, T2[tree2].rchild)))
{
return true;
}
else if((is_isomorphic(T1[tree1].lchild, T2[tree2].rchild) && is_isomorphic(T1[tree1].rchild, T2[tree2].lchild)))
{
return true;
}
return false;
}
int main(void)
{
int root1, root2;
root1 = build(T1);
root2 = build(T2);
bool flag = is_isomorphic(root1, root2);
if(flag)
{
printf("Yes\n");
}
else
{
printf("No\n");
}
return 0;
}
|
