Nederlandse leereditie

Binaire zoekboom in C

Voeg sleutels in en zoek ze op terwijl je het effect van boomhoogte begrijpt.

Kleinere sleutels gaan naar de ene deelboom en grotere naar de andere. Leg een regel voor duplicaten vast. Een inorder-doorloop geeft sleutels in oplopende volgorde.

Zoeken vergelijkt de sleutel met de huidige knoop en kiest één kind. De kosten hangen af van de hoogte: O(log N) bij balans, O(N) bij een keten. Een eenvoudige boom balanceert zichzelf niet.

Controleer reserveringen en geef kinderen vrij vóór hun ouder. Test gesorteerde, dubbele en ontbrekende sleutels en bekijk de boomvorm.

Broncode

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

Openen in de compiler

Verwacht resultaat

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

Veelgestelde vragen

Waarom blijven code en sommige resultaten Engels?

C-sleutelwoorden, namen, programmacommentaar en verwachte uitvoer blijven gelijk aan het origineel om uitvoerbare code en consistente tests te behouden. Uitleg en instructies zijn vertaald.