Edizione didattica italiana

Albero binario di ricerca in C

Inserisci e cerca chiavi comprendendo l’effetto dell’altezza dell’albero.

Le chiavi minori vanno in un sottoalbero e le maggiori nell’altro. Definisci una regola per i duplicati. La visita in ordine simmetrico elenca le chiavi in ordine crescente.

La ricerca confronta la chiave col nodo corrente e sceglie un solo figlio. Il costo dipende dall’altezza: O(log N) per un albero bilanciato, O(N) se diventa una catena. Un albero semplice non si bilancia da solo.

Controlla le allocazioni e libera i figli prima del genitore. Prova chiavi ordinate, duplicate e assenti e osserva la forma dell’albero.

Codice sorgente

#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;
}

Apri nel compilatore

Risultato atteso

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

Domande frequenti

Perché il codice e alcuni risultati restano in inglese?

Parole chiave C, identificatori, commenti del programma e output attesi restano quelli originali per preservare codice eseguibile e test coerenti. Spiegazioni e istruzioni sono tradotte.