Á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.