Árvores Binárias

Árvores Binárias

Definição: São estruturas do tipo árvore com as seguintes características:

A árvore tem grau 2.
Cada subárvore é identificada como subárvores esquerda e direita.
Pode haver uma ordenação entre as subárvores.

Exemplo:

Implementação Seqüencial

A implementação seqüencial de árvore binária tem as seguintes características:

Usa uma estrutura estática tipo array.
Os nós de cada nível são armazenados de forma contígua, ordenados da esquerda para a direita.
Um nó inexistente é deixado "em branco", mas ocupa espaço no array, gerando desperdício de memória.

Graficamente, teríamos:

Implementação Encadeada

A implementação encadeada de árvore binária tem as seguintes características:

Usa um estrutura dinâmica com apontadores.
Cada nó contém os dados e os apontadores para as subárvores esquerda e direita.

Graficamente, teríamos:

A implementação encadeada de árvore binária é mais usada do que a estática porque e mais eficiente em termos de espaço em memória.

Definição de uma árvore binária em pascal

type
   ArvoreBinaria = ^No;
   No = record
           Dado: tipo_do_dado;
           Esquerdo,
           Direito,
           Pai : ArvoreBinaria;
        end;

Para ver uma implementação de uma árvore binária encadeada, abra a unit ArvBin e para um programa que demonstra como usá-la, veja PArvBin.

O procedimento CriarNo recebe um apontador ArvoreBinaria e o dado que será colocado no nó. Além de alocar uma variável dinâmica para o nó, copia o dado para esta variável e faz com que os apontadores para o pai, para o nó esquerdo e para o nó direito sejam inicializados através do procedimento Inicializar.

A função ExisteNo retorna true se existe um nó na árvore binária passada seguindo pela direção especificada.

O procedimento Deslocar move o apontador do tipo ArvoreBinaria na direção especificada. Se a direção for nó raiz, Deslocar só encerra quando ArvoreBinaria não tiver mais um nó pai.

O procedimento ObterDado coloca em Dado (parâmetro), o valor contido no nó passado.

O procedimento AlterarDado modifica o valor do dado contido no nó passado para o valor passado como parâmetro.

O procedimento AdicionarFilho coloca um novo nó na direção especificada (nó esquerdo ou nó direito) e copia o dado passado para ele.

Algoritmos Especiais

O procedimento DisposeArvore libera a árvore passada da memória.

Dada a árvore abaixo:

Teríamos a seguinte execução do procedimento recursivo DisposeArvore:

O procedimento Deltree elimina uma subárvore de uma árvore. Além de desalocar da memória, faz com que o nó que apontava para a raiz da subárvore aponte para nil.

a) Removendo uma subárvore (o apontador passado para Deltree não é a raiz)

b) Removendo uma árvore completamente, quando o apontador passado para Deltree é o nó raiz.

Caminhamento

Definição: Caminhamento é o ato de percorrer todos os nós da árvore de uma forma sistemática sendo cada nó "visitado" visitado uma única vez.

Um caminhamento completo sobre uma árvore produz uma seqüência linear dos nós, de modo que cada nó da árvore passa a ter um nó seguinte ou um nó anterior, ou ambos, para uma dada forma de caminhamento.

No caso de árvores binárias existem 3 tipos de caminhamento mais freqüentemente utilizados. São eles:

Caminhamento LRN (pós-ordem)
Caminhamento NLR (pré-ordem)
Caminhamento LNR (in-ordem ou central)

onde: L = Left, R = Rigth e N = Node

Caminhamento Pós-Ordem (LRN)

Nesse caminhamento, partindo da raiz, visitamos todos os nós da subárvore esquerda, depois os subnós da subárvore direita e, por último, o nó na raiz.

Esse algoritmo é repetido para cada nó.

Seja uma árvore que representa uma expressão matemática A * (B + C) - (D + E):

Percorrendo a árvore usando o Pós-Ordem, teríamos a expressão na notação Pós-Fixada:

A B C + * D E + -

Para avaliar a expressão acima, usamos o seguinte algoritmo:

Se for operando empilha.
Senão se for operador desempilha dois operandos da pilha, efetua a operação indicada pelo operador e empilha o resultado.
Ao terminar, o resultado estará na pilha.

1) Lê A, B, C e Empilha	2) Lê + e desempilha dois operandos	3) Coloca o resultadona pilha	4) Lê * e desempilha 2 operandos
5) Coloca o resultado na pilha	6) Lê D e E e empilha	7) Lê + e desempilha 2 operandos	8) Coloca o resultado na pilha
9) Lê - e desempilha 2 operandos		10) Coloca o resultado na pilha

