C Árvores Binárias

Numa lista ligada, cada nó aponta para um próximo, e procurar um valor obriga a olhar um por um. Numa árvore binária, cada nó aponta para dois: um à esquerda e um à direita. Com uma regra simples (os menores à esquerda, os maiores à direita), a árvore permite achar um valor entre mil olhando só uns vinte. Nesta aula você vai montar árvores com malloc, percorrê-las com recursão, inserir, buscar e liberar tudo sem vazar memória.

Esta aula usa structs e a seta ->, malloc e free, recursão e listas ligadas. Todos os programas foram compilados com o gcc 15.2 na máquina fictícia da Ana (usuária ana, computador notebook), na pasta ~/c, com o comando padrão do guia: gcc -std=c23 -Wall -Wextra arquivo.c -o programa.

A ideia: o jogo do "maior ou menor"

A Ana pensa num número de 1 a 100, e você tenta adivinhar. A cada palpite, ela só responde "é maior" ou "é menor". Quem joga bem começa pelo 50: se ela disser "menor", nem precisa pensar nos números de 51 a 100. Depois tenta o 25, e assim por diante. A cada pergunta, metade das possibilidades some (o Projeto Adivinhação é esse jogo).

Uma árvore binária de busca guarda os valores já organizados para esse jogo. Cada nó guarda um valor e tem dois "caminhos": à esquerda ficam os menores, à direita os maiores. Para procurar, você começa no topo e, a cada nó, decide: "é este? é menor? é maior?".

As árvores da computação crescem de cabeça para baixo: a raiz fica em cima e as folhas embaixo. Os nomes vêm da árvore genealógica e da árvore de verdade:

1. O nó: dois ponteiros em vez de um

O nó da lista ligada tinha um valor e um prox. O nó da árvore tem um valor e dois ponteiros, um para cada filho. Quando um filho não existe, o ponteiro vale NULL. Para começar, três nós montados à mão, sem malloc:

#include <stdio.h>

typedef struct No {
    int valor;
    struct No *esq;
    struct No *dir;
} No;

int main(void) {
    No a = {30, NULL, NULL};
    No b = {70, NULL, NULL};
    No raiz = {50, &a, &b};

    printf("Raiz: %d\n", raiz.valor);
    printf("Filho da esquerda: %d\n", raiz.esq->valor);
    printf("Filho da direita: %d\n", raiz.dir->valor);
    printf("O 30 tem filhos? %s\n", a.esq == NULL && a.dir == NULL ? "não, é uma folha" : "sim");
    return 0;
}

$ gcc -std=c23 -Wall -Wextra arvore_mao.c -o arvore_mao
$ ./arvore_mao
Raiz: 50
Filho da esquerda: 30
Filho da direita: 70
O 30 tem filhos? não, é uma folha

typedef struct No { … } No;

Uma struct que, como na lista ligada, aponta para outras do mesmo tipo. Dentro dela é preciso escrever struct No, porque o apelido No só existe depois do ; final (veja typedef).

struct No *esq; struct No *dir;

Os dois filhos: esq (esquerda) e dir (direita). Em código em inglês você vai ver left e right.

No a = {30, NULL, NULL};

Um nó com o valor 30 e sem filhos: os dois ponteiros em NULL. Os valores entre chaves seguem a ordem dos campos.

No raiz = {50, &a, &b};

O nó 50 aponta para a à esquerda e para b à direita. Ele é a raiz: dele dá para chegar a todos os outros.

raiz.esq->valor

raiz.esq é um ponteiro (o endereço de a); a seta segue o ponteiro e pega o campo valor lá dentro: 30.

a.esq == NULL && a.dir == NULL

O teste de folha: nenhum dos dois filhos existe.

Nós montados à mão servem para entender, mas uma árvore de verdade cresce enquanto o programa roda. Daqui em diante, cada nó nasce com malloc.

2. Percorrer a árvore: recursão

Para mostrar uma lista ligada, um laço while anda de nó em nó. Numa árvore isso não basta: em cada nó o caminho se divide em dois, e é preciso visitar os dois lados. O jeito natural é a recursão: "mostrar a árvore" é mostrar a subárvore da esquerda, mostrar a raiz e mostrar a subárvore da direita. E cada subárvore é mostrada do mesmo jeito.

#include <stdio.h>
#include <stdlib.h>

typedef struct No {
    int valor;
    struct No *esq;
    struct No *dir;
} No;

