Árvores binárias e percursos

Uma árvore binária é vazia ou tem uma raiz e duas subárvores binárias, esquerda e direita. A posição de cada filho importa. Não existe, por definição, qualquer ordenação dos valores: uma árvore binária de pesquisa acrescenta essa propriedade na página seguinte.

Esta página fixa vocabulário de forma e percursos antes de usares a ordem das BST. Precisas apenas de recursão e pilha de chamadas das lições de complexidade.

Forma, altura e profundidade

A raiz é o nó sem pai. O pai é o nó diretamente acima; cada nó tem no máximo um pai. Uma folha é um nó sem filhos. A profundidade de um nó é o número de arestas da raiz até ele. A raiz tem profundidade zero. A altura de um nó é o maior número de arestas desse nó até uma folha. Adotamos altura -1 para a árvore vazia e 0 para uma folha. Alguns enunciados contam nós em vez de arestas; nesse caso os valores mudam em uma unidade.

Uma árvore completa tem todos os níveis preenchidos, exceto eventualmente o último, preenchido da esquerda para a direita. Uma árvore perfeita tem todos os níveis preenchidos. Uma árvore estrita tem zero ou dois filhos em cada nó. Estas condições são diferentes; «equilibrada» precisa de uma condição quantitativa sobre a altura.

Numa árvore de altura h, existem no máximo $2^d$ nós à profundidade d e no máximo $2^{h+1}-1$ nós no total. Logo uma árvore com n nós tem altura pelo menos $\lceil\log_2(n+1)\rceil-1$. Uma cadeia de n nós tem altura n-1, o máximo possível.

Recursão estrutural

Para contares nós, o vazio contribui zero e uma raiz contribui um mais os tamanhos das subárvores. Para a altura, o vazio contribui -1 e um nó contribui um mais o máximo das alturas dos filhos. Não somes as alturas, porque um caminho descendente escolhe um filho de cada vez.

A prova é por indução na estrutura. O resultado é correto para o vazio. Se as chamadas devolvem tamanhos corretos para as duas subárvores, somar esses tamanhos com a raiz conta todos os nós uma única vez. A mesma hipótese sobre alturas justifica escolher o caminho mais longo.

Cada nó é visitado uma vez: tempo $\Theta(n)$. A pilha tem no máximo um caminho da raiz à folha: espaço $O(h+1)$, que pode ser linear numa cadeia. Uma árvore de dimensão grande e desequilibrada pode exceder a pilha de chamadas, por isso usa um percurso iterativo quando os limites o exigem.

Pré-ordem, em-ordem e pós-ordem

A diferença está no momento em que visitas a raiz:

Começa na raiz 8. Em pré-ordem escreve-a antes de descer para 4. Em em-ordem suspende 8, visita toda a esquerda e só então a escreve. Em pós-ordem deixa 8 para depois das duas subárvores. Para a árvore desenhada, os percursos são pré-ordem 8 4 2 6 10 9, em-ordem 2 4 6 8 9 10 e pós-ordem 2 6 4 9 10 8. O percurso por níveis é 8 4 10 2 6 9.

#include <algorithm>
#include <iostream>
#include <vector>
enum class Ordem { pre, em, pos };
struct No { int valor, esq, dir; };
const std::vector<No> a{{8,1,2},{4,3,4},{10,5,-1},{2,-1,-1},{6,-1,-1},{9,-1,-1}};
int altura(int p) { return p == -1 ? -1 : 1 + std::max(altura(a[p].esq), altura(a[p].dir)); }
int tamanho(int p) { return p == -1 ? 0 : 1 + tamanho(a[p].esq) + tamanho(a[p].dir); }
void visitar(int p, Ordem ordem, std::vector<int>& r) {
    if (p == -1) return;
    if (ordem == Ordem::pre) r.push_back(a[p].valor);
    visitar(a[p].esq, ordem, r);
    if (ordem == Ordem::em) r.push_back(a[p].valor);
    visitar(a[p].dir, ordem, r);
    if (ordem == Ordem::pos) r.push_back(a[p].valor);
}
int main() {
    for (Ordem ordem : {Ordem::pre, Ordem::em, Ordem::pos}) {
        std::vector<int> r; visitar(0, ordem, r);
        for (std::size_t i = 0; i < r.size(); ++i)
            std::cout << (i ? " " : "") << r[i];
        std::cout << '\n';
    }
    std::cout << "nos: " << tamanho(0) << "; altura: " << altura(0) << '\n';
    std::cout << "vazia: " << tamanho(-1) << ' ' << altura(-1) << '\n';
}

