Árvore binária
Origem: Wikipédia, a enciclopédia livre.
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.
Índice |
[editar] 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.
Uma árvore binária é considerada estritamente binária se cada nó da árvore possui grau zero ou dois.
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 é dita completa se todo nível i, com exceção do último, tem o número máximo de elementos. Numa árvore binária, o numero máximo de elementos em um nivel é 2i. 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.
[editar] Definições em teoria dos grafos
Em teoria dos grafos, uma árvore binária é definida como um grafo acíclico, conexo, dirigido e que cada nó não tem grau maior que 2. Assim sendo, só existe um caminho entre dois nós distintos.
E cada ramo da árvore é um vértice dirigido, sem peso, que parte do pai e vai o filho.
[editar] Percursos em árvore
Existem três tipos de percursos: Percurso em em-ordem, pré-ordem e pós-ordem.
[editar] Em-Ordem
O algoritmo recursivo desse percurso é:
emOrdem(Struct No *n)
{
if(n != null)
{
emOrdem(n->esq);
visita(n);
emOrdem(n->dir);
}
}
Para a árvore acima, o percurso seria: 2, 7, 5, 6, 11, 2, 5, 4 e 9. Veja a linha de execução:
- emOrdem(2->esq)
- emOrdem(7->esq)
- emOrdem(2->esq)
- visita(2)
- emOrdem(2->dir)
- visita(7)
- emOrdem(7->dir)
- emOrdem(6->esq)
- emOrdem(5->esq)
- visita(5)
- emOrdem(5->dir)
- visita(6)
- emOrdem(6->dir)
- emOrdem(11->esq)
- visita(11)
- emOrdem(11->dir)
- emOrdem(6->esq)
- emOrdem(7->esq)
- visita(2)
- emOrdem(2->dir)
- emOrdem(5->esq)
- visita(5)
- emOrdem(5->dir)
- emOrdem(9->esq)
- emOrdem(4->esq)
- visita(4)
- emOrdem(4->dir)
- visita(9)
- emOrdem(9->dir)
- emOrdem(9->esq)
[editar] Pré-Ordem
O algoritmo recursivo desse percurso é:
preOrdem(Struct No *n){
if(n!=null){
visita(n);
preOrdem(n->esq);
preOrdem(n->dir);
}
}
Para a árvore acima, o percurso seria: 2, 7, 2, 6, 5, 11, 5, 9 e 4. Veja a linha de execução:
- visita(2)
- preOrdem(2->esq)
- visita(7)
- preOrdem(7->esq)
- visita(2)
- preOrdem(2->esq)
- preOrdem(2->dir)
- preOrdem(7->dir)
- visita(6)
- preOrdem(6->esq)
- visita(5)
- preOrdem(5->esq)
- preOrdem(5->dir)
- preOrdem(6->dir)
- visita(11)
- preOrdem(11->esq)
- preOrdem(11->dir)
- preOrdem(2->dir)
- visita(5)
- preOrdem(5->esq)
- preOrdem(5->dir)
- visita(9)
- preOrdem(9->esq)
- visita(4)
- preOrdem(4->esq)
- preOrdem(4->dir)
- preOrdem(9->dir)
[editar] Pós-Ordem
O algoritmo recursivo desse percurso é:
posOrdem(Struct No *n){
if(n!=null){
posOrdem(n->esq);
posOrdem(n->dir);
visita(n);
}
}
Para a árvore acima, o percurso seria: 2, 5, 11, 6, 7, 4, 9, 5 e 2. Veja a linha de execução:
- posOrdem(2->esq)
- posOrdem(7->esq)
- posOrdem(2->esq)
- posOrdem(2->dir)
- visita(2)
- posOrdem(7->dir)
- posOrdem(6->esq)
- posOrdem(5->esq)
- posOrdem(5->dir)
- visita(5)
- posOrdem(6->dir)
- posOrdem(11->esq)
- posOrdem(11->dir)
- visita(11)
- visita(6)
- posOrdem(6->esq)
- visita(7)
- posOrdem(7->esq)
- posOrdem(2->dir)
- posOrdem(5->esq)
- posOrdem(5->dir)
- posOrdem(9->esq)
- posOrdem(4->esq)
- posOrdem(4->dir)
- visita(4)
- posOrdem(9->dir)
- visita(9)
- posOrdem(9->esq)
- visita(5)
- visita(2)
[editar] Transformação de uma árvore n-ária
Uma árvore n-ária qualquer (árvore cujos nós possuem graus menores ou iguais a n) podem ser representados por uma árvore binária. Um exemplo dessa transformação pode ser vista em [1]
[editar] 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.
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).
![[1]](http://en.wikipedia.org/wiki/Image:Nary_to_binary_tree_conversion.png){kind=link}