Índice >
Árvore >
Árvore Binária
Instituto de Ciências Matemáticas de São Carlos
Departamento de Computação e Estatística
SCE182 - Algoritmos e Estruturas de Dados 1
Profs. Resp.: Graça Pimentel e Maria Cristina
Árvore Binária
Uma Árvore Binária T é um conjunto finito de
elementos denominados nós ou vértices, tal que:
-
T = 0 e a árvore é dita vazia ou
-
existe um nó especial r, chamado raiz de T, os restantes
podem ser divididos em dois subconjuntos disjuntos, Tre e Trd,
que são as subárvores esquerda e direita de r, respectivamente
e as quais, por sua vez, também são árvores binárias.
Definição da Estrutura de Dados
Type
PNo = ^no;
no = record
info: Telem;
esq, dir: PNo;
End;
Type tree: PNo;
Operações associadas ao TAD árvore binária
padrão:
1. Definir uma árvore vazia
Definir uma árvore vazia deve ser utilizado antes de qualquer outro.
Procedure Define(var t: tree);
Begin
t:=nil;
End;
2. Criar um nó raiz
Retorna o nó raiz da árvore em t
Procedure Cria_Raiz(var t: tree; item: Telem);
Var no: tree;
Begin
new(nó);
no^.esq:=nil;
no^.dir:=nil;
no^.info:=item;
t:=no;
End;
3. Verificar se árvore vazia ou não
Retorna true se árvore vazia, false c.c.
Function Vazia (t:tree):boolean;
Begin
vazia:=(t=nil);
End;
4. Criar um filho à direita de um dado nó
- Busca elemento contendo Item_Pai
- Se Item_Pai ainda não possui filho à direita, então
cria um filho à sua direita com o conteúdo de item.
Procedure Adicionar_Dir(t: tree; item_pai, item: Telem)
Var pai,
no: tree;
Begin
pai:=Localiza(t,item_pai);
If(pai<>nil) Then
If (pai^.dir<>nil) Then
erro("item já possui subárvore direita")
Else
Begin
New(nó);
no^.esq:=nil;
no^.dir:=nil;
no^.info:=item;
pai^.dir:=nó;
End;
End;
5. Criar um filho ŕ esquerda de um dado nó
Procedure Adicionar_Dir(t: tree; item_pai, item: Telem)
Var pai,
no: tree;
Begin
pai:=Localiza(t,item_pai);
If(pai<>nil) Then
If (pai^.esq<>nil) Then
erro("item já possui subárvore direita")
Else
Begin
New(nó);
no^.esq:=nil;
no^.dir:=nil;
no^.info:=item;
pai^.esq:=nó;
End;
End;
6. Verificar qual o nível de um dado nó
- Retorna o nível onde está um nó com item pesquisado
- Se item não existe retorna zero
Function Nível (t: tree; item: Telem): integer;
Var n: integer;
achou:boolean;
Procedure Travessia (ptr: tree; VAR niv: integer; item:Telem; VAR achou:boolean);
Begin
If ptr<>nil Then
Begin
niv:=niv+1;
If Igual(ptr^.info, item) Then
achou:=TRUE;
Else
Begin
Travessia(ptr^.esq, niv, item, achou);
If (NOT achou) then
Travessia(ptr^.dir, niv, item, achou);
If (NOT achou) Then
niv:=niv-1;
End;
End;
End;
Begin {n¡vel}
achou:= false;
n:= 0;
Travessia(t,n,item, achou);
nivel:=n;
End;
7. Retornar o pai de um dado nó
- Dado um item, procura se item existe na árvore
- Caso positivo retorna o conteúdo do pai do nó
Function Pai(t: tree; item:Telem):Telem;
Var achou: boolean;
it : Telem;
Procedure Travessia(t: tree; item: Telem; var it: Telem; var achou:Boolean);
Begin
If not Vazia(t) Then
Begin
If t^.esq<>nil Then
If Igual(item, t^.esq^.info) Then
Begin
achou:=true;
it:=t^.info;
End;
If not achou Then
If t^.dir<>nil Then
If Igual(item, t^.dir^.info) Then
Begin
achou:=true;
it:=t^.info;
End;
If not achou Then
Travessia(t^.esq, item, it, achou);
If not achou Then
Travessia(t^.dir, item, it, achou);
End;
End; {Travessia}
Begin {pai}
If not Vazia(t) Then
Begin
achou:=false;
If Igual(item, t^.info) Then
pai:=t^.info; {pai do raiz é ele próprio}
Else
Begin
Travessia(t,item,it,achou);
pai:=it;
End;
End;
End;
Modos de Travessia
Árvore
Índice