PTA数据结构与算法题目集(中文) 7-3

PTA数据结构与算法题目集(中文) 7-3 树的同构

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

图1

图2

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

输入格式:

输入给出2棵二叉树树的信息。对于每棵树，首先在一行中给出一个非负整数

输出格式:

如果两棵树是同构的，输出“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


题目分析：首先可以通过树最大大小 为10来建树---利用结构体数组存储树 对于判断2个树是否同构 可以递归的进行判断 对根节点判断完成后 分成两种情况继续判断----一种是 两颗树的左右节点正好匹配 一种是两棵树的左右节点匹配相反 这样判断下去 直到遇到不存在的结点为止

 1 #define _CRT_SECURE_NO_WARNINGS   
 2 #include<stdio.h>
 3 #include<stdlib.h>
 4 #include<malloc.h>
 5 typedef int LChild;
 6 typedef int RChild;
 7 
 8 typedef struct TNode
 9 {
10     char Data;
11     LChild Lc;
12     RChild Rc;
13 }Tree[10];
14 
15 Tree A;
16 Tree B;
17 
18 int Collected[10];
19 void InitiliazeCollected()
20 {
21     for (int i = 0; i < 10; i++)
22         Collected[i] = 0;
23 }
24 int  BuildTree(Tree A)
25 {
26     InitiliazeCollected();
27     int N;
28     char c,n1, n2;
29     scanf("%d
", &N);
30     if (N == 0)
31         return -1;
32     for (int i = 0; i < N; i++)
33     {
34         scanf("%c %c %c
", &c, &n1, &n2);
35         A[i].Data = c;
36         if (n1 != '-')
37         {
38             A[i].Lc = n1 - '0';
39             Collected[n1 - '0'] = 1;
40         }
41         else
42             A[i].Lc = -1;
43         if (n2 != '-')
44         {
45             A[i].Rc = n2 - '0';
46             Collected[n2 - '0'] = 1;
47         }
48         else
49             A[i].Rc = -1;
50     }
51     for (int i = 0; i < N; i++)
52         if (!Collected[i])
53             return i;
54 }
55 int Charge(int TreeA, int TreeB)
56 {
57 
58     if (TreeA== -1&&TreeB==-1)
59         return 1;
60     if (A[TreeA].Data == B[TreeB].Data)
61     {
62         if ((Charge(A[TreeA].Lc, B[TreeB].Lc) && Charge(A[TreeA].Rc,B[TreeB].Rc))||((Charge(A[TreeA].Lc,B[TreeB].Rc)&&Charge(A[TreeA].Rc,B[TreeB].Lc))))
63             return 1;
64     }
65     else
66         return 0;
67 }
68 int main()
69 {
70     int TreeA=BuildTree(A);
71     int TreeB=BuildTree(B);
72     if (TreeA == -1 && TreeB == -1)
73         printf("Yes");
74     else if (TreeA == -1&&TreeB!=-1|| TreeB == -1&&TreeA!=-1)
75         printf("No");
76     else if (Charge(TreeA, TreeB))
77         printf("Yes");
78     else
79         printf("No");
80     return 0;
81 }

View Code