c++之实现数的同构

冷不防 2022-06-02 06:50 147阅读 0赞

#include<bits/stdc++.h>
    #define Tree int
    #define ElemType char
    using namespace std;
    struct TreeNode
    {
        ElemType element;
        Tree left;
        Tree right;
    }T1[10],T2[10];
    int TreeBuild(struct TreeNode T[])
    {
        int N, i;
        char l, r;
        cin>> N;
        if (N)
        {
            int flag[N];
            for ( i = 0 ; i < N ; i ++)
                flag[i] = 1;
            for ( i = 0 ; i < N ; i ++)
            {
                cin>>T[i].element>>l>>r;
                if (l == '-')
                    T[i].left = -1;
                else
                {
                    T[i].left = l - '0';
                    flag[T[i].left] = 0;
                }
                if (r == '-')
                    T[i].right = -1;
                else
                {
                    T[i].right = r - '0';
                    flag[T[i].right] = 0;
                }
            }
            for ( i = 0 ; i < N ; i ++)
            {
                if (flag[i])
                    return i;
            }
        }
        else
            return -1;
    }
    int judge(Tree R1, Tree R2)
    {
        if ((R1 == -1) && (R2 == -1))//都是空树
            return 1;
        if ( ((R1 == -1)&&( R2 != -1)) || (R1 == -1) && ( R2 != -1))//一个是空树，一个不是空树
            return 0;
        if (T1[R1].element != T2[R2].element)//根结点元素不一样
            return 0;
        if ((T1[R1].left == -1) && (T2[R2].left == -1))//根节点都是只有右孩子，递归判断右孩子树是否同构
            return judge(T1[R1].right, T2[R2].right);
        if (((T1[R1].left != -1) && (T2[R2].left != -1)) && ((T1[T1[R1].left].element) == (T2[T2[R2].left].element)))
            return (judge(T1[R1].left, T2[R2].left) && judge(T1[R1].right, T2[R2].right));
        else
            return (judge(T1[R1].left, T2[R2].right) && judge(T1[R1].right, T2[R2].left));
    }
    int main ()
    {
        Tree R1,R2;
        R1=TreeBuild(T1);
        R2=TreeBuild(T2);
        if(judge(R1,R2))
            cout<<"Yes"<<endl;
        else
            cout<<"No"<<endl;
    }