Учебная версия на русском. Код и его вывод сохранены в исходном виде.

Двоичное дерево поиска на C

Вставляйте и ищите ключи, используя порядок значений в поддеревьях.

В двоичном дереве поиска меньшие ключи находятся в одном поддереве, большие — в другом. Заранее определите правило для одинаковых ключей. Симметричный обход посещает значения в возрастающем порядке.

Поиск сравнивает цель с текущим узлом и выбирает только одного потомка. Стоимость определяется высотой: O(log N) для сбалансированного дерева, но O(N), если оно превратилось в цепочку. Простое дерево не балансируется автоматически.

Проверяйте выделение памяти и освобождайте потомков раньше родителя. Добавляйте упорядоченные, повторяющиеся и отсутствующие ключи и наблюдайте за формой дерева.

Код C

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

Открыть в компиляторе

Ожидаемый вывод

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

Частые вопросы

Почему код и вывод остаются на английском?

Ключевые слова, идентификаторы и строки, проверяемые тестами, сохранены, чтобы не менять программу. Объяснения и элементы управления переведены.