quarta-feira, 13 de outubro de 2010

Árvore Binária

Olá! Esta postagem é um pouco diferente das demais, pois é voltada principalmente ao pessoal que está estudando algoritmos e estruturas de dados, que a princípio não é muito complicado, pois é só usar a lógica. Porém, nem tudo é assim tão simples, principalmente quando trabalhamos com ponteiros de memória em estruturas de dados. A coisa fica um pouco mais difícil quando chegamos a parte de árvores binárias e grafos.
 
Quanto a definição de árvores de busca binária, para quem está vendo isso em estruturas de dados, deve ser tranquilo, e para quem nunca ouviu na vida algo relacionado a isso, há inúmeros textos na internet, então não vou entrar em detalhes nesse sentido e sim vou dar um exemplo de alguns procedimentos (em Pascal)  de um trabalho feito para a disciplina Estruturas de Dados II, onde deveríamos criar uma árvore binária onde pudéssemos inserir elementos, excluir elementos, contar os nós da árvore, dentre outras coisas, como mostra a figura a seguir, que é a tela principal do programa (não notem o visual da tela do programa, pois o objetivo era fazer um programa que funcionasse, e não fazer milagres com o Pascal e costruir "telinhas bonitinhas"... ). Aliás, não é a tela inteira do programa, pois com o ".exe" sendo executado, acabou-se perdendo parte da tela... mas enfim, o menu está na imagem.


Como podemos ver, esse programa deve ser capaz de fazer uma quantidade significativa de coisas na árvore que será criada, o que sem dúvidas fez com que o programa tivesse um número considerável de linhas, então para esta postagem não ficar muito grande, optei por não inserir as linhas correspondentes ao programa principal, mas sim, as variáveis e procedimentos utilizados para que o programa funcionasse.

Uma coisa que deve ser lembrado, é esta árvore trabalha com elementos  numéricos do tipo integer, mas tranquilamente poderíamos alterar alguns detalhes para que ela funcionasse com letras (char).

No site da UFSC, no endereço http://www.inf.ufsc.br/~ine5384-hp/Estruturas.ArvBusca.html, podemos ver um exemplo bem interessante que trata do assunto.


Bom, mas vamos ao código! Veja abaixo, analise e verá que não é assim coisa de outro mundo. É um pouco complicado mas se não fosse, não seria interssante, pois não haveria um desafio... hehe!!!
 

{NOVEMBRO DE 2006
 TRABALHO DE ESTRUTURAS DE DADOS II
 ARVORE BINARIA

 Autor: Paulo Luis Steinhauser
}
program arvore_binaria;
uses crt;

type inform = integer;

     ptnodo = ^elemento;
     elemento = record
        dado : inform;
        dir : ptnodo;
        esq : ptnodo;
     end;

     arvore = record
        raiz : ptnodo;
     end;

     vetor = array[1..50] of integer;

var opt, first,pos_x,pos_y,pos_x2,pos_y2: integer;
    dado: inform;
    arv, arv_aux: ptnodo;
    conta, compara, alta, max, father: integer;
    a: vetor;
    tipos: byte;

{++++++++++++++++++++++++++++++++++++++++++++++++++++++++++}

procedure cria_arvore(var raiz: ptnodo);

begin            {cria a arvore vazia}
  raiz:= nil;
end;

{****************************************************}


procedure incluir(var tree: ptnodo; item: inform);
var no: ptnodo;

begin
   if tree = nil then
   begin                 { se a arvore estiver vazia}
      new (no);          { a informaçao vai para a raiz}
      no^.esq:= nil;
      no^.dir:= nil;
      no^.dado:= item;
      tree:= no;
   end
   else
   if item = tree^.dado then   {verifica se elento ja existe}
   begin
      textcolor(red + blink);
      writeln('Elemento ja cadastrado');
      readkey;
   end
   else
   if item < tree^.dado then
   begin                               {se ainda nao existir o elemento}
      incluir(tree^.esq,item);  {verifica-se se vai ser incluido na}
   end                                 {esquerda ou na direita}
   else
      incluir(tree^.dir,item);
end;

{***********************************************************}

function vazia(tree: ptnodo): boolean;

begin
   vazia:= false;
   if tree = nil then   {verifica se a arvore esta vazia}
      vazia:= true      {procedimentos posteriores utilizam esta function}
   else
      vazia:= false;
end;


{************************************************************}

