INF01203 - Estruturas de Dados - Instituto de Informática (UFRGS) - Prof. Dennis Giovani Balreira


Aula 11 - Árvores, Árvores Binárias e Caminhamentos

Até agora vimos apenas estruturas lineares (vetores e listas), em que cada elemento tem no máximo um sucessor. Nesta aula iniciamos o estudo das árvores, estruturas hierárquicas em que um elemento pode ter vários sucessores. Veremos os conceitos gerais de árvores, como representá-las, como convertê-las em árvores binárias, por que a recursão é a ferramenta natural para trabalhar com árvores, e quais são os principais caminhamentos (percursos) sobre árvores binárias. As operações da Árvore Binária de Pesquisa serão vistas na Aula 12.

Por que aprender árvores?

Árvores não são uma abstração acadêmica — elas aparecem em praticamente todo sistema computacional. Antes de entrar nos conceitos formais, vale ver onde elas surgem na prática:

  • Sistemas de arquivos (sistemas operacionais). O diretório raiz (/ no Linux, C:\ no Windows) é a raiz de uma árvore. Cada pasta é um nó interno; cada arquivo é uma folha. Operações como "listar recursivamente todos os arquivos de um diretório" ou "calcular o tamanho total de uma pasta" são, literalmente, caminhamentos em árvore sobre o sistema de arquivos. 
    /
├── home/
│   └── dennis/
│       ├── documentos/
│       └── fotos/
├── etc/
│   └── hosts
└── usr/
    └── bin/
        └── gcc
  • Bancos de dados e índices. A estrutura interna de um índice de banco de dados — seja uma B-tree, uma B+-tree ou uma árvore AVL — é a razão pela qual uma consulta com WHERE id = 42 encontra um registro entre milhões em milissegundos, em vez de varrer a tabela inteira. Sem árvores equilibradas, bancos de dados modernos não existiriam na forma que conhecemos.
  • Compiladores e interpretadores. Quando o compilador lê a = (b + c) * d, ele constrói internamente uma Árvore Sintática Abstrata (AST — Abstract Syntax Tree) que representa a estrutura da expressão. A geração de código e a análise semântica são caminhamentos sobre essa árvore. 
           =
      / \
     a   *
        / \
       +   d
      / \
     b   c
  • HTML e XML (DOM). Uma página web é uma árvore: o elemento <html> é a raiz, <head> e <body> são filhos, e assim por diante. O navegador percorre essa árvore para renderizar a página; o JavaScript navega por ela via document.getElementById() e similares.
  • Compressão de dados. O algoritmo de Huffman (usado em formatos como ZIP, JPEG e MP3) constrói uma árvore binária onde os caracteres mais frequentes ficam nas folhas mais rasas (caminho mais curto = menos bits). Veremos isso na Aula 27.
  • Inteligência artificial e jogos. Algoritmos como Minimax (xadrez, damas, Go) e Monte Carlo Tree Search exploram uma árvore de jogo: cada nó representa um estado do tabuleiro, e cada ramo representa uma jogada possível. A busca em profundidade (DFS) que veremos hoje é a base desses algoritmos.

Em todos esses casos, o que torna as árvores úteis é a mesma propriedade: a hierarquia natural dos dados e, quando a árvore está equilibrada, a possibilidade de localizar qualquer elemento em tempo O(log n) — muito mais eficiente do que a busca linear O(n) em uma lista.

1. O que é uma árvore?

Uma árvore é uma estrutura de dados que organiza elementos em uma hierarquia: cada elemento (chamado de nó) pode ter zero ou mais nós "abaixo" dele, e todo nó (exceto um) tem exatamente um nó "acima" dele. É a mesma ideia de uma árvore genealógica, do sistema de pastas de um computador, ou da estrutura de capítulos e seções de um livro. 

                 A          <- raiz (nível 0)
               / | \
              B  C  D        <- nível 1
             /|      \
            E F       G      <- nível 2
            |
            H                <- nível 3 (folha)