procedure PosOrdem(Arvore : ArvoreBinaria);
begin
   if Arvore <> nil then
      begin
         PosOrdem(Arvore^.Links[NoEsquerdo]);
         PosOrdem(Arvore^.Links[NoDireito]);
         Visite(Arvore);
      end;
end;

Caminhamento Pré-Ordem (NLR)

Nesse caminhamento, partindo da raiz, visitamos o nó raiz, em seguida todos os nós da subárvore esquerda e finalmente os nós da subárvore direita.

Percorrendo a árvore exemplo, teríamos a expressão na notação prefixada:

- * A + B C + D E

procedure PreOrdem(Arvore : ArvoreBinaria);
begin
   if Arvore <> nil then
      begin
         Visite(Arvore);
         PreOrdem(Arvore^.Links[NoEsquerdo]);
         PreOrdem(Arvore^.Links[NoDireito]);
      end;
end;

Caminhamento In-Ordem ou Central (LNR)

Nesse caminhamento, partindo da raiz, visitamos todos os nós da subárvore esquerda, depois o nó raiz e finalmente os nós da subárvore direita.

Percorrendo a árvore exemplo, teríamos a expressão na notação infixa:

-A * (B + C) - (D + E)

procedure InOrdem(Arvore : ArvoreBinaria);
begin
   if Arvore <> nil then
      begin
         InOrdem(Arvore^.Links[NoEsquerdo]);
         Visite(Arvore);
         InOrdem(Arvore^.Links[NoDireito]);
      end;
end;

Exemplo: Determinar as características de uma árvore.

Número de nós;
Altura da árvore (maior nível);
Comprimento médio dos caminhos (soma dos comprimentos dos caminhos / número de nós).

Número de nós = 7

Altura = 3

Comprimento médio = (0 + 1 + 1 + 2 + 2 + 2 + 3) / 7 = 11/7 = 1,57

procedure Caracteristicas(Arvore : ArvoreBinaria; var NumNos, Altura : integer; var CompMedio : real);
var
   Soma : integer;

procedure InOrd(Arvore : ArvoreBinaria; Nivel : integer);
begin { InOrd }
   if not Vazia(Arvore) then
      begin
         InOrd(Arvore^.Links[NoEsquerdo], Nivel + 1);
         inc(NumNos);
         Soma := Soma + Nivel;
         if Nivel > Altura then
            Altura := Nivel;
         InOrd(Arvore^.Links[NoDireito], Nivel + 1);
      end;
end; { InOrd }

begin { Caracteristicas }
   NumNos := 0;
   Altura := 0;
   Soma := 0;
   InOrd(Arvore, 0);
   CompMedio := Soma / NumNos;
end; { Caracteristicas }

Tipo Procedural

Cada vez que é necessário percorrer uma árvore e executar uma operação (visitar) sobre cada nó, é necessário reescrever o algoritmo de caminhamento e dentro dele chamar um procedimento diferente.

Para solucionar esse problema, podemos usar um parâmetro do tipo procedural no procedimento de caminhamento, isto é, passar uma espécie de endereço, que nada mais é do que um apontador para o procedimento que será chamado de dentro do procedimento de caminhamento, utilizando o nome do parâmetro.

Definindo um tipo procedural:

type ParamVisite = procedure (Arvore : ArvoreBinaria);

De forma genérica:

type
<identificador> = procedure (<lista_de_parâmetros>);
<identificador> = function (<lista_de_parâmetros>) : <tipo_de_retorno>;

Exemplo: Redefinindo PosOrdem para receber um parâmetro do tipo procedural ParamVisite.

procedure PosOrdem(Arvore : ArvoreBinaria; Visite : ParamVisite);
begin
   if not Vazia(Arvore) then
      begin
         PosOrdem(Arvore^.Links[NoEsquerdo], Visite);
         PosOrdem(Arvore^.Links[NoDireito], Visite);
         Visite(Arvore);
      end;
end;

Criando um procedimento do tipo procedural ParamVisite:

procedure ImprimirDadoDoNo(Arvore : ArvoreBinaria); far;
var Dado: tipo_do_dado;
begin
ObterDado(Arvore, Dado);
writeln(Dado);
end;

O procedimento criado deve ter os tipos dos parâmetros iguais. Se for uma função, o tipo de retorno também deve coincidir.

A diretiva far é usada para forçar o uso de endereços absolutos (incluem o segmento e o deslocamento dentro do segmento) ao chamar a função ou procedimento. Normalmente só é necessário o deslocamento (endereço relativo).