Arvores binárias

1. Introdução 2. Definições Básicas 3. Àrvores Binárias 4. Armazenamento de Árvores Binárias 5. Uma Aplicação de Árvores Binárias 6. Percorrendo Árvores Binárias 7. O Algoritmo de Huffman 8. Removendo Nós de Árvores Binárias 9. Árvores Binárias Balanceadas 10. Exercícios

Introdução

Definições Básicas

Árvores são estruturas de dados extremamente úteis em muitas aplicações. Uma árvore é formada por um conjunto finito T de elementos denominados vértices ou nós de tal modo que se T = 0 a árvore é vazia, caso contrário temos um nó especial chamado raiz da árvore (r), e cujos elementos restantes são particionados em m>=1 conjuntos distintos não vazios, as subárvores de r, sendo cada um destes conjuntos por sua vez uma árvore.
A forma convencional de representar uma árvore está indicado na figura aini abaixo. Esta árvore tem nove nós sendo A o nó raiz.

Figura (aini): Uma árvore

Os conjuntos das subárvores tem de ser disjuntos tem de ser disjuntos portanto a estrutura indicada na Figura arvn não é uma árvore.

Figura arvn: Estrutura que não representa uma árvore

Se n é um nó da árvore T então Tn indica uma subárvore de T com raiz no nó n. Os nós n1, n2, ..., nk das subárvores de Tn são chamados de filhos de n e n é o pai destes nós, que são nós irmãos. Os nós B e C são filhos de A e nós irmãos. Nós sem filhos como os nós D, H, I, F e G são chamados de folhas. A subárvore da esquerda do nó A tem raiz em B e a subárvore da direita tem raiz em C, isto está indicado pelos dois ramos saindo de A. A ausência de um ramo na árvore indica uma subárvore vazia, como a subárvore da direita do nó B. O número de de filhos de um nó é chamado de grau de saída deste nó. Por exemplo, o nó C tem grau de saída 3 e o nó E grau 2. Se o nó n é a raiz de uma subárvore Tn e n1 pertence a Tn então n1 é descendente de n e n ancestral de n1. Portanto nós sem descendentes próprios é uma folha. Por exemplo, o nó H é