No *novo(int valor, No *esq, No *dir) {
    No *n = malloc(sizeof *n);
    if (n == NULL) {
        fprintf(stderr, "Sem memória\n");
        exit(1);
    }
    n->valor = valor;
    n->esq = esq;
    n->dir = dir;
    return n;
}

void em_ordem(const No *raiz) {
    if (raiz == NULL) {
        return;
    }
    em_ordem(raiz->esq);
    printf("%d ", raiz->valor);
    em_ordem(raiz->dir);
}

void pre_ordem(const No *raiz) {
    if (raiz == NULL) {
        return;
    }
    printf("%d ", raiz->valor);
    pre_ordem(raiz->esq);
    pre_ordem(raiz->dir);
}

void pos_ordem(const No *raiz) {
    if (raiz == NULL) {
        return;
    }
    pos_ordem(raiz->esq);
    pos_ordem(raiz->dir);
    printf("%d ", raiz->valor);
}

void liberar(No *raiz) {
    if (raiz == NULL) {
        return;
    }
    liberar(raiz->esq);
    liberar(raiz->dir);
    free(raiz);
}

int main(void) {
    No *raiz = novo(50,
                    novo(30, novo(20, NULL, NULL), novo(40, NULL, NULL)),
                    novo(70, novo(60, NULL, NULL), novo(80, NULL, NULL)));

    printf("Em ordem:  ");
    em_ordem(raiz);
    printf("\nPré-ordem: ");
    pre_ordem(raiz);
    printf("\nPós-ordem: ");
    pos_ordem(raiz);
    printf("\n");

    liberar(raiz);
    return 0;
}

$ gcc -std=c23 -Wall -Wextra -g percursos.c -o percursos
$ ./percursos
Em ordem:  20 30 40 50 60 70 80
Pré-ordem: 50 30 20 40 70 60 80
Pós-ordem: 20 40 30 60 80 70 50
$ valgrind -q --leak-check=full ./percursos
Em ordem:  20 30 40 50 60 70 80
Pré-ordem: 50 30 20 40 70 60 80
Pós-ordem: 20 40 30 60 80 70 50

No *novo(int valor, No *esq, No *dir)

Cria um nó no heap com malloc e já liga os filhos. Se faltar memória, avisa no stderr e encerra (veja exit).

novo(50, novo(30, …), novo(70, …))

As chamadas aninhadas desenham a árvore: o C cria primeiro os filhos (os argumentos) e depois o pai, que recebe os endereços deles. É a mesma árvore da figura do começo.

if (raiz == NULL) return;

O caso base da recursão: uma árvore vazia não tem nada para mostrar. Toda chamada que chega a um filho que não existe para aqui e volta.

em_ordem(raiz->esq); printf(…); em_ordem(raiz->dir);

Em ordem (in-order): esquerda, raiz, direita. Numa árvore de busca, sai tudo em ordem crescente.

pre_ordem

Pré-ordem (pre-order): a raiz antes dos filhos. É a ordem em que alguém "copiaria" a árvore: primeiro o pai, depois os filhos.

pos_ordem

Pós-ordem (post-order): a raiz depois dos filhos. É a ordem certa para liberar: os filhos vão embora antes do pai.

liberar(raiz->esq); liberar(raiz->dir); free(raiz);

Uma pós-ordem que, no lugar de mostrar, devolve a memória. O valgrind -q não reclamou de nada: os 7 nós foram liberados.

A única diferença entre as três funções é onde fica o printf: antes, entre ou depois das duas chamadas. Acompanhe a em ordem no 30: ela primeiro desce para o 20 (que não tem filhos e é mostrado), volta e mostra o 30, desce para o 40 e mostra o 40. Só então volta para o 50.

#include <stdio.h>
#include <stdlib.h>

typedef struct No {
    int valor;
    struct No *esq;
    struct No *dir;
} No;

No *novo(int valor, No *esq, No *dir) {
    No *n = malloc(sizeof *n);
    if (n == NULL) {
        fprintf(stderr, "Sem memória\n");
        exit(1);
    }
    n->valor = valor;
    n->esq = esq;
    n->dir = dir;
    return n;
}

void em_ordem(const No *raiz) {
    if (raiz == NULL) {
        return;
    }
    em_ordem(raiz->esq);
    printf("%d ", raiz->valor);
    em_ordem(raiz->dir);
}

void pre_ordem(const No *raiz) {
    if (raiz == NULL) {
        return;
    }
    printf("%d ", raiz->valor);
    pre_ordem(raiz->esq);
    pre_ordem(raiz->dir);
}

