L'isomorphisme d'arbres est un concept fondamental en structures de données. Deux arbres binaires, T1 et T2, sont dits isomorphes si l'on peut transformer T1 en T2 en échangeant, pour un nombre quelconque de nœuds, leurs enfants gauche et droit. Cet article présente une approche systématique pour résoudre ce problème en utilisant une représentation statique des arbres et une fonction récursive de comparaison.

Représenttaion des données

Pour modéliser l'arbre, nous utilisons un tableau de structures où chaque indice représente un nœud. Cette méthode est particulièrement efficace pour les problèmes où le nombre maximal de nœuds est connu à l'avance et où les références aux enfants sont fournies sous forme d'indices.

#include <stdio.h>

#define MAX_NODES 10
#define NULL_NODE -1

typedef struct {
    char element;
    int left;
    int right;
} BinaryNode;

BinaryNode Tree1[MAX_NODES], Tree2[MAX_NODES];

Construction de l'arbre et identification de la racine

Lors de la lecture des données, il est crucial d'identifier la racine de l'arbre. La racine est le seul nœud qui n'est l'enfant d'aucun autre nœud. Nous utilisons un tableau de marquage pour suivre les nœuds référencés.

int build_tree(BinaryNode tree[]) {
    int n;
    if (scanf("%d", &n) != 1 || n == 0) return NULL_NODE;

    int is_child[MAX_NODES] = {0};
    char lc, rc;

    for (int i = 0; i < n; i++) {
        scanf(" %c %c %c", &tree[i].element, &lc, &rc);

        if (lc != '-') {
            tree[i].left = lc - '0';
            is_child[tree[i].left] = 1;
        } else {
            tree[i].left = NULL_NODE;
        }

        if (rc != '-') {
            tree[i].right = rc - '0';
            is_child[tree[i].right] = 1;
        } else {
            tree[i].right = NULL_NODE;
        }
    }

    for (int i = 0; i < n; i++) {
        if (!is_child[i]) return i;
    }
    return NULL_NODE;
}

Logique de comparaison récursive

La fonction de vérification d'isomorphisme repose sur une exploration récursive. Pour chaque paire de nœuds, nous devons envisager deux scénarios :

• Les sous-arbres correspondants sont identiques (Gauche-Gauche et Droite-Droite).
• Les sous-arbres ont été intervertis (Gauche-Droite et Droite-Gauche).

int check_isomorphism(int root1, int root2) {
    // Cas de base : les deux nœuds sont vides
    if (root1 == NULL_NODE && root2 == NULL_NODE) 
        return 1;
    
    // Un seul est vide ou les données divergent
    if (((root1 == NULL_NODE) != (root2 == NULL_NODE)) || 
        (Tree1[root1].element != Tree2[root2].element)) 
        return 0;

    // Cas 1 : Pas d'inversion au niveau actuel
    if (check_isomorphism(Tree1[root1].left, Tree2[root2].left) &&
        check_isomorphism(Tree1[root1].right, Tree2[root2].right))
        return 1;

    // Cas 2 : Inversion des enfants gauche et droit
    return (check_isomorphism(Tree1[root1].left, Tree2[root2].right) &&
            check_isomorphism(Tree1[root1].right, Tree2[root2].left));
}

Implémentation principale

Le programme principal orchestre la construction des deux structures et affiche le résultat final en fonction de la validation récursive.

int main() {
    int r1 = build_tree(Tree1);
    int r2 = build_tree(Tree2);

    if (check_isomorphism(r1, r2)) {
        printf("Yes\n");
    } else {
        printf("No\n");
    }

    return 0;
}

Analyse de complexité

L'algorithme parcourt les arbres de manière récursive. Dans le pire des cas, la complexité temporelle est proportionnelle au nombre de nœuds, noté O(N), car chaque nœud est visité un nombre constant de fois. L'espace mémoire utilisé est également O(N) pour stocker les tableaux statiques et la pile d'appels de la récursion.