C 语言树同构判断代码示例：使用递归算法判断两棵树是否同构

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

typedef struct Node { int data; int left; int right; } Node;

bool isomorphic(Node *t1, Node *t2, int root1, int root2) { // Base case: if both roots are -1, the trees are isomorphic if (root1 == -1 && root2 == -1) return true;

// Base case: if one root is -1 and the other is not, the trees are not isomorphic
if (root1 == -1 || root2 == -1)
    return false;

// Check if the data in the roots of both trees is the same
if (t1[root1].data != t2[root2].data)
    return false;

// Recursively check the left and right subtrees of both trees
bool leftIsomorphic = isomorphic(t1, t2, t1[root1].left, t2[root2].left) && isomorphic(t1, t2, t1[root1].right, t2[root2].right);
bool rightIsomorphic = isomorphic(t1, t2, t1[root1].left, t2[root2].right) && isomorphic(t1, t2, t1[root1].right, t2[root2].left);

// If either the left subtrees or the right subtrees of both trees are isomorphic, the trees are isomorphic
return leftIsomorphic || rightIsomorphic;

}

int main() { int n; scanf("%d", &n);

Node *t1 = (Node *)malloc(n * sizeof(Node));
Node *t2 = (Node *)malloc(n * sizeof(Node));

for (int i = 0; i < n; i++)
{
    int val, leftval, rightval;
    scanf("%d", &val);
    t1[i].data = val;
    t1[i].left = -1;
    t1[i].right = -1;
    t2[i].data = val;
    t2[i].left = -1;
    t2[i].right = -1;
}

for (int i = 0; i < n; i++)
{
    int val, leftval, rightval;
    scanf("%d %d %d", &val, &leftval, &rightval);

    if (leftval != -1)
    {
        for (int j = 0; j < n; j++)
        {
            if (t1[j].data == leftval)
            {
                t1[i].left = j;
                break;
            }
        }
    }

    if (rightval != -1)
    {
        for (int j = 0; j < n; j++)
        {
            if (t1[j].data == rightval)
            {
                t1[i].right = j;
                break;
            }
        }
    }
}

for (int i = 0; i < n; i++)
{
    int val, leftval, rightval;
    scanf("%d %d %d", &val, &leftval, &rightval);

    if (leftval != -1)
    {
        for (int j = 0; j < n; j++)
        {
            if (t2[j].data == leftval)
            {
                t2[i].left = j;
                break;
            }
        }
    }

    if (rightval != -1)
    {
        for (int j = 0; j < n; j++)
        {
            if (t2[j].data == rightval)
            {
                t2[i].right = j;
                break;
            }
        }
    }
}

bool result = isomorphic(t1, t2, 0, 0);
if (result)
    printf("yes\n");
else
    printf("no\n");

free(t1);
free(t2);

return 0;