void pos_ordem(const No *raiz) {
    if (raiz == NULL) {
        return;
    }
    pos_ordem(raiz->esq);
    pos_ordem(raiz->dir);
    printf("%d ", raiz->valor);
}

void liberar(No *raiz) {
    if (raiz == NULL) {
        return;
    }
    liberar(raiz->esq);
    liberar(raiz->dir);
    free(raiz);
}

int main(void) {
    No *raiz = novo(50,
                    novo(30, novo(20, NULL, NULL), novo(40, NULL, NULL)),
                    novo(70, novo(60, NULL, NULL), novo(80, NULL, NULL)));

    printf("Em ordem:  ");
    em_ordem(raiz);
    printf("\nPré-ordem: ");
    pre_ordem(raiz);
    printf("\nPós-ordem: ");
    pos_ordem(raiz);
    printf("\n");

    liberar(raiz);
    return 0;
}

3. Árvore de busca: a regra e o inserir

Até aqui, quem decidiu onde cada nó ficava foi você, à mão. Numa árvore binária de busca (em inglês, binary search tree, ou BST), quem decide é uma regra:

• Tudo o que está na subárvore esquerda de um nó é menor que ele.
• Tudo o que está na subárvore direita é maior.

Para inserir um número novo, você faz o jogo do "maior ou menor": começa na raiz e desce para a esquerda ou para a direita até achar um lugar vazio (NULL). O nó novo nasce ali, sempre como folha.

#include <stdio.h>
#include <stdlib.h>

typedef struct No {
    int valor;
    struct No *esq;
    struct No *dir;
} No;

No *inserir(No *raiz, int valor) {
    if (raiz == NULL) {
        No *n = malloc(sizeof *n);
        if (n == NULL) {
            fprintf(stderr, "Sem memória\n");
            exit(1);
        }
        n->valor = valor;
        n->esq = NULL;
        n->dir = NULL;
        return n;
    }
    if (valor < raiz->valor) {
        raiz->esq = inserir(raiz->esq, valor);
    } else if (valor > raiz->valor) {
        raiz->dir = inserir(raiz->dir, valor);
    }
    return raiz;
}

void em_ordem(const No *raiz) {
    if (raiz == NULL) {
        return;
    }
    em_ordem(raiz->esq);
    printf("%d ", raiz->valor);
    em_ordem(raiz->dir);
}

void liberar(No *raiz) {
    if (raiz == NULL) {
        return;
    }
    liberar(raiz->esq);
    liberar(raiz->dir);
    free(raiz);
}

int main(void) {
    int numeros[] = {50, 30, 70, 20, 40, 60, 80, 40};
    int n = sizeof numeros / sizeof numeros[0];
    No *raiz = NULL;

    for (int i = 0; i < n; i++) {
        raiz = inserir(raiz, numeros[i]);
    }
    printf("Em ordem: ");
    em_ordem(raiz);
    printf("\n");
    printf("Raiz: %d, esquerda: %d, direita: %d\n",
           raiz->valor, raiz->esq->valor, raiz->dir->valor);

    liberar(raiz);
    return 0;
}

$ gcc -std=c23 -Wall -Wextra inserir.c -o inserir
$ ./inserir
Em ordem: 20 30 40 50 60 70 80
Raiz: 50, esquerda: 30, direita: 70

No *inserir(No *raiz, int valor)

Recebe uma árvore (a raiz dela) e um valor, e devolve a raiz da árvore depois de inserir. Por que devolver? Porque, se a árvore estava vazia, a raiz muda: passa de NULL para o nó novo.

if (raiz == NULL) { … return n; }

Achou o lugar vazio: cria o nó, sem filhos, e o devolve. Ele vira a raiz desta (sub)árvore.

if (valor < raiz->valor) raiz->esq = inserir(raiz->esq, valor);

É menor: o lugar dele está na subárvore esquerda. A chamada recursiva insere lá e devolve a raiz daquela subárvore, que é guardada de volta em raiz->esq. Se a esquerda era NULL, agora ela aponta para o nó novo.

else if (valor > raiz->valor) …

É maior: mesma coisa, pela direita.

(e se for igual?)

Nenhum dos dois if vale e nada acontece: valores repetidos são ignorados. O segundo 40 do array não entrou. Se você quiser contar repetições, guarde um contador no nó (é a missão final).

raiz = inserir(raiz, numeros[i]);

Quem chama sempre guarda o retorno. No primeiro número, raiz era NULL e passa a apontar para o 50. Esquecer este raiz = é o erro mais comum (veja Quando dá errado).

