首页 > 代码库 > 5-3 树的同构 (25分)

5-3 树的同构 (25分)

2024-09-03 13:37:01   217人阅读

5-3 树的同构   (25分)

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

 

技术分享

 

图1

技术分享

图2

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

输入格式:

输入给出2棵二叉树树的信息。对于每棵树，首先在一行中给出一个非负整数NN (\le 10≤10)，即该树的结点数（此时假设结点从0到N-1N?1编号）；随后NN行，第ii行对应编号第ii个结点，给出该结点中存储的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
 1 #include <iostream>
 2 using namespace std;
 3 #define MaxTree 10
 4 
 5 typedef char ElementType;
 6 typedef int Tree;
 7 struct TreeNode
 8 {
 9     ElementType Data;
10     Tree  Left;
11     Tree  Right;
12 } T1[MaxTree], T2[MaxTree];
13 
14 Tree BuildTree(struct TreeNode T[]);
15 bool  Isomorphic(Tree R1, Tree R2);
16 int main()
17 {
18     Tree R1, R2;
19     R1 = BuildTree(T1);
20     R2 = BuildTree(T2);
21     if (Isomorphic(R1, R2))
22         printf("Yes\n");
23     else
24         printf("No\n");
25     
26     return 0;
27 }
28 
29 Tree BuildTree(struct TreeNode T[])
30 {
31     int N;
32     Tree Root;      // 根结点
33     cin>>N;
34     if (N) {
35         int check[N];
36         for (int i = 0; i < N; i++)
37             check[i] = 0;
38         for (int i = 0; i < N; i++) {
39             char c_left, c_right;
40             cin >> T[i].Data >> c_left >> c_right;
41             if (c_left != ‘-‘) {
42                 T[i].Left = c_left - ‘0‘;
43                 check[T[i].Left] = 1;
44             }
45             else {
46                 T[i].Left = -1;
47             }
48             if (c_right != ‘-‘) {
49                 T[i].Right = c_right - ‘0‘;
50                 check[T[i].Right] = 1;
51             }
52             else {
53                 T[i].Right = -1;
54             }
55         }
56         int i;
57         for (i = 0; i < N; i++) {
58             if (!check[i])
59                 break;
60         }
61         Root = i;
62     }
63     else
64         Root = -1;
65     return Root;
66 }
67 
68 bool  Isomorphic(Tree R1, Tree R2)
69 {
70     /* both empty */
71     if ((R1 == -1) && (R2 == -1))
72         return  true;
73     /* one of them is empty */
74     if (((R1 == -1) && (R2 != -1)) || ((R1 != -1) && (R2 == -1)))
75         return  false;
76     /* roots are different */
77     if (T1[R1].Data != T2[R2].Data)
78         return  false;
79     /* both have no left subtree */
80     if ((T1[R1].Left == -1) && (T2[R2].Left == -1))
81         return  Isomorphic(T1[R1].Right, T2[R2].Right);
82     /* no need to swap the left and the right */
83     if (((T1[R1].Left != -1) && (T2[R2].Left != -1))
84         && ((T1[T1[R1].Left].Data) == (T2[T2[R2].Left].Data)))
85         return  (Isomorphic(T1[R1].Left, T2[R2].Left) && Isomorphic(T1[R1].Right, T2[R2].Right));
86     /* need to swap the left and the right  */
87     else
88         return (Isomorphic(T1[R1].Left, T2[R2].Right) && Isomorphic(T1[R1].Right, T2[R2].Left));
89 }

 

 

5-3 树的同构 (25分)


联系
我们