Principais conceitos:

  • Nó (ou nodo): cada elemento da árvore (na figura, cada letra).
  • Raiz: o único nó sem pai — o "topo" da árvore (A).
  • Pai / filho: se B está diretamente abaixo de A, então A é pai de B, e B é filho de A.
  • Irmãos: nós que têm o mesmo pai (B, C e D são irmãos).
  • Folha: nó sem nenhum filho (C, F, G, H).
  • Nó interno: nó com pelo menos um filho (A, B, D, E).
  • Grau de um nó: número de filhos que ele tem (grau de A é 3; grau de B é 2; grau de C é 0).
  • Subárvore: um nó qualquer, junto com todos os seus descendentes, forma uma árvore "menor" dentro da árvore original (a subárvore de B contém B, E, F, H).
  • Nível (ou profundidade) de um nó: número de arestas do caminho da raiz até ele (raiz está no nível 0; B, C, D estão no nível 1).
  • Altura de um nó: maior número de arestas do caminho desse nó até uma folha de sua subárvore (altura de E é 1; altura de uma folha é 0).
  • Altura da árvore: altura da raiz (nesta figura, 3).
⚠ Convenção adotada nesta disciplina: altura = número de arestas.

Existem duas convenções comuns na literatura:
  • Altura = número de arestas (caminho mais longo até uma folha) — adotada aqui.
  • Altura = número de nós no caminho mais longo — encontrada em alguns livros.
Com a convenção de arestas:
  • Uma árvore com um único nó (a própria raiz, que é também folha) tem altura 0.
  • Uma árvore vazia (NULL) tem altura −1 por convenção — o que torna a fórmula recursiva natural: altura(raiz) = 1 + max(altura(esq), altura(dir)), com caso base altura(NULL) = −1.
  • Uma árvore binária perfeita de altura h tem exatamente 2h+1 − 1 nós e 2h folhas — fórmulas que só “fecham” naturalmente com essa convenção.
  • Uma ABP equilibrada com n nós tem altura Θ(log2 n), pois 2h+1 − 1 ≥ n ⇒ h ≥ log2(n+1) − 1.
Quando encontrar "altura" em outro material, verifique qual convenção ele usa antes de comparar fórmulas.
Por que árvores? Estruturas lineares (vetores, listas) são ótimas para representar sequências, mas não representam bem relações hierárquicas nem permitem busca eficiente sem estar totalmente ordenadas. Árvores bem construídas permitem buscar, inserir e remover em tempo proporcional à altura da árvore — que, se ela estiver "bem formada", é muito menor que n (o número de elementos).

2. Representando árvores genéricas

Numa árvore genérica, um nó pode ter qualquer número de filhos, o que dificulta representá-la diretamente em C (um struct precisaria de um número fixo de ponteiros, ou de uma lista de filhos de tamanho variável). Duas formas comuns:

  • Vetor de ponteiros para filhos: cada nó guarda um vetor (de tamanho fixo, ou dinâmico) de ponteiros para seus filhos. Simples de entender, mas desperdiça memória quando o grau máximo é grande e a maioria dos nós tem poucos filhos.
  • Lista encadeada de filhos: cada nó guarda um ponteiro para o primeiro filho e um ponteiro para o próximo irmão — a representação "filho-esquerdo, irmão-direito" (left-child, right-sibling).
typedef struct str_NodoGen NodoGen;

struct str_NodoGen {
    Produto dado;
    NodoGen *primeiroFilho;   // aponta para o filho mais à esquerda
    NodoGen *proximoIrmao;    // aponta para o próximo filho do MESMO pai
};

Conversão de árvore genérica para árvore binária

A representação "filho-esquerdo, irmão-direito" é, na verdade, uma árvore binária disfarçada: basta reinterpretar primeiroFilho como o ponteiro esquerdo e proximoIrmao como o ponteiro direito. É assim que qualquer árvore genérica pode ser convertida (sem perda de informação) em uma árvore binária: 

Árvore genérica:              Convertida (esq = filho, dir = irmão):

       A                              A
     / | \                           /
    B  C  D                         B
   /|      \                       / \
  E F       G                     E   C
  |                               / \   \
  H                              H   F   D
                                         /
                                        G

A ideia é simples: o ponteiro esquerdo de cada nó aponta para o seu primeiro filho, e o ponteiro direito aponta para o seu próximo irmão. Os demais filhos de um nó formam uma corrente encadeada via ponteiros direitos a partir do primeiro filho.

Note que G fica à esquerda de D (G era filho de D, logo ocupa o ponteiro esquerdo), e H fica à esquerda de E com F à direita (H era filho de E, F era irmão de E). Um erro comum é confundir filho com irmão e colocar G à direita de D.

