# Árvores binárias

Nós, altura, travessias em pré-ordem, em ordem e pós-ordem, e reconstrução a partir de duas travessias.

Página: https://resumos.rgo.pt/cadeiras/aed/arvores-binarias/

Uma lista é uma fila de nós; uma árvore é uma hierarquia. Cada nó tem até dois filhos, e dessa regra simples nascem as travessias, a pesquisa logarítmica da próxima página e os heaps da seguinte. O trabalho desta página é mecânico e tem de ficar automático: percorrer qualquer árvore nas três ordens sem hesitar.

## Vocabulário

Uma **árvore binária** é vazia ou um **nó raiz** com uma subárvore esquerda e uma direita, ambas binárias. Quem tem filhos é **interno**; quem não tem é **folha**. A **altura** é o número de arestas do caminho mais longo da raiz a uma folha (uma árvore só com a raiz tem altura 0). Uma árvore **cheia** tem todos os níveis completos; uma **completa** tem todos os níveis completos exceto talvez o último, preenchido da esquerda para a direita. Uma árvore completa com $n$ nós tem altura $\lfloor \log_2 n \rfloor$: cada nível duplica a capacidade, por isso a altura cresce devagar.

A implementação é um nó com valor e dois apontadores, como nas listas mas a dobrar:

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

Os mesmos avisos das listas aplicam-se: cada `new` precisa do seu `delete`, e o destrutor percorre a árvore a libertar.

## As três travessias

Cada travessia visita todos os nós uma vez; diferem na posição da raiz entre as subárvores. Toma esta árvore de 7 nós: raiz 4, filho esquerdo 2 (filhos 1 e 3), filho direito 6 (filhos 5 e 7).

![Árvore binária de 7 nós: raiz 4, filho esquerdo 2 com filhos 1 e 3, filho direito 6 com filhos 5 e 7.](https://resumos.rgo.pt/cadeiras/aed/arvores-binarias/figura-1.svg)

![A mesma árvore com a ordem de visita da pré-ordem numerada por baixo de cada nó: 4 é o primeiro, 1 é o terceiro, 7 é o sétimo.](https://resumos.rgo.pt/cadeiras/aed/arvores-binarias/figura-2.svg)

*   **Pré-ordem** (raiz, esquerda, direita): 4, 2, 1, 3, 6, 5, 7. A raiz sai sempre primeiro: serve para copiar ou serializar a árvore, porque a reconstrução sabe onde começa cada subárvore. São os números por baixo dos nós no desenho.
*   **Em ordem** (esquerda, raiz, direita): 1, 2, 3, 4, 5, 6, 7. Numa árvore de pesquisa, sai ordenado: é a travessia que vais usar para listar.
*   **Pós-ordem** (esquerda, direita, raiz): 1, 3, 2, 5, 7, 6, 4. Os filhos saem antes do pai: serve para libertar memória (apagar o pai antes dos filhos perdia-lhes o endereço) e para avaliar expressões.

Todas custam $O(n)$ porque visitam cada nó uma vez, e usam $O(h)$ de pilha, sendo $h$ a altura. Numa árvore degenerada (uma lista disfarçada), $h = n$.

```cpp
#include <iostream>
using namespace std;
struct No { int v; No *e, *d; };
void pre(No* n) { if (!n) return; cout << n->v << " "; pre(n->e); pre(n->d); }
void em(No* n) { if (!n) return; em(n->e); cout << n->v << " "; em(n->d); }
void pos(No* n) { if (!n) return; pos(n->e); pos(n->d); cout << n->v << " "; }
int main() {
    No n1{1,0,0}, n3{3,0,0}, n5{5,0,0}, n7{7,0,0};
    No n2{2,&n1,&n3}, n6{6,&n5,&n7}, n4{4,&n2,&n6};
    pre(&n4); cout << "\n"; em(&n4); cout << "\n"; pos(&n4); cout << "\n";
}
```

O programa imprime as três linhas `4 2 1 3 6 5 7`, `1 2 3 4 5 6 7` e `1 3 2 5 7 6 4`: confere com as sequências que seguiste à mão e com os números do desenho para a pré-ordem.

Como não trocar as ordens

Lê o nome como a posição da raiz: **pré** é antes dos filhos, **pós** é depois, **em** é no meio. Fixa uma árvore pequena como a de cima e recita as três sequências até saírem sem pensar.

## Reconstruir a partir de duas travessias

Dadas a pré-ordem $[4, 2, 1, 3, 6, 5, 7]$ e a em ordem $[1, 2, 3, 4, 5, 6, 7]$, reconstrói: o primeiro da pré-ordem é a raiz, $4$. Na em ordem, tudo à esquerda do $4$ ($[1, 2, 3]$) é a subárvore esquerda e tudo à direita ($[5, 6, 7]$) é a direita. Na pré-ordem, a seguir ao $4$ vêm os nós da esquerda ($[2, 1, 3]$) e depois os da direita ($[6, 5, 7]$). Repete: raiz da esquerda é $2$, com $[1]$ à esquerda e $[3]$ à direita na em ordem; raiz da direita é $6$, com $[5]$ e $[7]$. A árvore está reconstruída.

Uma travessia sozinha não chega (várias árvores partilham a mesma em ordem), e pré mais pós também não bastam sem mais informação. Mas em ordem mais pré, ou em ordem mais pós, determinam a árvore: a em ordem separa esquerda de direita, a outra diz quem é a raiz de cada parte. Este é um exercício clássico de teste; resolve-o sempre por este algoritmo, nunca por tentativa.