Étant donné une séquence d'insertion, on peut construire un unique arbre binaire de recherche. Cependant, un même arbre binaire de recherche peut être obtenu à partir de plusieurs séquences d'insertion différentes. Par exemple, les séquences {2, 1, 3} et {2, 3, 1} insérées dans un arbre binaire de recherche initialement vide donnent le même résultat. Pour chaque ensemble de séquences d'insertion, vous devez déterminer si elles produisent le même arbre binaire de recherche.

Format d'entrée :

L'entrée contient plusieurs groupes de données de test. Pour chaque groupe, la première ligne donne deux entiers positifs N (≤10) et L, respectivement le nombre d'éléments de chaque séquence d'insertion et le nombre de séquances à vérifier. La deuxième ligne donne N antiers positifs séparés par des espaces, constituant la séquence d'insertion initiale. Les L lignes suivantes donnent chacune N éléments insérés, appartenant aux L séquences à vérifier.

Pour simplifier, chaque séquence d'insertion est une permutation des entiers de 1 à N. Lorsque N est 0, cela marque la fin de l'entrée et ce groupe ne doit pas être traité.

Format de sortie :

Pour chaque séquence à vérifier, si l'arbre binaire de recherche généré est identique à celui produit par la séquence initiale, affichez "Yes", sinon "No".

Exemple d'entrée :

4 2
3 1 4 2
3 4 1 2
3 2 4 1
2 1
2 1
1 2
0

Exemple de sortie :

Yes
No
No

Analyse du problème :

Il s'agit d'insérer les éléments dans un arbre binaire de recherche, puis de comparer récursivement deux arbres pour voir s'ils sont identiques. L'idée est similaire à celle du problème 7-3 : une fonction de comparaison récursive.

Solution en C (restructurée) :

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

typedef struct Node {
    int value;
    struct Node* left;
    struct Node* right;
} Node;

Node* createNode(int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->value = value;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

Node* insert(Node* root, int value) {
    if (root == NULL) {
        return createNode(value);
    }
    if (value < root->value) {
        root->left = insert(root->left, value);
    } else if (value > root->value) {
        root->right = insert(root->right, value);
    }
    return root;
}

Node* buildTree(int n) {
    Node* root = NULL;
    int value;
    for (int i = 0; i < n; i++) {
        scanf("%d", &value);
        root = insert(root, value);
    }
    return root;
}

bool areIdentical(Node* tree1, Node* tree2) {
    if (tree1 == NULL && tree2 == NULL) return true;
    if (tree1 == NULL || tree2 == NULL) return false;
    if (tree1->value != tree2->value) return false;
    return areIdentical(tree1->left, tree2->left) &&
           areIdentical(tree1->right, tree2->right);
}

void freeTree(Node* root) {
    if (root == NULL) return;
    freeTree(root->left);
    freeTree(root->right);
    free(root);
}

int main() {
    int n;
    scanf("%d", &n);
    while (n != 0) {
        int l;
        scanf("%d", &l);
        Node* reference = buildTree(n);
        for (int i = 0; i < l; i++) {
            Node* candidate = buildTree(n);
            if (areIdentical(reference, candidate)) {
                printf("Yes\n");
            } else {
                printf("No\n");
            }
            freeTree(candidate);
        }
        freeTree(reference);
        scanf("%d", &n);
    }
    return 0;
}

Cette version utilise des noms de variables plus explicites, une fonction de création de nœud, et bool pour la comparaison. La logique reste identique à l'originale.