Essa conversão é útil porque permite reaproveitar toda a teoria (e o código) de árvores binárias para representar árvores de grau qualquer — sem perda de informação.

Conversão inversa: de árvore binária de volta à árvore genérica

A operação é completamente reversível com a interpretação oposta: o ponteiro esquerdo de um nó indica o seu primeiro filho na árvore original, e os demais filhos são obtidos seguindo os ponteiros direitos consecutivos a partir dele até encontrar NULL. 

Árvore binária:                Recuperada (esq = filho, dir = irmão):

       A                              A
      /                             / | \
     B                             B  C  D
    / \                           /|      \
   E   C                         E F       G
  / \   \                        |
 H   F   D                       H
        /
       G

Para recuperar filhos de A: começa em A.esq = B, segue pelos dir: B → C → D → NULL.
Para recuperar filhos de B: começa em B.esq = E, segue pelos dir: E → F → NULL.
Para recuperar filhos de E: começa em E.esq = H, H.dir = NULL → só H.
Para recuperar filhos de D: começa em D.esq = G, G.dir = NULL → só G.
A conversão é bijetora. Toda árvore genérica se mapeia em exatamente uma árvore binária, e toda árvore binária assim produzida se mapeia de volta na original. Não há ambiguidade em nenhuma direção.

3. Por que árvores "pedem" recursão

Antes de entrar em árvores binárias especificamente, vale entender por que praticamente todo algoritmo sobre árvores (caminhamentos, busca, inserção, remoção, altura, destruição) é escrito de forma recursiva. Não é estilo — é que a própria definição de árvore já é recursiva:

Uma árvore é definida em termos de árvores menores. Uma árvore binária é: (a) vazia (NULL), ou (b) um nó com um valor, cuja subárvore esquerda é uma árvore binária e cuja subárvore direita é uma árvore binária. A definição usa "árvore binária" dentro da própria definição de árvore binária — é uma definição recursiva, assim como a definição de lista encadeada (Aula 4) também é ("uma lista é vazia, ou um nó seguido de uma lista").

Como a estrutura é auto-similar (cada subárvore é, ela mesma, uma árvore completa), qualquer operação sobre uma árvore pode ser descrita assim:

  • Caso base: o que fazer quando a árvore (ou subárvore) é vazia (no == NULL) — geralmente a operação mais simples possível: não faz nada, retorna NULL, retorna 0, etc.
  • Caso recursivo: resolver o problema para as subárvores esquerda e direita (chamando a mesma função nelas — elas são árvores também), e combinar os dois resultados com o valor do nó atual.

É exatamente esse padrão que vamos ver nos caminhamentos a seguir: cada um chama a si mesmo sobre as subárvores esquerda e direita. Na Aula 12, as próprias operações da Abp (busca, inserção, remoção) seguirão exatamente essa mesma estrutura.

A alternativa — escrever essas operações de forma iterativa (com laços, sem recursão) — é possível, mas exige montar manualmente uma pilha própria para lembrar "aonde voltar" depois de descer por um ramo (é exatamente o que a pilha de chamadas da recursão já faz de graça). Por isso a recursão não é só mais curta de escrever para árvores: ela espelha diretamente a definição recursiva da estrutura, tornando o código mais próximo do raciocínio matemático sobre o problema.

4. Árvores binárias

Uma árvore binária é uma árvore em que todo nó tem no máximo dois filhos, distinguidos como filho esquerdo e filho direito (mesmo que um nó tenha um único filho, ele é obrigatoriamente "esquerdo" ou "direito" — não existe filho "sem lado").

  • Árvore binária cheia (ou completa): todo nó tem 0 ou 2 filhos (nenhum nó com exatamente 1 filho).
  • Árvore binária perfeita: todos os níveis estão totalmente preenchidos (uma árvore perfeita de altura h tem exatamente 2^(h+1) - 1 nós).
  • Árvore binária balanceada: para todo nó, a altura das subárvores esquerda e direita difere no máximo por uma constante (garante altura O(log n); veremos formalmente na Aula 15).
  • Árvore degenerada: cada nó tem no máximo um filho — vira, na prática, uma lista encadeada, com altura O(n).

Representação em C: cada nó guarda o dado e dois ponteiros, esq e dir: 

typedef struct {
    int cod;
    char nome[50];
    float preco;
} Produto;

typedef struct str_NodoArv NodoArv;

