C Program: Isomorphism of Trees

Isomorphism of Trees

Given two trees T1 and T2. If T1 can become the same as T2 through swapping left and right children several times, then we consider these two trees are "isomorphic". For example, Figure 1 shows two isomorphic trees. If we swap the left and right children of nodes A, B, G of either tree, we can get another tree. But in Figure 2, the trees are not isomorphic.

Figure 1

Figure 2

Now given two trees, please determine whether they are isomorphic.

Input Specification:

Enter the information of 2 binary tree. For each tree, give a non-negative integer N($\le 10$) in the first line, which is the number of the tree nodes(the nodes are numbered from 0 to N - 1). Then N lines follewed, the ith line is related to No.i node, giving a capital letter in English stored in this node, the serial number of the left child node, and that of the right child node. If a child node is empty, give a "-" in the corresponding position. Every two given data should be separated with a space. Note: this question make sure that letters stored in all nodes are different from each other.

Output Specification:

If the two trees are isomorphic, print "Yes". Otherwise, print "No".

Sample Input 1 (Figure 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 (Figure 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

My program is following.

//Isomorphism of Trees

#include <stdio.h>
#include <stdlib.h>

//Tree node and pointer
typedef struct TreeNode
{
    char data;
    int left;
    int right;
} TreeNode, *Tree;

Tree tree1, tree2;//Two trees
Tree BuildTree(Tree* tree);
int Isomorphic(Tree p1, Tree p2);

int main(void)
{
    Tree T1, T2;
    T1 = BuildTree(&tree1);
    T2 = BuildTree(&tree2);
    if (Isomorphic(T1, T2))
    {
        printf("Yes\n");
    }
    else
    {
        printf("No\n");
    }
    return 0;
}

//To build a binary tree
Tree BuildTree(Tree* tree)
{
    int i, N;
    char leftc, rightc;
    scanf("%d", &N);
    getchar();
    *tree = (Tree)malloc(N * sizeof(TreeNode));//Expressing a binary tree through an array of structures
    if (N == 0)
    {
        return NULL;//Empty tree
    }
    int* flag = (int*)malloc(N * sizeof(int));
    for (i = 0; i < N; ++i)
    {
        flag[i] = 1;
    }
    for (i = 0; i < N; ++i)
    {
        scanf("%c %c %c", &((*tree + i)->data), &leftc, &rightc);//Input node information by characters
        getchar();
        if (leftc >= '0'&&leftc <= '9')
        {
            (*tree + i)->left = leftc - '0';//Having left child, transform the character to subscript of left child
            flag[(*tree + i)->left] = 0;
        }
        else
        {
            (*tree + i)->left = -1;//No left child, set it to -1
        }
        if (rightc >= '0'&&rightc <= '9')
        {
            (*tree + i)->right = rightc - '0';//Having right child, transform the character to subscript of right child
            flag[(*tree + i)->right] = 0;
        }
        else
        {
            (*tree + i)->right = -1;//No right child, set it to -1
        }
    }
    for (i = 0; i < N; ++i)
    {
        if (flag[i])
        {
            return *tree + i;
        }
    }
}

//To judge whether two trees are isomorphic
int Isomorphic(Tree p1, Tree p2)
{
    if (p1<tree1&&p2<tree2)//Both p1 and p2 are empty
    {
        return 1;
    }
    if ((p1<tree1&&p2>=tree2)||(p1>=tree1&&p2<tree2))//one of p1 and p2 is empty, another is not empty
    {
        return 0;
    }

    //Both p1 and p2 are not empty
    if (p1->data != p2->data)//Root node elements not equal
    {
        return 0;
    }
    return Isomorphic(tree1 + p1->left, tree2 + p2->left) && Isomorphic(tree1 + p1->right, tree2 + p2->right) || Isomorphic(tree1 + p1->left, tree2 + p2->right) && (Isomorphic(tree1 + p1->right, tree2 + p2->left));
}