Os índices dos filhos no programa referem-se a posições válidas do vetor, ou a -1 para ausência. A estrutura fixa não tem ciclos nem nós partilhados entre pais. Se permitisses essas situações, deixaria de ser uma árvore e as recorrências poderiam visitar nós várias vezes ou não terminar.

Calcular propriedades em pós-ordem

Para contar nós com exatamente dois filhos, soma os resultados das subárvores e acrescenta um apenas quando ambas as ligações existem. Uma folha e um nó com um filho contribuem zero. Na árvore da figura, só 8 e 4 contribuem, logo o resultado é 2.

Para decidir se a árvore é perfeita, não basta comparar as alturas dos filhos da raiz. Cada subárvore também tem de ser perfeita. Devolve em cada chamada um resumo com a altura, a perfeição e a contagem de nós com dois filhos:

• O vazio tem altura -1, contagem zero e é considerado perfeito neste contrato.
• Um nó é perfeito se as duas subárvores forem perfeitas e tiverem alturas iguais.
• A sua altura é um mais a maior altura; a contagem soma as dos filhos e a contribuição local.

#include <algorithm>
#include <iostream>
struct No { int valor; const No* esq; const No* dir; };
struct Resumo { bool perfeita; int altura; int binarios; };
Resumo resumir(const No* p) {
    if (!p) return {true, -1, 0};
    const auto e = resumir(p->esq), d = resumir(p->dir);
    return {e.perfeita && d.perfeita && e.altura == d.altura,
            1 + std::max(e.altura, d.altura),
            e.binarios + d.binarios + (p->esq && p->dir ? 1 : 0)};
}
void mostrar(const No* p) {
    const auto r = resumir(p);
    std::cout << "perfeita=" << r.perfeita << "; altura=" << r.altura
              << "; dois filhos=" << r.binarios << '\n';
}
int main() {
    const No a{1,nullptr,nullptr}, b{3,nullptr,nullptr};
    const No folhaDireita{6,nullptr,nullptr};
    const No c{2,&a,&b}, umFilho{4,&folhaDireita,nullptr};
    const No alturasIguais{5,&c,&umFilho};
    mostrar(nullptr); mostrar(&a); mostrar(&c); mostrar(&alturasIguais);
    return 0;
}

Os primeiros casos mostram o vazio, uma folha e uma raiz com duas folhas: todos perfeitos, com alturas -1, 0 e 1 e contagens 0, 0 e 1. O último caso tem dois filhos de altura 1, mas a subárvore direita só tem um filho. A altura da árvore é 2 e há dois nós com dois filhos, mas não é perfeita. Esta entrada revela por que a igualdade de alturas só na raiz seria insuficiente.

O argumento é indutivo: duas subárvores perfeitas de igual altura enchem todos os níveis até à mesma profundidade; acrescentar a raiz enche o nível anterior. Se faltar um filho, as alturas das subárvores perfeitas seriam -1 e pelo menos 0, diferentes. O método visita cada nó uma vez, dando $\Theta(n)$ de tempo e $O(h+1)$ de pilha. Recalcular a altura por um percurso completo em cada nó pode dar custo quadrático numa cadeia.

Reconstruir e representar

Com valores distintos, pré-ordem e em-ordem determinam a árvore: o primeiro valor da pré-ordem é a raiz; a sua posição na em-ordem separa os valores das subárvores. Os tamanhos dessas regiões separam a pré-ordem restante. Repete o procedimento nas duas regiões.

Para pré-ordem [8,4,2,6,10,9] e em-ordem [2,4,6,8,9,10], a raiz é 8 e a esquerda tem três nós. A pré-ordem esquerda começa em 4; na em-ordem esquerda, 2 fica antes de 4 e 6 depois. A direita começa em 10 e tem 9 à esquerda. Procurar a raiz por percurso linear em cada chamada pode dar custo quadrático; um mapa de posições localiza cada chave sem repetir esses percursos. Com uma tabela hash de consultas esperadas constantes, a reconstrução é esperada linear; com um mapa ordenado, custa O(n log n).

Pré-ordem sozinha não determina uma árvore binária genérica: [1,2] pode ter 2 à esquerda ou à direita. Marcas explícitas de vazio resolvem a ambiguidade; uma folha em pré-ordem torna-se valor, vazio, vazio. Com chaves repetidas, pré-ordem mais em-ordem pode voltar a ser ambígua.

Para contares nós à profundidade k, o vazio contribui zero; com k=0, um nó existente contribui um; caso contrário, soma os resultados dos filhos com k-1. Na árvore desenhada, as folhas são 2, 6 e 9, três no total; a profundidade 1 tem os nós 4 e 10. Contar folhas soma um por folha e zero no vazio. Para k<0, devolve zero. O algoritmo só precisa de visitar até ao nível pedido; o limite de pior caso continua $O(n)$.