Arvore binaria

Árvore binária

Exemplo de árvore binária

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.

Definições para árvores binárias

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. [1]

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.

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 [pic]e [pic]e o seu pai terá índice piso((i - 1)/2). Caso a raiz esteja na posição um, os filhos terão índices [pic]e [pic]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