Repare na primeira linha da saída: os números entraram fora de ordem (50, 30, 70, 20…), mas a em ordem os mostrou ordenados. A regra da árvore garante isso. Veja como o 65 entraria nessa árvore:

4. Buscar: o caminho de um só lado

Para procurar, não é preciso visitar a árvore toda: a cada nó, a regra diz para que lado ir, e o outro lado inteiro é descartado. Como só um caminho é seguido, dá para usar um laço while, sem recursão. Esta versão mostra cada nó olhado:

#include <stdio.h>
#include <stdlib.h>

typedef struct No { … } No;          // igual ao inserir.c
No *inserir(No *raiz, int valor) { … }
void liberar(No *raiz) { … }

bool buscar(const No *raiz, int procurado) {
    int passos = 0;
    const No *atual = raiz;
    while (atual != NULL) {
        passos++;
        printf("  olhou o %d\n", atual->valor);
        if (procurado == atual->valor) {
            printf("  achou em %d passos\n", passos);
            return true;
        }
        if (procurado < atual->valor) {
            atual = atual->esq;
        } else {
            atual = atual->dir;
        }
    }
    printf("  não está na árvore (%d passos)\n", passos);
    return false;
}

int main(void) {
    int numeros[] = {50, 30, 70, 20, 40, 60, 80};
    No *raiz = NULL;
    for (int i = 0; i < 7; i++) {
        raiz = inserir(raiz, numeros[i]);
    }
    printf("Procurando 60:\n");
    buscar(raiz, 60);
    printf("Procurando 45:\n");
    buscar(raiz, 45);
    liberar(raiz);
    return 0;
}

$ gcc -std=c23 -Wall -Wextra buscar.c -o buscar
$ ./buscar
Procurando 60:
  olhou o 50
  olhou o 70
  olhou o 60
  achou em 3 passos
Procurando 45:
  olhou o 50
  olhou o 30
  olhou o 40
  não está na árvore (3 passos)

const No *atual = raiz;

Um ponteiro que desce pela árvore, como o atual que andava pela lista ligada. O const diz que a busca só olha, sem mudar nada.

while (atual != NULL)

Desce até cair num filho que não existe. Se chegar ao NULL, o valor não está na árvore: se estivesse, teria de estar justamente ali.

if (procurado == atual->valor)

Achou: devolve true.

atual = atual->esq; / atual = atual->dir;

Escolhe um lado e esquece o outro. Procurando o 45, depois de ver que ele é menor que 50, os nós 70, 60 e 80 nem são olhados.

Com 7 nós a diferença é pequena. Com mais nós ela cresce depressa: uma árvore "cheia" de altura 10 guarda até 1023 valores, e qualquer busca olha no máximo 10. Uma lista com 1023 valores pode precisar de 1023 passos. Essa é a mesma ideia da busca binária num array ordenado.

5. Menor, maior, quantos e altura

Duas perguntas se respondem com um laço, seguindo um lado só. Outras duas precisam olhar a árvore inteira e ficam bonitas com recursão:

…                                    // No, inserir e liberar como antes

int contar(const No *raiz) {
    if (raiz == NULL) {
        return 0;
    }
    return 1 + contar(raiz->esq) + contar(raiz->dir);
}

int altura(const No *raiz) {
    if (raiz == NULL) {
        return 0;
    }
    int e = altura(raiz->esq);
    int d = altura(raiz->dir);
    return 1 + (e > d ? e : d);
}

int minimo(const No *raiz) {
    while (raiz->esq != NULL) {
        raiz = raiz->esq;
    }
    return raiz->valor;
}

int maximo(const No *raiz) {
    while (raiz->dir != NULL) {
        raiz = raiz->dir;
    }
    return raiz->valor;
}

int main(void) {
    int numeros[] = {50, 30, 70, 20, 40, 60, 80, 65};
    No *raiz = NULL;
    for (int i = 0; i < 8; i++) {
        raiz = inserir(raiz, numeros[i]);
    }
    printf("Nós: %d\n", contar(raiz));
    printf("Altura: %d\n", altura(raiz));
    printf("Menor: %d\n", minimo(raiz));
    printf("Maior: %d\n", maximo(raiz));
    liberar(raiz);
    return 0;
}

$ gcc -std=c23 -Wall -Wextra medidas.c -o medidas
$ ./medidas
Nós: 8
Altura: 4
Menor: 20
Maior: 80

