Édition pédagogique en français

Arbre binaire de recherche en C

Insérez et cherchez des clés grâce à l’ordre des sous-arbres.

Les clés plus petites vont dans un sous-arbre et les plus grandes dans l’autre. Définissez une règle pour les doublons. Le parcours infixe visite les clés dans l’ordre croissant.

La recherche compare la clé au nœud courant et choisit un seul enfant. Son coût dépend de la hauteur : O(log N) si l’arbre est équilibré, O(N) s’il devient une chaîne. Un arbre simple ne s’équilibre pas automatiquement.

Vérifiez les allocations et libérez les enfants avant le parent. Essayez des clés triées, dupliquées et absentes, puis observez la forme de l’arbre.

Code source

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

typedef struct BSTNode {
    int val;
    struct BSTNode *left;
    struct BSTNode *right;
} BSTNode;

/* Return 0 on allocation failure without changing existing nodes. */
int insert(BSTNode **root, int val) {
    if (*root == NULL) {
        BSTNode *node = malloc(sizeof *node);
        if (node == NULL) return 0;
        node->val = val;
        node->left = node->right = NULL;
        *root = node;
        return 1;
    }
    if (val < (*root)->val) return insert(&(*root)->left, val);
    if (val > (*root)->val) return insert(&(*root)->right, val);
    return 1; /* Ignore duplicate keys. */
}

void inorder(const BSTNode *root) {
    if (root != NULL) {
        inorder(root->left);
        printf("%d ", root->val);
        inorder(root->right);
    }
}

void freeBST(BSTNode *root) {
    if (root != NULL) {
        freeBST(root->left);
        freeBST(root->right);
        free(root);
    }
}

int main(void) {
    BSTNode *root = NULL;
    const int keys[] = {50, 30, 20, 40, 70, 60, 80};
    for (size_t i = 0; i < sizeof keys / sizeof keys[0]; i++) {
        if (!insert(&root, keys[i])) {
            fputs("Unable to allocate a BST node.\n", stderr);
            freeBST(root);
            return EXIT_FAILURE;
        }
    }

    printf("BST In-Order Sorted Traversal: ");
    inorder(root);
    printf("\n");

    freeBST(root);
    return EXIT_SUCCESS;
}

Ouvrir dans le compilateur

Résultat attendu

BST In-Order Sorted Traversal: 20 30 40 50 60 70 80

Questions fréquentes

Pourquoi le code et certains résultats restent-ils en anglais ?

Les mots-clés C, les identifiants, les commentaires du programme et les sorties attendues restent ceux de la version originale pour conserver un code exécutable et des tests cohérents. Les explications et les consignes sont traduites.