struct str_NodoArv {
    Produto dado;
    NodoArv *esq;
    NodoArv *dir;
};

A variável que representa a árvore inteira é o ponteiro para o nó raiz: NodoArv *raiz (ou NULL, se a árvore estiver vazia). "Inicializar" uma árvore binária é simplesmente declarar NodoArv *raiz = NULL;.

5. Caminhamentos (percursos)

Caminhar (ou percorrer) uma árvore significa visitar todos os seus nós em alguma ordem sistemática. Ao contrário de uma lista, uma árvore não tem uma única ordem "natural" de percurso — existem quatro caminhamentos clássicos. Os três primeiros são definidos recursivamente e recebem seus nomes de acordo com a posição em que a raiz é visitada em relação às suas subárvores: 

Pré-ordem          (RAIZ, esquerda, direita)   <-- raiz ANTES das subárvores
Em-ordem (central) (esquerda, RAIZ, direita)   <-- raiz NO MEIO das subárvores
Pós-ordem          (esquerda, direita, RAIZ)   <-- raiz DEPOIS das subárvores
Em nível           (visita nível 0, nível 1, nível 2, ...)

O prefixo pré- indica que a raiz vem antes das subárvores; pós- indica que vem depois; e o caminhamento do meio — também chamado de central — visita a raiz entre as duas subárvores. O quarto caminhamento, em nível, não segue esse padrão de posição da raiz: ele percorre a árvore em largura, nível por nível.

DFS × BFS

Os quatro caminhamentos se agrupam em duas famílias, de acordo com a estratégia usada para decidir qual nó visitar em seguida:

  • DFS (depth-first search, busca em profundidade): pré-ordem, em-ordem (central) e pós-ordem. A ideia é mergulhar o mais fundo possível por um ramo antes de voltar (backtrack) e explorar outro. É exatamente o que a recursão faz "de graça", usando a pilha de chamadas da linguagem como estrutura auxiliar implícita.
  • BFS (breadth-first search, busca em largura): o caminhamento em nível. A ideia é visitar tudo o que está "mais perto" da raiz antes de avançar para o que está mais longe, nível por nível.

Resumindo a relação entre estratégia, estrutura de dados e forma de implementação: 

DFS (pré/em/pós-ordem)  -->  PILHA (LIFO)  -->  natural via RECURSÃO
BFS (em nível)          -->  FILA  (FIFO)  -->  natural via LAÇO + fila explícita
Por que BFS usa fila e DFS usa pilha? No DFS, quando descemos por um ramo, empilhamos implicitamente os nós "a visitar depois" na pilha de chamadas da recursão (LIFO) — o último ramo aberto é o primeiro a ser explorado. No BFS, queremos visitar todos os nós de um nível antes de avançar ao próximo: os filhos descobertos agora só devem ser visitados depois de todos os nós do nível atual, o que exige uma estrutura FIFO — exatamente uma fila. É possível escrever uma versão recursiva do BFS, mas ela continua dependendo de uma fila explícita passada entre as chamadas; a recursão não elimina a necessidade da fila, só reorganiza o código em torno dela. Por isso, na prática, o BFS é quase sempre escrito de forma iterativa.

Com esse quadro em mente, vejamos a implementação de cada caminhamento: 

void preOrdem(const NodoArv *raiz) {
    if (raiz == NULL) return;   // caso base: subárvore vazia

    printf("%d ", raiz->dado.cod);   // 1. visita a RAIZ (antes)
    preOrdem(raiz->esq);              // 2. depois a esquerda
    preOrdem(raiz->dir);              // 3. depois a direita
}

void emOrdem(const NodoArv *raiz) {   // também chamado: central
    if (raiz == NULL) return;

    emOrdem(raiz->esq);               // 1. primeiro a esquerda
    printf("%d ", raiz->dado.cod);   // 2. visita a RAIZ (no meio)
    emOrdem(raiz->dir);               // 3. depois a direita
}

void posOrdem(const NodoArv *raiz) {
    if (raiz == NULL) return;

    posOrdem(raiz->esq);              // 1. primeiro a esquerda
    posOrdem(raiz->dir);              // 2. depois a direita
    printf("%d ", raiz->dado.cod);   // 3. visita a RAIZ (depois)
}

O caminhamento em nível (BFS) não é recursivo: usa uma fila (Aula 9b) para visitar os nós nível por nível, da esquerda para a direita.

