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.
