3340--数据结构实验之二叉树一：树的同构

悠悠 2022-04-22 06:08 144阅读 0赞

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

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

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

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 -  
Sample Output

Yes

#include <stdio.h>
    #include <stdlib.h>
    struct node
    {
        char data;
        int l, r;
    } a[15], b[15];
    
    int main()
    {
        int n, m, i, j, flag;
        char x, y, z;
        while(scanf("%d", &n) != EOF)
        {
            for(i = 0; i < n; i++)
            {
                getchar();//先吃掉回车
                scanf("%c %c %c", &x, &y, &z);
                a[i].data = x;
                if(y == '-')
                    a[i].l = -1;
                else
                    a[i].l = y - '0';
                if(z == '-')
                    a[i].r = -1;
                else
                    a[i].r = z - '0';
            }
            scanf("%d", &m);
            for(i = 0; i < m; i++)
            {
                getchar();
                scanf("%c %c %c", &x, &y, &z);
                b[i].data = x;
                if(y == '-')b[i].l = -1;
                else
                    b[i].l = y - '0';
                if(z == '-')
                    b[i].r = -1;
                else
                    b[i].r = z - '0';
            }
            if(n != m)
            {
                printf("No\n");//结点都不相等肯定不同构
            }
            else
            {
                flag = 1;
                for(i = 0; i < n; i++)
                {
                    for(j = 0; j < m; j++)
                    {
                        if(a[i].data == b[j].data)
                        {
                            if((a[a[i].l].data == b[b[j].l].data && a[a[i].r].data == b[b[j].r].data)||(a[a[i].l].data == b[b[j].r].data && a[a[i].r].data == b[b[j].l].data))
                                break;
                        }
                    }
                    if(j == m)
                    {
                        flag = 0;
                        break;
                    }
                }
                if(flag)
                    printf("Yes\n");
                else
                    printf("No\n");
            }
           //思路把树1里面的所有的结点在树2里面查找，如果对应结点的左子树等于对应结点的左子树，右子树等于右子树，或者左子树等于右子树，右子树等于左子树，则成立。
        }
        return 0;
    }