Arvore binaria

Disponível somente no TrabalhosFeitos
  • Páginas : 2 (474 palavras )
  • Download(s) : 0
  • Publicado : 2 de setembro de 2012
Ler documento completo
Amostra do texto
Á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 árvoresbiná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 queela 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. Umconjunto 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 ouduas 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 deelementos.




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 filhosterã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...
tracking img