数据结构实验之二叉树一：树的同构 （SDUT 3340）

题解：把原本结构体的左右子树的类型定义成 int 型，用来存放这个结点的左右子树的编号，分别建造两棵二叉树，按个比较，如果在第二棵树中没有找到，那么就不用在判断了。

代码语言：javascript复制

#include <bits/stdc  .h>

using namespace std;

struct node
{
    char data;
    int l,r;
};
struct node t1[20],t2[20];
void build(struct node *t, int n)
{
    for(int i = 0; i < n; i   )
    {
        char s[55];
        scanf("%s", s);
        t[i].data = s[0];
        scanf("%s", s);
        if(s[0] == '-') t[i].l = 100;
        else t[i].l = s[0] - '0';
        scanf("%s", s);
        if(s[0] == '-') t[i].r = 100;
        else t[i].r = s[0] - '0';
    }
}
int ok(int i, int j)
{
    if(t1[t1[i].l].data == t2[t2[j].l].data && t1[t1[i].r].data == t2[t2[j].r].data)
        return 1;
    else if(t1[t1[i].r].data == t2[t2[j].l].data && t1[t1[i].l].data == t2[t2[j].r].data)
        return 1;
    else return 0;
}
int main()
{
    int n,m;
    while(~scanf("%d",&n))
    {
        build(t1,n);
        scanf("%d",&m);
        build(t2,m);
        int f = 0,i,j;
        for(i = 0; i < n; i   )
        {
            for( j = 0; j < m; j   )
            {
                if(t1[i].data == t2[j].data)
                {
                    if(ok(i,j)==0){
                        f = 1;
                        break;
                    }
                    else break;
                }
            }
            if(f)break;
            if(j >= m){f = 1;break;}
        }
        if(f)printf("Non");
        else printf("Yesn");
    }
    return 0;
}

二叉树 int

0 人点赞