contar: 1 + contar(raiz->esq) + contar(raiz->dir)

Quantos nós tem a árvore? O nó atual (1) mais os da esquerda mais os da direita. A árvore vazia tem 0.

altura: 1 + (e > d ? e : d)

A altura é o nó atual mais a altura do lado mais alto (o ternário escolhe o maior entre e e d). O 65 inserido debaixo do 60 deixou a árvore com altura 4: 50 → 70 → 60 → 65.

minimo: while (raiz->esq != NULL)

O menor valor é o que está mais à esquerda: desça pela esquerda até não dar mais. O maior, pelo mesmo raciocínio, está mais à direita.

(cuidado com a árvore vazia)

minimo e maximo leem raiz->esq logo na primeira volta. Com uma árvore vazia (NULL), isso é falha de segmentação. Quem chama precisa conferir antes, ou a função pode devolver um bool e o valor por ponteiro, como o pop da aula Pilhas e Filas.

Soma: 350

#include <stdio.h>
#include <stdlib.h>

typedef struct No {
    int valor;
    struct No *esq;
    struct No *dir;
} No;

No *novo(int valor, No *esq, No *dir) {
    No *n = malloc(sizeof *n);
    if (n == NULL) {
        exit(1);
    }
    n->valor = valor;
    n->esq = esq;
    n->dir = dir;
    return n;
}

int somar(const No *raiz) {
    // COMPLETE: árvore vazia soma 0;
    // senão, é o valor da raiz + a soma da esquerda + a soma da direita
    (void)raiz;
    return 0;
}

int main(void) {
    No *raiz = novo(50,
                    novo(30, novo(20, NULL, NULL), novo(40, NULL, NULL)),
                    novo(70, novo(60, NULL, NULL), novo(80, NULL, NULL)));
    printf("Soma: %d\n", somar(raiz));
    return 0;
}

#include <stdio.h>
#include <stdlib.h>

typedef struct No {
    int valor;
    struct No *esq;
    struct No *dir;
} No;

No *novo(int valor, No *esq, No *dir) {
    No *n = malloc(sizeof *n);
    if (n == NULL) {
        exit(1);
    }
    n->valor = valor;
    n->esq = esq;
    n->dir = dir;
    return n;
}

int somar(const No *raiz) {
    if (raiz == NULL) {
        return 0;
    }
    return raiz->valor + somar(raiz->esq) + somar(raiz->dir);
}

int main(void) {
    No *raiz = novo(50,
                    novo(30, novo(20, NULL, NULL), novo(40, NULL, NULL)),
                    novo(70, novo(60, NULL, NULL), novo(80, NULL, NULL)));
    printf("Soma: %d\n", somar(raiz));
    return 0;
}

6. Liberar: dos filhos para o pai

Cada nó nasceu de um malloc, então cada um precisa do seu free. A ordem importa: se você liberar o pai primeiro, os ponteiros esq e dir dele somem junto, e os filhos ficam sem ninguém que saiba onde eles estão. Por isso a função liberar é uma pós-ordem:

void liberar(No *raiz) {
    if (raiz == NULL) {
        return;
    }
    liberar(raiz->esq);   // primeiro a subárvore da esquerda inteira
    liberar(raiz->dir);   // depois a da direita
    free(raiz);           // só então o próprio nó
}

Ela já estava em todos os programas desta aula. O valgrind do percursos.c (seção 2) ficou calado, e um relatório completo de um programa que libera tudo termina assim:

$ gcc -std=c23 -Wall -Wextra -g palavras.c -o palavras
$ valgrind --leak-check=full ./palavras 2>&1 | tail -4
==424411== All heap blocks were freed -- no leaks are possible
==424411==
==424411== For lists of detected and suppressed errors, rerun with: -s
==424411== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

(O palavras.c é a solução da missão final. All heap blocks were freed = "todos os blocos do heap foram liberados".)

7. A árvore torta

A busca rápida depende de a árvore ser "baixa e larga". Mas o formato depende da ordem em que os valores chegam. Se eles chegarem já em ordem crescente, cada um é maior que todos os anteriores e vai sempre para a direita:

Este programa insere 1000 números em ordem numa árvore e 1000 números embaralhados em outra. Para os números "embaralhados" saírem iguais em qualquer computador, ele usa um sorteador próprio no lugar do rand() (que dá números diferentes no editor e no gcc; veja Números Aleatórios):

…                                    // No, inserir e liberar como antes

