Aula 06 – 05/04
Árvores binárias
• É um tipo de árvore especial onde cada nó pode ter de 0 a 2 nós
descendentes.
• Por convenção os nós são chamados de nó da esquerda e nó da
direita
• Dessa forma a árvore binária tem no máximo grau 2.
• Exemplo de uma árvores binária
• No raiz é 8
• Subarvore esquerda iniciando nó 3 e a subarvore direta iniciando no
nó 10.
• Nós folha 1, 4, 7 e 13
Prática - Declarando uma árvores binária
PApontador = ^TItem;
TItem = record
Valor: TEstado;
NoEsquerda: PApontador;
NoDireta: PApontador;
end;
Prática – Inserindo um elemento na árvore
• Vamos inserir os itens seguindo uma ordem.
• Se a árvore estiver vazia insere o novo elemento no raiz.
• Se o item que estiver sendo inserido é menor que a raiz inserimos o
item na esquerda.
• Se o item que estiver sendo inserido é maior que a raiz inserimos o
item na direita.
Exemplo de inserção
Algoritmo
procedure TForm2.Inserir( AEstado: TEstado; var AItem: PApontador );
begin
if ( AItem = nil ) then
begin
// Aloca um novo item na memória
New( AItem );
AItem.Valor:= AEstado;
AItem.NoEsquerda:= nil;
AItem.NoDireta:= nil;
end else
begin
// A o campo para ordenação é o nome
if ( AEstado.Codigo < AItem.Valor.Codigo ) then
Inserir(AEstado, AItem.NoEsquerda)
else if ( AEstado.Codigo > AItem.Valor.Codigo ) then
Inserir(AEstado, AItem.NoDireta)
else
raise Exception.Create('Não é permitido item duplicado');
end;
end;
Prática – Pesquisando um item na arvore
• Percorre a árvore de forma ordenada.
• Processo eficiente pois temos uma direção a ser percorrida.
• Verifica se a raiz é igual ao item a ser pesquisado.
• Se o nó raiz é menor, continua a busca pela esquerda.
• Se o nó raiz é menor, continua a busca pela direita.
Exemplo de pesquisa
Algoritmo
procedure TForm2.Buscar(AItem: PApontador);
begin
// Verifica se a lista esta vazia
if ( AItem <> nil ) then
begin
// Encontrou o registro
if ( AItem.Valor.Codigo = StrToInt ( EdtCodigo.Text )) then
begin
EdtSiglaEstado.Text:= AItem.Valor.Sigla;
EdtNomeEstado.Text:= AItem.Valor.Nome;
end else
begin
if ( (StrToInt ( EdtCodigo.Text )) < AItem.Valor.Codigo ) then
Buscar( AItem.NoEsquerda )
else if ((StrToInt ( EdtCodigo.Text )) > AItem.Valor.Codigo ) then
Buscar( AItem.NoDireta )
end;
end;
end;
Percorrendo árvores binarias
• Necessidade de percorrer a arvores de forma sistêmica percorrendo
todos os nós da arvore.
• No caso de uma estrutura de arvores possuir os dados de um
produto, teríamos que percorrer todas a arvores para emitir um
relatórios dos produtos.
Tipos de percurso – Pré ordem
• Visita a raiz (executa uma certa operação).
• Percorre a sub arvore da esquerda.
• Percorre a sub arvore da direita.
Tipos de percurso – Em ordem
• Percorre a sub arvore da esquerda.
• Visita a raiz (executa uma certa operação).
• Percorre a sub arvore da direita.
Tipos de percurso – Pós ordem
• Percorre a sub arvore da esquerda.
• Percorre a sub arvore da direita.
• Visita a raiz (executa uma certa operação).
Prática – Pré ordem
procedure TForm2.PreOrdem(AItem: PApontador);
begin
if ( AItem <> nil ) then
begin
// Esse nó é o raiz da subarvore
ShowMessage( Aitem.Valor.Nome )
PreOrdem( AItem.NoEsquerda );
PreOrdem( AItem.NoDireta );
end;
end;
Exercícios
aula 06 – Exercícios.docx