Son un caso especial de
listas, donde la adición de nuevos elementos se hace por el final de la
estructura, y la eliminación por el frente de la estructura. Se las conod¡ce
como estructuras FIFO. Se pueden implementar con arrays o simularlas con arrays.
·
Reestructuración :
cuando llega al tope, se desplaza todo a la izquierda.
·
Retroceso : ir
desplazando todo a la izquierda.
Lo mejor es implementarlo con
arrays circulares (similares a las listas circulares).
Si final=NULO entonces
frente
auxi
si no
final^.sig
auxi
fin si
final
auxi
Procedure Inicialización
(variable frente, final :puntero) ;
Begin
frente :=NIL ;
final :=NIL ;
end ;
{-------------------------------------------------------------------------------}
Procedure Meter (variable
final, frente :puntero ;elemento :Tipoelemento) ;
Variable
auxi :puntero ;
Begin
New(auxi) ;
auxi^.elem :=elem ;
auxi^.sig :=NIL ;
If final=NIL then
frente :=auxi
Else
Else
final^.sig :=auxi ;
final :=auxi ;
end ;
{-----------------------------------------------------------------------------}
Procedure Sacar
(..................
....................) ;{mientras no esté
vacía}
Variable auxi :puntero
Begin
auxi :=frente ;
elemento :=frente^.elemento ;
frente :=frente^.sig ;
If frente=NIL then
final :=NIL ;
Dispose(auxi) ;
end ;
{----------------------------------------------------------------------------}
n
Simulación con Arrays
(circulares) :
Ahora sig no es necesario.
Tiene que haber elemento cabecera que marque principio y fin.
Procedure Inicializar
(variable frente,final :integer) ;
Begin
frente :=1 ;
{1 va a ser el elemento cabecera}
final :=1 ;
end ;
Frente apunta siempre a
cabecera (vacío), nunca al 1º,y la nueva cabecera aumenta. { se sacan datos y
luego aumenta frente}
Function Vacia (frente,final :integer) ;
Begin
Vacia :=frente=final ;
end ;
{Cabecera puede ser 1, 3,
5,...}
En Meter :
final
final
MOD Max+1 {para que de la vuelta al llegar al final a Max}. Si
final^.sig=frente, está llena.
Function Llena (final, frente :integer) ;
Begin
Llena :=final
MOD Max+1=frente ;
end ;
Procedure
Meter (var final :integer ;elem :Tipoelemento) ;
Begin
final :=final
MOD Max+1 ;
a[final] :=elem ;
End ;
Procedure Sacar (var frente :integer ;elem :Tipoelemento) ;
Begin
elemento :=a[frente
MOD Max+1] ;
frente :=frente
MOD Max+1 ;
End ;
Estructura de datos no lineal
caracterizada porque en ella cada elemento, excepto la raiz, tiene un único
elemento predecesor, y cada elemento puede tener varios elementos sucesores o
siguientes.
A los elementos de un árbol
se les llama NODOS. La definición de árbol se puede hacer como : un árbol
está formado por la raiz y un conjunto disjunto de subárboles. Se pueden
reperesentar como conjuntos.
·
Grado de un Nodo : Es el
número de hijos o subárboles que descienden de él. Un Nodo de grado 0 (el de
más abajo) se llama HOJA.
·
Nivel de un Nodo : Es el
número de elementos que hay que recorrer para llegar desde la raíz sabiendo
que la raíz está en nivel 1.
·
Altura de un árbol : Es
el máximo de los niveles de sus Nodos. Los árboles pueden tener un número
indeterminado de hijos (árboles generadores).
·
Arbol Binario : Es aquel
en que cada Nodo tiene como máximo grado 2.
Un arbol binario está Completo cuando sus Nodos son de grado 2 o son Hojas.
Un arbol binario está Lleno cuando está completo y además todas sus ramas
tienen la misma
altura.
Los árboles binarios se suelen emplear para representar expresiones aritméticas.
·
Arbol Equilibrado : Es
aquel en el que las alturas de sus ramas se diferencian en 1 como máximo.
Los recorridos de un árbol
se hacen recursivamente. Estos recorridos pueden ser :
·
In Orden :
Subárbol Izquierdo - Raiz - Subárbol Derecho
·
Pre Orden : (Notación
Polaca Infija)
Raiz - Subárbol Izquierdo - Subárbol Derecho
·
Post Orden : (Notación
Polaca PostFija)
Subárbol Izquierdo - Subarbol Derecho - Raiz
Un árbol binario de búsqueda
es aquel en el que cada elemento es superior (en valor) a los de su subárbol
izquierdo, e inferior a los del subárbol derecho. Por ejemplo :
H-B-Q-A-F-D
raiz
H
B
Q
A
F
D
La ventaja es que se busca
por su lista (efectividad como búsqueda binaria).
Los registros que se emplean
tienen el siguiente formato :
D a
t o HI
HD
Type
puntero=^nodo ;
nodo=RECORD
elemento :Tipoelemento ;
izqdo,dcho :puntero ;
end ;
Var
elemento :Tipoelemento ;
raiz :puntero ;
Procedure Inicializar
(variable raiz :puntero) ;
Begin
raiz :=NIL ;
end ;
Function
ArbolVacio(raiz :puntero) :boolean ;
Begin
ArbolVacio :=raiz=NIL ;
end ;
Procedure Buscar (raiz :puntero :elemento :Tipoelemento ;variable
ant, act :puntero) ;
Variable
encontrado :boolean ;
{ indica si está o no el dato}
Begin
act :=raiz ;
ant :=NIL ;
encontrado :=false ;
While (act<>NIL) AND (NOT encontrado) do
If act^.elemento=elemento then
encontrado :=true
Else
Begin
and :=act ;
If act^.elemento > elemento then
act :=act^.izqdo
Else
act :=act^.dcho ;
end ;
end ;
Procedure Altas (variable
raiz :puntero ; elemento :Tipoelemento) ;
Var
ant,act :puntero ;
auxi :puntero ;
Begin
Buscar
(raiz,elemento,ant,act) ;
If
act<>NIL then
WriteLn(‘Ya existe’) ;
Else {alta}
Begin
New (auxi) ;
auxi^.izqdo :=NIL ;
auxi^.dcho :=NIL ;
auxi^.elemento :=elemento ;
If ant=NIL then
raiz :=auxi
Else
If ant^.elemento > elemento then
ant^.izqdo :=auxi
Else
ant^.dcho :=auxi ;
end ;
end ;
Procedure Bajas (variable
raiz :puntero ; elemento :Tipoelemento) ;
Var
auxi,
ant,act :puntero ;
Begin
Buscar
(raiz, elemento, ant, act) ;
If act=NIL then
WriteLn(‘No está’)
Else
Begin
If (act^.izq=NIL) AND (act^.dcho=NIL) then
If ant=NIL then
raiz :=NIL
Else
If ant^.izqdo=act then
ant^.izqdo :=NIL
Else
ant^.dcho :=NIL
Else {no es hoja}
If (act^.dcho <>NIL) then
If ant=NIL then
raiz :=act^.dcho
Else
If ant^.izqdo= act then
ant^.izqdo :=act^.dcho
Else
ant^.dcho :=act^.dcho
Else
If (act^.izqdo<>NIL) AND (act^.dcho=NIL) then
If ant=NIL then
raiz :=act^.izqdo
Else
If ant^.izqdo=act then
ant^.izqdo :=act^.izqdo
Else
ant^.dcho :=act^.izqdo
Else {existe, no es hoja, tiene 2 hijos}
{If (act^.izqdo<>NIL) AND (act^.dcho<>NIL)
then}
Begin
ant :=act ;
auxi :=act^.izqdo ; {para buscar su
inmediato inferior}
While auxi^.dcho<>NIL do
Begin
ant :=auxi ;
auxi :=auxi^.dcho ;
end ;
act^.elemento :=auxi^.elemento ;
If ant=act then
ant^.izqdo :=auxi^.izqdo ;
Else
ant^.dcho :=auxi^.izqdo ;
act :=auxi ;
end ;
Dispose(act) ;
end ;
End ;
Procedure
Recorrer (raiz :puntero) ;
Begin {In Orden}
If
raiz<>NIL then {condición de salida de la recursión}
Begin
Recorrer (raiz^.izqdo) ;
WriteLn(raiz^.clave) ;
Recorrer (raiz^.dcho) ;
End ;
End ;
n
Implementación de árboles
con arrays :
raiz
elemento
izqdo dcho
vacio
0
2
1
3
4
5
6
7
8
0
Const
Max=100 ;
Type
Reg=RECORD
elemento :Tipoelemento ;
izqdo :integer ;
dcho :integer ;
end ;
arr
=ARRAY [1..Max] of Reg ;
Var
a :arr ;
raiz :integer ;
vacio :integer ;
{para libres}
Procedure Iniciar (var a :arr ;var
vacio :integer) ;
Var i :integer ;
Begin
vacio :=1 ;
For i :=1
to (Max-1) do
a[i].dcho :=i+1 ;
a[Max].dcho :=0 ;
end ;
Procedure
Inicializar (var raiz :integer) ;
Begin
raiz :=0 ;
end ;
Procedure
Buscar (raiz :integer ;elemento :Tipoelemento ;var ant,act :integer ;
vacio :integer ;a :arr) ;
Var encontrado :boolean ;
Begin
ant :=0 ;
act :=raiz ;
encontrado :=false ;
While
(NOT encontrado) AND (act<>0) do
If a[act].elemento=elemento then
encontrado :=true
Else
If a[act].elemento > elemento then
begin
ant :=act ;
act :=a[act].izqdo
end
Else
begin
ant :=act ;
act :=a[act].dcho
end ;
End ;
Procedure
Altas (variable raiz :integer ; elemento :Tipoelemento ;variable
a :arr ; variable vacio :integer) ;
Variable
ant,act :integer ;
auxi :integer ;
Begin
Buscar(raiz,elemento,ant,act,vacio,a) ;
If
act<>0 then
WriteLn(‘Ya está el dato’)
Else
begin
Reservar (auxi, a, vacio) ;
a[auxi].elemento :=elemento ;
a[auxi].dcho :=0 ;
a[auxi].izqdo :=0 ;
If ant=0 then
raiz :=auxi
Else
If a[ant].elemento > elemento then
a[ant].izqdo :=auxi
Else
a[ant].dcho :=auxi ;
end ;
End ;
Procedure Reservar (var auxi :integer ;
var a :arr ; var vacio :integer) ;
Begin
auxi :=vacio ;
vacio :=
a[vacio].dcho ;
End ;
Procedure Bajas (var raiz :integer ;elemento :Tipoelemento ;var
vacio :integer ; var a :arr) ;
Variable ant, act,aauxi :integer ;
Begin
Buscar
(raiz, elemento, ant,act,vacio,a) ;
If
act=0 then
WriteLn(‘No existe’)
Else
begin
If (a[act].dcho=0) AND
(a[act].izqdo=0) then
If ant=0 then
raiz :=0
Else
If a[ant].izqdo=act then
a[ant].izqdo :=0
Else
a[ant].dcho :=0
Else
If (a[act].izqdo<>0) AND (a[act].dcho=0) then
If ant=0 then
raiz :=a[act].izqdo
Else
If a[ant].izqdo =act then
a[ant].izqdo :=a[act].izqdo
Else
a[ant].dcho :=a[act].izqdo
Else
If (a[act].izqdo=0) AND (a[act].dcho<>0) then
If ant=0 then
raiz :=a[act].dcho
Else
If a[ant].izqdo= act then
a[ant].izqdo :=a[act].dcho
Else
a[ant].dcho :=a[act].dcho
Else
If (a[act].izqdo<>0) AND (a[act].dcho<>0) then
begin
ant :=act ;
auxi :=a[act].izqdo ;
While a[auxi].dcho<>0 do
begin
ant :=auxi ;
auxi :=a[auxi].dcho ;
end ;
a[act].elemento :=a[auxi].elemento ;
If ant=act then
a[ant].izqdo :=a[auxi].izqdo
Else
a[ant].dcho :=a[auxi].izqdo ;
act :=auxi ;
end ;
End ;
Liberar
(act, a, vacio) ;
End ;
End ;
Procedure
Liberar (act :integer ;variable a :arr ; variable vacio :integer) ;
Begin
a[act].dcho :=vacio ;
vacio :=act ;
End ;