Árvores binárias e percursos

Vocabulário mínimo

Uma árvore binária está vazia ou tem uma raiz com subárvore esquerda e direita. A posição de cada nó importa; a ordem dos valores não faz parte da definição.

• A profundidade conta as arestas desde a raiz. A altura conta o maior caminho até uma folha: a árvore vazia tem altura -1 e uma folha tem altura 0.
• Uma árvore completa tem todos os níveis cheios exceto possivelmente o último, que fica preenchido da esquerda para a direita. Uma árvore perfeita tem todos os níveis cheios. Uma árvore estrita dá zero ou dois filhos a cada nó.
• Com n nós, a altura fica entre $\lceil\log_2(n+1)\rceil-1$ e $n-1$.

Percursos que interessam

Para um nó com alturas h_e e h_d e tamanhos t_e e t_d nas subárvores esquerda e direita:

$$\operatorname{altura}=1+\max(h_e,h_d),\qquad \operatorname{tamanho}=1+t_e+t_d.$$

A árvore vazia tem tamanho 0. Cada percurso visita cada nó uma vez, logo custa $\Theta(n)$, com pilha $O(h+1)$.

Ordem	Regra	Sequência na figura
Pré	Raiz, esquerda, direita	8 4 2 6 10 9
Em	Esquerda, raiz, direita	2 4 6 8 9 10
Pós	Esquerda, direita, raiz	2 6 4 9 10 8
Níveis	Por níveis, da esquerda à direita	8 4 10 2 6 9

Pós-ordem calcula nos filhos antes do pai. Em-ordem só ordena numa BST.

Propriedades e reconstrução

• Dois filhos: soma recursiva mais um quando ambas as ligações existem.
• Perfeita pede subárvores perfeitas de igual altura. Verifica altura e forma juntas para ficar linear.
• Pré mais em com valores distintos dá a árvore: raiz é o primeiro da pré; a sua posição na em separa lados. Pré sozinha é ambígua.

Detalhes e programas.