03 isomorphism of tree 1

03- Trees 1 The isomorphism of trees

fraction 25

author Chen Yue

Company Zhejiang University

Given two trees T1 and T2. If T1 It can be changed into... By exchanging children several times T2, Then we call the two trees “ isomorphism ” Of . For example, figure 1 The two given trees are isomorphic , Because we put one of the tree nodes A、B、G After the exchange of left and right children , You get another tree . Diagram 2 It's not isomorphic .

chart 1
chart 2

Here are two trees , Please judge whether they are isomorphic .

Input format :

Type to give 2 Information about a binary tree . For every tree , First, give a nonnegative integer in a row N (≤10), That is, the number of nodes in the tree （ In this case, we assume that the node is from 0 To N−1 Number ）; And then N That's ok , The first i Line corresponding to No i Nodes , Give the 1 English capital letters 、 The number of the left child node 、 The number of the right child node . If the child node is empty , In the corresponding position “-”. The data given is separated by a space . Be careful ： Make sure that the letters stored in each node are different .

Output format :

If two trees are isomorphic , Output “Yes”, Otherwise output “No”.

sample input 1（ Corresponding graph 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 -

sample output 1:

Yes

sample input 2（ Corresponding graph 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

sample output 2:

No

 

    tydedef Is to replace the existing type , That is to give a name to an existing type ;
    #define Put the variable name in the middle , No semicolon at the end ;

Node is from 0 To n-1 Numbered starting , Except that the subscript of the root node does not appear in the input , The numbers of other nodes appear in the input , So let's use a hash Array to find the number of the root node .

coding：

/**
    tydedef  Is to replace the existing type , That is to give a name to an existing type ;
    #define  Put the variable name in the middle , No semicolon at the end ;
*/

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

typedef char ElementType;
typedef int Tree;
const int maxn =10;
#define Null -1
struct TNode
{
    ElementType data;
    Tree left,right;
}T1[maxn],T2[maxn];
bool hashT[maxn]={0};

Tree CreateTree(TNode *T);
bool Issomer(Tree R1,Tree R2);
int main()
{
    Tree R1,R2;
    R1=CreateTree(T1);
    R2=CreateTree(T2);
    if(Issomer(R1,R2))
        cout << "Yes\n";
    else
        cout << "No\n";
    return 0;
}

// Node is from 0 To n-1 Numbered starting , Except that the subscript of the root node does not appear in the input , The numbers of other nodes appear in the input ,
// So let's use a hash Array to find the number of the root node .
Tree CreateTree(TNode *T) // Return the head node of the tree 
{
    Tree R=Null;
    int n;
    scanf("%d",&n);
    getchar();
    if(n)
    {
        memset(hashT,0,sizeof(hashT));
        char d,l,r;
        for(int i=0;i<n;++i)
        {
            scanf("%c %c %c",&d,&l,&r);
            T[i].data=d;
            if(l!='-')
            {
                int pos=l-'0';
                T[i].left=pos;
                hashT[pos]=1;
            }
            else
                T[i].left=Null;

            if(r!='-')
            {
                int pos=r-'0';
                T[i].right=pos;
                hashT[pos]=1;
            }
            else
                T[i].right=Null;
            getchar();
        }
        for(int i=0;i<n;++i)
        {
            if(hashT[i]==0)
            {
                R=i;
                break;
            }
        }

    }
    return R;
}

bool Issomer(Tree R1,Tree R2)
{
    if(R1==Null&&R2==Null)
        return true;  // If both trees are empty 
    else if((R1==Null&&R2!=Null)||(R1!=Null&&R2==Null))
        return false; // If a tree is empty 
    else if(T1[R1].data!=T2[R2].data)
        return false;   // If the values of the root nodes of two trees are not equal 
    else if(T1[T1[R1].left].data==T2[T2[R2].left].data) // If the left nodes of two trees are equal , There is no need to exchange left and right nodes 
        return Issomer(T1[R1].left,T2[R2].left) && Issomer(T1[R1].right,T2[R2].right);
    else // Switch left and right nodes 
        return Issomer(T1[R1].left,T2[R2].right) && Issomer(T1[R1].right,T2[R2].left);
}