Árboles binarios

Algoritmo propuesto a ejercicio de clase (Eliminar un dato de una lista simplemente ligada)

int p,q
lea dato
lea tope
p=q=tope
if(dato == tope(DATO)){
tope = tope(liga)
libere(p)
}
else{
while(p != NULL){
if(dato == p(DATO)){
q(liga) = p(liga)
libere(p)
break
}
else{
q=p
p=p(liga)
}
}
}

COLAS

Definición
Una cola es una lista de elementos en la que éstos ingresan por un extremo y se eliminan por el otro. Los elementos se eliminan de la cola en el mismo orden en el que ingresaron a ella, por esta razón, las colas, también son conocidas como estructuras FIFO (First-In, First-Out: Primero en entrar,Primero en salir).
Algunos ejemplos de colas en la vida real son: colas de personas para ingresar a un cine, colas de archivos para ser impresos, colas de pedidos en un restaurante, etc.

Representación de colas
Las colas se representan mediante el uso de arreglos unidimensionales o de listas ligadas. A continuación se presentan representaciones gráficas de las pilas utilizando para ello, arreglos unidimensionales o vectores.
Inicialmente se deben definir tres valores básicos para trabajar con colas:
• Frente, indica la posición en la que está ubicado el primer elemento de la cola
• Final, indica la posición en la que está ubicado el último elemento de la cola
• Máximo, indica el tamaño de la cola

2.2 Operaciones con colas
• Insertar un elemento, las inserciones se llevan a cabo por el final de la cola
• Eliminar un elemento, las eliminaciones se llevan a cabo por el frente de la cola
Es importante aclarar que cuando un elemento es eliminado, los demás NO se desplazan dentro de la cola, es decir, ningún elemento “sube” a ocupar la posición que ha dejado libre el elemento eliminado. De igual forma, cuando un elemento ingresa a una cola, NO “empuja” a los elementos que ya están en el interior de la estructura.

Algoritmo para insertar en una cola sencilla

Algoritmo para eliminar en una cola sencilla

Colas circulares
En este tipo de estructuras, el primer elemento puede estar precedido por el último. Los siguientes ejemplos gráficos representan el comportamiento de una cola en la cual se han eliminado de forma secuencial dos elementos (XX , YY) y luego se ingresa un nuevo elemento (PP), a pesar de que FINAL = MAX, sin embargo como la cola es circular, el último elemento queda en la posición 1:



Algoritmo para insertar en una cola circular


Algoritmo para eliminar de una cola circular

Doble cola
En este tipo de estructura los elementos pueden ser insertados o eliminados por cualquiera de los dos extremos que posee, (frente o final). La siguiente es una representación gráfica de una doble cola:

La doble flecha en cada extremo indica que se pueden insertar o eliminar elementos por cada “lado”.
Cuando sólo uno de los dos extremos recibe ambas operaciones (insertar y eliminar), se dice que tenemos un caso de Doble cola con entrada o salida restringida, así:
• Entrada restringida

• Salida restringida