Arvores Binárias
Estudo através de diagramas
Aluno: Jocimar B. A. Huss
Turma: 2º Ano de Ciência da Computação
1
Árvores Binarias
Nessa parte do estudo estaremos observando através de um diagrama como um
algorítimo utiliza recursão para mostrar uma arvore binária na tela do computador
de forma organizada.
Estudaremos como funciona o seguinte algoritmo:
procedure mostra (T: arvore; lin, col, colanterior: integer);
begin
if T <> nil then
begin
mostra (T^.esq, lin+1, col-abs(colanterior-col) div 2, col);
gotoxy(col, lin); write (T^.elem.ch);
mostra (T^.dir, lin+1, col+abs(colanterior-col) div 2, col);
end;
end;
O código acima foi escrito na linguagem Pascal por ser uma linguagem didática.
2
No algorítimo anterior vimos que a rotina recebe parâmetro T
do tipo arvore
O tipo de dado arvore é um ponteiro para uma estrutura de
dados. Represento esse esquema no quadro abaixo:
type
Arvore =^elemento;
elemento = record
dir :Arvore;
ch :Integer;
esq :Arvore;
end;
Na representação ao lado é criado
um tipo de dado chamado de
arvore como um ponteiro para o
tipo de dado elemento.
Então qualquer variável declarada
como tipo arvore, irá armazenar
um endereço (ponteiro) para uma
estrutura de dados do tipo
elemento.
3
Árvores Binarias
Usaremos a arvore abaixo em nosso exemplo:
No Slide a seguir você poderá
conferir o diagrama mostrando
como o algoritmo mostrará a
arvore ao lado no tela.
5
3
2
7
4
6
4
T = 5, L = 3, C = 40, CA = 80
If T<> nil then
m(P1)
gotoxy(C,L)
write(t^.el.ch)
m(P2)
T = 3, L = 4, C = 20, CA = 40
If T<> nil then
m(P1)
gotoxy(C,L)
write(t^.el.ch)
m(P2)
T = 2, L = 5, C = 10, CA = 20
If T<> nil then
m(P1)
gotoxy(C,L)
write(t^.el.ch)
m(P2)
T = nil,
If T<> nil then
m(P1)
gotoxy(C,L)
write(t^.el.ch)
m(P2)
5
T = nil
T = 7, L = 4, C = 40, CA = 20
If T<> nil then
m(P1)
gotoxy(C,L)
write(t^.el.ch)
m(P2)
T = nil
If T<> nil then
m(P1)
gotoxy(C,L)
write(t^.el.ch)
m(P2)
T = 4, L = 5, C = 40, CA = 20
If T<> nil then
m(P1)
gotoxy(C,L)
write(t^.el.ch)
m(P2)
T = 6, L = 4, C = 50, CA = 40
If T<> nil then
m(P1)
gotoxy(C,L)
write(t^.el.ch)
m(P2)
T = nil
Consideremos:
P1: T^.E,L+1,C-abs(CA – C) div 2, C
P2: T^.D,L+1,C+abs(CA – C) div 2, C
E o m representa a rotina mostra
If T<> nil then
m(P1)
gotoxy(C,L)
write(t^.el.ch)
m(P2)
If T<> nil then
m(P1)
gotoxy(C,L)
write(t^.el.ch)
m(P2)
3
2
7
4
6
T = nil
If T<> nil then
m(P1)
gotoxy(C,L)
write(t^.el.ch)
m(P2)
T = nil
If T<> nil then
m(P1)
gotoxy(C,L)
write(t^.el.ch)
m(P2)
T = nil
If T<> nil then
m(P1)
gotoxy(C,L)
write(t^.el.ch)
m(P2)
5