A FilaEnc da Aula 9b guarda Produto no campo dado de cada nodo. Para a BFS em árvore, adaptamos o TAD trocando Produto por NodoArv* e fazendo dequeue retornar o ponteiro diretamente (em vez de receber parâmetro de saída): 

/* Adaptação do TAD FilaEnc para armazenar NodoArv* */
typedef struct str_NodoFila {
    NodoArv *dado;                 // em vez de Produto dado
    struct str_NodoFila *prox;
} NodoFila;

typedef struct {
    NodoFila *frente;
    NodoFila *final;
} FilaArv;

void     inicializa (FilaArv *f);
int      estaVazia  (const FilaArv *f);
void     enqueue    (FilaArv *f, NodoArv *no);
NodoArv* dequeue    (FilaArv *f);              // retorna o ponteiro diretamente
A fila guarda endereços, não nós. O campo dado de cada NodoFila é um NodoArv* — um endereço de nó da árvore, não uma cópia do nó. Isso é intencional: copiar o nó inteiro (com seus dois ponteiros filhos) quebraria a estrutura da árvore, pois as cópias não estariam ligadas a nada. Ao guardar apenas o endereço, a fila sabe onde cada nó está na memória e pode acessar seus filhos normalmente via no->esq e no->dir.

Com essa interface, o emNivel fica:

void emNivel(NodoArv *raiz) {
    FilaArv fila;
    NodoArv *no;

    inicializa(&fila);
    if (raiz != NULL) enqueue(&fila, raiz);

    while (!estaVazia(&fila)) {
        no = dequeue(&fila);
        printf("%d ", no->dado.cod);

        // enqueue os filhos — serão visitados DEPOIS de todos os do nível atual
        if (no->esq != NULL) enqueue(&fila, no->esq);
        if (no->dir != NULL) enqueue(&fila, no->dir);
    }
}

Exemplo

        50
       /  \
     30    70
    /  \   /  \
  20   40 60   80

Pré-ordem: 50 30 20 40 70 60 80   (raiz sempre antes das subárvores)
Em-ordem:  20 30 40 50 60 70 80   (nesta árvore, sai em ORDEM CRESCENTE!)
Pós-ordem: 20 40 30 60 80 70 50   (raiz sempre depois das subárvores)
Em nível:  50 30 70 20 40 60 80   (nível 0, depois nível 1, depois nível 2)
Em-ordem não é coincidência. Visitar uma árvore em-ordem produz os elementos em ordem crescente sempre que a árvore satisfaz a propriedade de Árvore Binária de Pesquisa — que é exatamente o assunto da Aula 12.

Resumo

  • Árvore: estrutura hierárquica; conceitos-chave: raiz, pai/filho, folha, subárvore, nível, altura.
  • Árvore genérica: representada com vetor de filhos, ou com "filho-esquerdo, irmão-direito" — essa segunda forma é uma árvore binária, e permite converter qualquer árvore genérica em binária sem perda de informação.
  • Recursão em árvores: natural porque a definição de árvore é recursiva (árvore = nó + subárvore esquerda + subárvore direita). O padrão é: caso base para NULL, e chamadas recursivas para as subárvores esquerda e direita.
  • Árvore binária: cada nó tem no máximo 2 filhos (esquerdo e direito). Tipos: cheia, perfeita, balanceada, degenerada.
  • Caminhamentos DFS: pré-ordem (raiz, esq, dir), em-ordem / central (esq, raiz, dir), pós-ordem (esq, dir, raiz) — os nomes referem-se à posição da raiz; todos recursivos, usam pilha implícita.
  • Caminhamento BFS (em nível): visita nível por nível, da esquerda para a direita — iterativo, usa fila explícita.

Exercícios

  1. Defina, com suas palavras, os termos raiz, folha, altura de um nó e altura da árvore.
  2. Explique como a representação "filho-esquerdo, irmão-direito" permite converter qualquer árvore genérica em uma árvore binária. Por que essa conversão não perde nenhuma informação da árvore original?
  3. Por que a definição recursiva de árvore torna a recursão a abordagem natural para implementar algoritmos sobre árvores? Como essa mesma ideia aparece nos caminhamentos?
  4. Dada a árvore binária abaixo, escreva a sequência de valores visitados em pré-ordem, em-ordem, pós-ordem e em nível: 
            60
       /  \
     30    80
    /  \      \
  10   40     90
  5. Explique a diferença entre DFS e BFS. Qual estrutura de dados cada um usa internamente, e por quê?
  6. É possível reconstruir uma árvore binária conhecendo apenas sua sequência em pré-ordem? E conhecendo apenas em-ordem? E conhecendo as duas juntas (pré-ordem + em-ordem)? Justifique.
  7. Escreva uma função int contarNos(const NodoArv *raiz) que retorna o número de nós de uma árvore binária. Use recursão e explique o raciocínio.
  8. Escreva uma função int contarFolhas(const NodoArv *raiz) que retorna o número de folhas de uma árvore binária.