int altura(const No *raiz) {
    if (raiz == NULL) {
        return 0;
    }
    int e = altura(raiz->esq);
    int d = altura(raiz->dir);
    return 1 + (e > d ? e : d);
}

// Gerador de números "embaralhados" que dá a mesma sequência em qualquer computador
unsigned int semente = 12345;
unsigned int sortear(void) {
    semente = semente * 1103515245u + 12345u;
    return (semente / 65536u) % 32768u;
}

int main(void) {
    No *em_ordem = NULL;
    No *embaralhada = NULL;
    for (int i = 1; i <= 1000; i++) {
        em_ordem = inserir(em_ordem, i);
        embaralhada = inserir(embaralhada, (int)sortear());
    }
    printf("1000 números em ordem:     altura %d\n", altura(em_ordem));
    printf("1000 números embaralhados: altura %d\n", altura(embaralhada));
    liberar(em_ordem);
    liberar(embaralhada);
    return 0;
}

$ gcc -std=c23 -Wall -Wextra torta.c -o torta
$ ./torta
1000 números em ordem:     altura 1000
1000 números embaralhados: altura 23

Com os números em ordem, buscar o último exige descer 1000 nós, como numa lista. Embaralhados, nunca mais que 23. Por isso as bibliotecas de verdade usam árvores balanceadas, que se reorganizam a cada inserção para continuar baixas. As mais conhecidas são a AVL e a rubro-negra (red-black tree). Elas são assunto para um curso de estruturas de dados; a ideia desta aula continua valendo nelas.

Formas diferentes

Inserir com um laço e ponteiro para ponteiro

O inserir recursivo devolve a raiz, e quem chama precisa guardá-la. Uma alternativa é passar o endereço da raiz (um ponteiro para ponteiro, No **) e descer com um laço até o lugar vazio:

#include <stdio.h>
#include <stdlib.h>

typedef struct No {
    int valor;
    struct No *esq;
    struct No *dir;
} No;

bool inserir(No **raiz, int valor) {
    No **lugar = raiz;
    while (*lugar != NULL) {
        if (valor < (*lugar)->valor) {
            lugar = &(*lugar)->esq;
        } else if (valor > (*lugar)->valor) {
            lugar = &(*lugar)->dir;
        } else {
            return true;
        }
    }
    No *n = malloc(sizeof *n);
    if (n == NULL) {
        return false;
    }
    n->valor = valor;
    n->esq = NULL;
    n->dir = NULL;
    *lugar = n;
    return true;
}

void em_ordem(const No *raiz) {
    if (raiz == NULL) {
        return;
    }
    em_ordem(raiz->esq);
    printf("%d ", raiz->valor);
    em_ordem(raiz->dir);
}

void liberar(No *raiz) {
    if (raiz == NULL) {
        return;
    }
    liberar(raiz->esq);
    liberar(raiz->dir);
    free(raiz);
}

int main(void) {
    int numeros[] = {50, 30, 70, 20, 40, 60, 80};
    No *raiz = NULL;
    for (int i = 0; i < 7; i++) {
        if (!inserir(&raiz, numeros[i])) {
            fprintf(stderr, "Sem memória\n");
            liberar(raiz);
            return 1;
        }
    }
    em_ordem(raiz);
    printf("\n");
    liberar(raiz);
    return 0;
}

$ gcc -std=c23 -Wall -Wextra iterativo.c -o iterativo
$ ./iterativo
20 30 40 50 60 70 80

No **lugar = raiz;

lugar guarda o endereço do ponteiro onde o nó novo vai ser pendurado. No começo é o endereço da variável raiz do main.

lugar = &(*lugar)->esq;

*lugar é o nó atual; (*lugar)->esq é o ponteiro do filho esquerdo dele; o & pega o endereço desse ponteiro. Assim, quando o laço parar, lugar aponta exatamente para o esq ou dir que está em NULL.

*lugar = n;

Pendura o nó novo ali. Se a árvore estava vazia, isso muda a própria raiz do main.

bool inserir(…)

Como a raiz não precisa ser devolvida, o retorno fica livre para dizer se o malloc deu certo, e o main não precisa encerrar o programa dentro de inserir.

Qual usar

Para buscar, o laço é o mais natural (só um caminho). Para percorrer, contar, medir e liberar, a recursão é o mais natural (os dois lados).

Árvore, lista ou array ordenado?

