Arvores binarias

Árvores binárias

(Veja o verbete Binary tree na Wikipedia.)

Uma árvore binária é uma estrutura de dados mais geral que uma lista encadeada. Este capítulo introduz as operações mais simples sobre árvores binárias. O capítulo seguinte trata de uma aplicação básica.
Nós e filhos

Uma árvore binária (= binary tree) é um conjunto de registros que satisfaz certas condições. (As condições não serão dadas explicitamente, mas elas ficarão implicitamente claras no contexto.) Os registros serão chamados nós (poderiam também ser chamados células). Cada nó tem um endereço. Suporemos por enquanto que cada nó tem três campos: um número inteiro e dois ponteiros para nós. Os nós podem, então, ser definidos assim:

struct cel { int conteudo; /* conteúdo */ struct cel *esq; struct cel *dir;
};
typedef struct cel no; /* nó */

conteudo
999

esq dir

O campo conteudo é a "carga útil" do nó; os outros dois campos servem apenas para dar estrutura à árvore. O campo esq de todo nó contém o endereço de outro nó ou NULL. A mesma hipótese vale para o campo dir. Se o campo esq de um nó X é o endereço de um nó Y, diremos que Y é o filho esquerdo de X. Analogamente, se X.dir é igual a &Y então Y é o filho direito de X.

Se um nó Y é filho (esquerdo ou direito) de X, diremos que X é o pai de Y. Uma folha (= leaf) é um nó que não tem filho algum.

É muito conveniente confundir cada nó com seu endereço. Assim, se x é um ponteiro para um nó (ou seja, se x é do tipo *no), dizemos simplesmente "considere o nó x" em lugar de "considere o nó cujo endereço é x".