Métodos para representar árvores binárias

Métodos para representação de árvores binárias

Uma das maneiras mais simples de representar árvores binárias em linguagens de programação é por meio de arranjos unidimensionais (vetores). Caso a raiz esteja na posição zero, dado um nó de índice i qualquer, os seus filhos terão índices 2i+1 e 2i + 2 e o seu pai terá índice piso((i - 1)/2). Caso a raiz esteja na posição um, os filhos terão índices 2i e 2i+1 e o pai terá índice piso(i/2). Essa implementação é utilizada para representar árvores completas ou quase completas. Heaps, que são árvores binárias quase completas são implementadas na forma de um vetor de uma maneira bastante eficiente.

Apesar da simplicidade, essa representação requer uma grande quantidade de memória contígua para o armazenamento de árvores grandes, o crescimento desta é díficil de implementar e manter e pode haver grande quantidade de desperdício de memória.

Uma pequena árvore binária com raiz na posição 0, representada como um vetor.

Em uma linguagem que possua suporte a estruturas e referências (por exemplo pascal e C), as árvores podem ser implementadas a partir de nós, com um, ou mais, campos para a(s) informação(ões) principal(is) e dois campos apontadores especiais, denominados esquerda e direita, que fazem referência às sub-árvores esquerda e direita, respectivamente. Algumas vezes, há um apontador para o pai. Em um nó do tipo folha, os campos apontadores possuem valores especiais (nil em Pascal e "NULL" em C).