function achou(tree: ptnodo; item: inform): boolean;

begin
   achou:= false;
   if tree = nil then             {funcao que procura o elemnto}
   begin                            {na arvore para ver se ele existe}
     achou:= false;             {ou nao, retornando um valor...}
   end
   else
   if item = tree^.dado then
   begin
      achou:= true;
   end
   else
   if item < tree^.dado then
      begin
      achou:= achou(tree^.esq,item);
   end
   else
   begin
      achou:= achou(tree^.dir,item);
   end;
end;

{*********************************************************}

procedure deleta (aux:ptnodo; var tree:ptnodo);
begin
   if tree^.dir <> nil
   then
   begin
      deleta(aux,tree^.dir);
   end
   else
   begin
      aux^.dado:= tree^.dado;
      aux:= tree;
      tree:= tree^.esq;
      dispose(aux);
   end;
end;

{********************************************************}

procedure excluir (var tree: ptnodo; item: inform);
var aux : ptnodo;

begin
  if (item < tree^.dado) then
  begin
     excluir(tree^.esq,item); {verifica a sub da esquerda}
  end
  else
  if (item > tree^.dado) then
  begin
     excluir(tree^.dir,item); {verifica a sub da direira}
  end
  else
  if tree^.dir = nil then
  begin
     aux := tree;
     tree := tree^.esq;
     dispose(aux);
  end
  else
  if tree^.esq = nil then
  begin
     aux := tree;
     tree := tree^.dir;
     dispose(aux);
  end
  else
  begin
     deleta(tree, tree^.esq);
  end;
end;

{*********************************************************}

procedure caminha_pre(tree: ptnodo);

begin
   if tree <> nil then           {procedimento para camhinhar prefixado}
   begin
      write(tree^.dado,' ');
      caminha_pre(tree^.esq);
      caminha_pre(tree^.dir);
   end;
end;

{**********************************************************}

procedure caminha_in(tree: ptnodo);
{procedimento para camhinhar infixado}
begin
   if tree <> nil then           
   begin
      caminha_in(tree^.esq);
      write(tree^.dado,' ');
      caminha_in(tree^.dir);
   end;
end;

{***********************************************************}

procedure caminha_pos(tree: ptnodo);
{procedimento para camhinhar posfixado}
begin
   if tree <> nil then         
   begin
      caminha_pos(tree^.esq);
      caminha_pos(tree^.dir);
      write(tree^.dado,' ');
   end;
end;

{***********************************************************}

procedure mostra_folha(tree: ptnodo; var cont: integer);
{procedimento que verifica se folha, mostra as mesmas e caminha na arvore}
begin
   if (tree^.esq = nil) and (tree^.dir = nil) then
   begin
      write(tree^.dado,' ');
      cont:= cont + 1;
   end                
   else              
   if tree^.esq <> nil then    
   begin
      mostra_folha(tree^.esq,cont);
   end;

   if tree^.dir <> nil then
   begin
      mostra_folha(tree^.dir,cont);
   end;
end;

{***********************************************************}

function conta_nos(tree: ptnodo; var cont: integer):integer;

begin
   if tree <> nil then
   begin
      cont:= cont + 1;
      conta_nos:=conta_nos(tree^.esq,cont);
      conta_nos:=conta_nos(tree^.dir,cont);
      conta_nos:= cont;
   end;
end;

{************************************************************}

procedure altura(tree: ptnodo;var alt: integer; aux: integer);

begin
   if (tree^.esq = nil) and (tree^.dir = nil) then
   begin
      if aux > alt then
      begin
         alt := aux;
      end;
      aux:= 0;
   end
   else
   begin
      aux:= aux + 1;
      if tree^.esq <> nil then
      begin
         altura(tree^.esq,alt,aux);
      end;

      if tree^.dir <> nil then
      begin
         altura(tree^.dir,alt,aux);
      end;
   end;
end;

{************************************************************}

procedure nivel_elemento(tree: ptnodo; item: inform; var nivel: integer);

begin
   if item = tree^.dado then
   begin
      textcolor(yellow);
      writeln;
      writeln;
      writeln('*   O elemento ',dado,' esta no nivel ',nivel);
   end
   else
   begin
      nivel:= nivel + 1;
      if item < tree^.dado then
      begin
         nivel_elemento(tree^.esq,item,nivel);
      end
      else
      begin
         nivel_elemento(tree^.dir,item,nivel);
      end;
   end;
