Edição didática em português. O código e suas saídas preservam o original.

Árvore binária de busca em C

Insira e busque chaves usando a ordem das subárvores.

Em uma árvore binária de busca, chaves menores ficam em uma subárvore e maiores na outra. Defina uma política para duplicatas e mantenha-a em todas as operações. Um percurso em ordem visita as chaves em ordem crescente.

A busca compara a chave com o nó atual e escolhe apenas um filho. Seu custo depende da altura: O(log N) em uma árvore equilibrada, mas O(N) se os dados formarem uma cadeia. Uma árvore binária de busca simples não se equilibra automaticamente.

Verifique alocações e libere os filhos antes do nó pai. Teste chaves ordenadas, duplicadas e ausentes; observe como a forma da árvore muda.

Código 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;
}

Abrir no compilador

Saída esperada

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

Perguntas frequentes

Por que o código e a saída continuam em inglês?

Palavras-chave, identificadores e textos verificados pelos testes são preservados para não alterar o programa. As explicações e os controles estão traduzidos.