• Poucos dados (dezenas): um array, ou uma lista. A diferença de tempo nem aparece.
• Muitos dados, buscas frequentes, inserções no meio do caminho: árvore de busca (de preferência balanceada).
• Muitos dados que mudam pouco: um array ordenado com qsort e procurado com bsearch. É mais simples e gasta menos memória.
• Só procurar pela chave exata, sem precisar de ordem: uma tabela hash costuma ser ainda mais rápida.

Quando dá errado

    No *raiz = NULL;
    for (int i = 0; i < 3; i++) {
        inserir(raiz, numeros[i]);      // faltou o "raiz ="
    }
    if (raiz == NULL) {
        printf("A árvore está vazia!\n");
    }

$ gcc -std=c23 -Wall -Wextra -g sem_retorno.c -o sem_retorno
$ ./sem_retorno
A árvore está vazia!
$ valgrind --leak-check=full ./sem_retorno 2>&1 | grep -A3 'definitely lost in'
==417713== 72 bytes in 3 blocks are definitely lost in loss record 1 of 1
==417713==    at 0x4850858: malloc (vg_replace_malloc.c:447)
==417713==    by 0x40011CC: inserir (sem_retorno.c:12)
==417713==    by 0x40012B8: main (sem_retorno.c:33)

$ gcc -std=c23 -Wall -Wextra nodiscard.c -o nodiscard
nodiscard.c: In function ‘main’:
nodiscard.c:33:9: warning: ignoring return value of ‘inserir’, declared with attribute ‘nodiscard’ [-Wunused-result]
   33 |         inserir(raiz, numeros[i]);
      |         ^~~~~~~~~~~~~~~~~~~~~~~~~
