Deutsche Lernausgabe

Binärer Suchbaum in C

Fügen Sie Schlüssel ein und suchen Sie anhand der Ordnung der Teilbäume.

Kleinere Schlüssel kommen in einen Teilbaum, größere in den anderen. Legen Sie eine Regel für Duplikate fest. Ein Inorder-Durchlauf besucht die Schlüssel in aufsteigender Reihenfolge.

Die Suche vergleicht den Schlüssel mit dem aktuellen Knoten und wählt ein Kind. Der Aufwand hängt von der Höhe ab: O(log N) bei einem ausgeglichenen Baum, O(N) bei einer Kette. Ein einfacher Suchbaum gleicht sich nicht automatisch aus.

Prüfen Sie Reservierungen und geben Sie Kinder vor dem Elternknoten frei. Probieren Sie sortierte, doppelte und fehlende Schlüssel und beobachten Sie die Baumform.

Quellcode

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

Im Compiler öffnen

Erwartetes Ergebnis

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

Häufige Fragen

Warum bleiben Code und manche Ausgaben englisch?

C-Schlüsselwörter, Bezeichner, Programmkommentare und erwartete Ausgaben bleiben wie im Original, damit der Code ausführbar und die Tests konsistent bleiben. Erklärungen und Aufgabenstellungen sind übersetzt.