Arvores Binarias

ÍNDICE

1. ÁRVORE BINÁRIA

1.1. Definição

Uma árvore binária é uma estrutura de dados caracterizada por:
Ou não tem elemento algum (árvore vazia).
Ou tem um elemento distinto, denominado raiz, com dois ponteiros para duas estruturas diferentes, denominadas sub-árvore esquerda e sub-árvore direita.

Perceba que a definição é recursiva e, devido a isso, muitas operações sobre árvores binárias utilizam recursão. É o tipo de árvore mais utilizado na computação. A principal utilização de árvores binárias são as árvores de busca binária.

Os nós de uma árvore binária possuem graus zero, um ou dois. Um nó de grau zero é denominado folha.

Em uma árvore binária, por definição, cada nó poderá ter até duas folhas, sendo que ela se compara com a abb (árvore binária de busca), apesar de não ter a propriedade da mesma ("na abb, existe uma regra na inserção").

A profundidade de um nó é a distância deste nó até a raiz. Um conjunto de nós com a mesma profundidade é denominado nível da árvore. A maior profundidade de um nó, é a altura da árvore.

Uma árvore "estritamente binária" é uma árvore na qual todo nó tem zero ou duas folhas.

Existem autores, porém, que adotam essa definição para o termo quase completa, e utilizam o termo completa apenas para árvores em que todos os níveis têm o máximo número de elementos.

1.2. Funcionamento

EXEMPLO

Nós - são todos os itens guardados na árvore;
Raiz - é o nó do topo da árvore (no caso da figura acima, a raiz é o nó 8);
Filhos - são os nós que vem depois dos outros nós (no caso da figura acima, o nó 6 é filho do 3);
Pais - são os nós que vem antes dos outros nós (no caso da figura acima, o nó 10 é pai do 14);
Folhas - são os nós que não têm filhos; são os últimos nós da árvore (no caso da figura acima, as folhas são 1, 4, 7 e 13).

1.3. Código

Struct typedef struct No{ int numero; struct No *pEsquerda; struct No *pDireita;
}No;