Sugestões de Respostas dos Exercícios

Exercício 1

Raiz: o único nó da árvore que não tem pai — o nó "no topo" da hierarquia. Folha: um nó que não tem nenhum filho. Altura de um nó: o maior número de arestas em um caminho desse nó até uma folha de sua subárvore (uma folha tem altura 0). Altura da árvore: a altura do nó raiz — ou seja, o maior número de arestas entre a raiz e a folha mais distante.


Exercício 2

Cada nó guarda um ponteiro para seu primeiro filho (o mais à esquerda) e um ponteiro para o seu próximo irmão (o filho seguinte do mesmo pai). Reinterpretando "primeiro filho" como o filho esquerdo e "próximo irmão" como o filho direito, obtém-se uma árvore binária válida. Nenhuma informação é perdida porque, a partir de qualquer nó, ainda é possível reconstruir todos os seus filhos originais: o primeiro filho é o ponteiro esquerdo, e os demais filhos formam uma "corrente" encadeada pelos ponteiros direitos a partir dele.


Exercício 3

A definição de árvore já é recursiva: uma árvore binária é vazia, ou é um nó com uma subárvore esquerda (que é uma árvore binária) e uma subárvore direita (que também é uma árvore binária). Como a estrutura se repete nos próprios componentes, qualquer operação pode ser resolvida pelo mesmo raciocínio: (a) caso base — o que fazer quando a árvore está vazia (raiz == NULL); (b) caso recursivo — aplicar a operação à subárvore esquerda e à direita, e combinar os resultados com o nó atual. Os caminhamentos seguem exatamente esse padrão: cada um faz uma chamada recursiva sobre esq e outra sobre dir, diferindo apenas no momento em que visita o nó atual (antes, entre ou depois das chamadas).


Exercício 4 
Pré-ordem: 60 30 10 40 80 90
Em-ordem:  10 30 40 60 80 90
Pós-ordem: 10 40 30 90 80 60
Em nível:  60 30 80 10 40 90

Exercício 5

DFS mergulha o mais fundo possível antes de retroceder (backtrack) e explorar outro ramo. Usa uma pilha (LIFO) — implicitamente, via pilha de chamadas da recursão. BFS explora todos os nós de um nível antes de avançar ao próximo. Usa uma fila (FIFO) — explicitamente, porque a ordem FIFO é o que garante que todos os nós do nível atual sejam visitados antes dos do nível seguinte.


Exercício 6

Apenas pré-ordem: não é suficiente — a mesma sequência pré-ordem pode corresponder a diferentes árvores. Apenas em-ordem: também não é suficiente pelo mesmo motivo. Pré-ordem + em-ordem juntas: sim, é possível reconstruir a árvore de forma única (desde que não haja valores repetidos). O primeiro elemento da pré-ordem é sempre a raiz. Encontrando esse valor na em-ordem, os elementos à sua esquerda formam a subárvore esquerda, e os da direita formam a subárvore direita — e o processo se aplica recursivamente.


Exercício 7 
int contarNos(const NodoArv *raiz) {
    if (raiz == NULL) return 0;   // árvore vazia: 0 nós
    return 1 + contarNos(raiz->esq) + contarNos(raiz->dir);
    // 1 (este nó) + nós na subárvore esquerda + nós na subárvore direita
}

Raciocínio: o número de nós de uma árvore é 1 (o nó atual) mais o número de nós na subárvore esquerda mais o da direita. Caso base: árvore vazia tem 0 nós.


Exercício 8 
int contarFolhas(const NodoArv *raiz) {
    if (raiz == NULL) return 0;
    if (raiz->esq == NULL && raiz->dir == NULL) return 1;   // é folha
    return contarFolhas(raiz->esq) + contarFolhas(raiz->dir);
}