nodiscard.c:10:19: note: declared here
   10 | [[nodiscard]] No *inserir(No *raiz, int valor) {
      |                   ^~~~~~~

void em_ordem(const No *raiz) {
    em_ordem(raiz->esq);        // faltou: if (raiz == NULL) return;
    printf("%d ", raiz->valor);
    em_ordem(raiz->dir);
}

$ gcc -std=c23 -Wall -Wextra sem_base.c -o sem_base
sem_base.c: In function ‘em_ordem’:
sem_base.c:21:6: warning: infinite recursion detected [-Winfinite-recursion]
   21 | void em_ordem(const No *raiz) {
      |      ^~~~~~~~
sem_base.c:22:5: note: recursive call
   22 |     em_ordem(raiz->esq);
      |     ^~~~~~~~~~~~~~~~~~~
$ ./sem_base
Falha de segmentação     (imagem do núcleo gravada) ./sem_base

void liberar(No *raiz) {
    if (raiz == NULL) {
        return;
    }
    free(raiz);
    liberar(raiz->esq);   // raiz já foi devolvida!
    liberar(raiz->dir);
}

$ gcc -std=c23 -Wall -Wextra -g liberar_errado.c -o liberar_errado
liberar_errado.c: In function ‘liberar’:
liberar_errado.c:27:17: warning: pointer ‘raiz’ used after ‘free’ [-Wuse-after-free]
   27 |     liberar(raiz->dir);
      |             ~~~~^~~~~
liberar_errado.c:25:5: note: call to ‘free’ here
   25 |     free(raiz);
      |     ^~~~~~~~~~
liberar_errado.c:26:17: warning: pointer ‘raiz’ used after ‘free’ [-Wuse-after-free]
   26 |     liberar(raiz->esq);
      |             ~~~~^~~~~
liberar_errado.c:25:5: note: call to ‘free’ here
   25 |     free(raiz);
      |     ^~~~~~~~~~
$ ./liberar_errado
free(): invalid pointer
Abortado                   (imagem do núcleo gravada) ./liberar_errado
$ valgrind -q ./liberar_errado 2>&1 | head -10
==417373== Invalid read of size 8
==417373==    at 0x400122D: liberar (liberar_errado.c:26)
==417373==    by 0x40012A5: main (liberar_errado.c:32)
==417373==  Address 0x4a8e108 is 8 bytes inside a block of size 24 free'd
==417373==    at 0x48538BF: free (vg_replace_malloc.c:990)
==417373==    by 0x4001228: liberar (liberar_errado.c:25)
==417373==    by 0x40012A5: main (liberar_errado.c:32)
==417373==  Block was alloc'd at
==417373==    at 0x4850858: malloc (vg_replace_malloc.c:447)
==417373==    by 0x40011C9: novo (liberar_errado.c:11)

Referência rápida

Exercícios

Missão final: as frutas da feira em ordem alfabética

abacate 1
acerola 1
banana 1
caju 2
goiaba 1
manga 2
uva 1

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct No {
    const char *palavra;
    int vezes;
    struct No *esq;
    struct No *dir;
} No;

No *inserir(No *raiz, const char *palavra) {
    if (raiz == NULL) {
        No *n = malloc(sizeof *n);
        if (n == NULL) {
            fprintf(stderr, "Sem memória\n");
            exit(1);
        }
        n->palavra = palavra;
        n->vezes = 1;
        n->esq = NULL;
        n->dir = NULL;
        return n;
    }
    // COMPLETE: compare as palavras com strcmp(palavra, raiz->palavra)
    //   menor que 0 -> insira na esquerda
    //   maior que 0 -> insira na direita
    //   igual a 0   -> a palavra já está na árvore: some 1 em raiz->vezes
    return raiz;
}

void mostrar(const No *raiz) {
    if (raiz == NULL) {
        return;
    }
    mostrar(raiz->esq);
    printf("%s %d\n", raiz->palavra, raiz->vezes);
    mostrar(raiz->dir);
}

void liberar(No *raiz) {
    if (raiz == NULL) {
        return;
    }
    liberar(raiz->esq);
    liberar(raiz->dir);
    free(raiz);
}

int main(void) {
    const char *feira[] = {"banana", "manga", "caju", "abacate", "uva",
                           "manga", "goiaba", "caju", "acerola"};
    int n = sizeof feira / sizeof feira[0];
    No *raiz = NULL;
    for (int i = 0; i < n; i++) {
        raiz = inserir(raiz, feira[i]);
    }
    mostrar(raiz);
    liberar(raiz);
    return 0;
}

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct No {
    const char *palavra;
    int vezes;
    struct No *esq;
    struct No *dir;
} No;

No *inserir(No *raiz, const char *palavra) {
    if (raiz == NULL) {
        No *n = malloc(sizeof *n);
        if (n == NULL) {
            fprintf(stderr, "Sem memória\n");
            exit(1);
        }
        n->palavra = palavra;
        n->vezes = 1;
        n->esq = NULL;
        n->dir = NULL;
        return n;
    }
    int c = strcmp(palavra, raiz->palavra);
    if (c < 0) {
        raiz->esq = inserir(raiz->esq, palavra);
    } else if (c > 0) {
        raiz->dir = inserir(raiz->dir, palavra);
    } else {
        raiz->vezes++;
    }
    return raiz;
}

void mostrar(const No *raiz) {
    if (raiz == NULL) {
        return;
    }
    mostrar(raiz->esq);
    printf("%s %d\n", raiz->palavra, raiz->vezes);
    mostrar(raiz->dir);
}

void liberar(No *raiz) {
    if (raiz == NULL) {
        return;
    }
    liberar(raiz->esq);
    liberar(raiz->dir);
    free(raiz);
}

int main(void) {
    const char *feira[] = {"banana", "manga", "caju", "abacate", "uva",
                           "manga", "goiaba", "caju", "acerola"};
    int n = sizeof feira / sizeof feira[0];
    No *raiz = NULL;
    for (int i = 0; i < n; i++) {
        raiz = inserir(raiz, feira[i]);
    }
    mostrar(raiz);
    liberar(raiz);
    return 0;
}

Repare que o mostrar é a em ordem de sempre, só que com palavras. As frutas foram vendidas fora de ordem e saíram em ordem alfabética, sem nenhum qsort. O strcmp compara pelos códigos dos caracteres; com acentos ("maçã") a ordem já não é a do dicionário (veja Acentos e UTF-8).

Resumo

• Uma árvore binária é feita de nós com um valor e dois ponteiros, esq e dir; filho que não existe vale NULL. O nó do topo é a raiz; os nós sem filhos são as folhas.
• Percorrer a árvore é natural com recursão, sempre com o caso base if (raiz == NULL). Em ordem (esquerda, raiz, direita), pré-ordem (raiz primeiro) e pós-ordem (raiz por último).
• Numa árvore de busca, os menores ficam à esquerda e os maiores à direita. Inserir e buscar seguem um caminho só, da raiz até, no máximo, uma folha; a em ordem mostra tudo ordenado.
• raiz = inserir(raiz, v);: guarde sempre o retorno (ou use [[nodiscard]], ou a versão com No **).
• Libere em pós-ordem: os filhos antes do pai. Confira com o valgrind.
• Valores que chegam em ordem deixam a árvore torta (altura = número de nós), e ela perde a vantagem. As árvores balanceadas (AVL, rubro-negra) resolvem isso.