end;

{************************************************************}

procedure completa(tree: ptnodo; qtd: integer; alt: integer);
var expo: real;
    x: real;

begin
   alta:= 0;
   compara:= 0;
   expo:= 0;

   altura(arv,alta,compara);  
   alt:= alta;
   qtd:= conta_nos(arv, conta);

   expo:= Round(Exp((alt+1) * Ln(2)) - 1);             


   if  (expo = qtd) then
   begin
      textcolor(green);
      writeln('Arvore Completa !!!');
   end
   else
   begin
      textcolor(red);
      writeln('Arvore Incompleta!!!');
   end;
end;

{************************************************************}

procedure tipo_elem(inf:inform;var vet: vetor; var i:integer;tipo: integer; var pai: integer);
{procedimento que inclui elementos no vetorna respectiva posiçao que ‚ indicada pelo parâmetro tipo}
begin
   if tipo = 0 then      
      vet[1]:= inf;                                
   if tipo = 1 then
   begin
      vet[2*i]:= inf;
      pai:= 2*i;
   end;

   if tipo = 2 then
   begin
      vet[2*i+1]:= inf;
      pai:= 2*i+1;
   end;
end;

{*************************************************************}

procedure tree_vetor(tree:ptnodo;i: integer; var vet: vetor; tipo: integer;  pai: integer; var maior: integer);

begin
   if tree <> nil then
   begin
      tipo_elem(tree^.dado,vet,i,tipo,pai);
      i:= pai;
      tree_vetor(tree^.esq,i,vet,1,pai,maior);
      if i > pai then
         maior:= i;
      tree_vetor(tree^.dir,i,vet,2,pai,maior);
   end;
end;

{**************************************************************}

procedure cria_vetor(var vet: vetor; var tam: integer);
{procedimento que cria o vetor e insere um valor default nos seus elementos}
var alta, compara, alt, i: integer;

begin
   alta:= 0;                             
   compara:= 0;                 
   altura(arv,alta,compara);
   alt:= alta;

   tam:= Round(Exp((alt+1) * Ln(2)) - 1);

   for i:= 1 to tam do
   begin
      vet[i]:= 1000;
   end;
end;

{**************************************************************}

procedure escreve_vetor(vet: vetor; tam: integer);
var i: integer;

begin
   for i:= 1 to tam do                  
   begin                                     
      if vet[i] <> 1000 then   
      begin
         write(vet[i],' ');
      end
      else
      begin
         write('_');
      end;
   end;
end;

{*************************************************************}

procedure desenha(tree:ptnodo; x, y, primeiro:integer);

begin
  if tree^.dado > primeiro then
  begin
     textcolor(6);
  end
  else
  begin
     textcolor(10);
  end;

  if (tree^.esq = nil) and (tree^.dir = nil) then
  begin
     if tree^.dado > primeiro then
     begin
        textcolor(12);
     end
     else
     begin
        textcolor(2);
     end;
  end;
  gotoxy(x,y);
  write(tree^.dado);
end;

{************************************************************}

procedure grafica(tree, aux:ptnodo; alt, primeiro, x, y, x2, y2: integer);

begin
   if tree <> nil then
   begin
      if tree^.esq <> nil then
      begin
         aux:= tree^.esq;
         x:= x - (4 * alt-1);
         y:= y + 2;
         desenha(aux,x,y,first);
      end;
      if tree^.dir <> nil then
      begin
         aux:= tree^.dir;
         x2:= x2 + (4 * alt-1);
         y2:= y2 + 2;
         desenha(aux,x2,y2,first);
      end;
      alt:= alt - 1;
      grafica(tree^.esq,aux,alt,primeiro,x,y,x,y);
      grafica(tree^.dir,aux,alt,primeiro,x2,y2,x2,y2);
   end;
end;


{*****************************************************************}

procedure le_item(var inf: inform);

begin
   textcolor(green);
   gotoxy(5,20);
   write('Informe o n£mero ==>');
   gotoxy(27,20);
   read(inf);
end;

{***********************************************************}

begin

AQUI VAI O PROGRAMA PRINCIPAL!!! 

end.

2 comentários:

Anônimo disse...

Sorry for my bad english. Thank you so much for your good post. Your post helped me in my college assignment, If you can provide me more details please email me.

Paulo Luis Steinhauser disse...

Thanks for the comment! Any questions please contact ...