25-E-Arrieta-Manual-de-Estructura-de-Datos

Vista previa del material en texto

1
MANUAL DE ESTRUCTURA DE DATOS
Evelio Ramiro Arrieta Torres
M
an
ua
l d
e 
ES
tr
uc
tu
ra
 d
e 
D
at
os
EVELIO ARRIETA In
st
itu
to
 Te
cn
ol
óg
ic
o 
D
e 
So
le
da
d 
A
tlá
nt
ic
o 
IT
SA
 (9
58
-5
73
93
)
IS
BN
 9
78
-9
58
-5
91
73
-9
-2
Introducción ......................................................................................................... 4
1. COLAS............................................................................................................... 5
1.1 Definición .................................................................................................. 5
1.2 Operaciones básicas con colas .................................................................. 6
1.2.1 Agregar un elemento ........................................................................ 6
1.2.2 Eliminar un elemento de una cola .................................................... 7
1.3 Aplicaciones del uso de Colas ................................................................. 10
1.4 Cola circular ............................................................................................ 10
1.5 Ejercicios Colas ....................................................................................... 12
2. PILAS .............................................................................................................. 13
2.1 Definición ................................................................................................ 13
2.2 Operaciones básicas con pilas ................................................................ 13
2.2.1 Inserción de elementos .................................................................. 14
2.2.1.1 Inserción en una pila vacía ..................................................... 14
2.2.2 Eliminación en una Pila ................................................................... 15
2.5 Aplicaciones del uso de Pilas .................................................................. 17
2.6 Ejercicios con Pilas .................................................................................. 17
3. LISTAS ENLAZADAS ......................................................................................... 18
3.1 Definición ................................................................................................ 18
3.2 Declaraciones de tipos para manejar listas............................................. 18
3.3 Operaciones básicas con listas ................................................................ 19
3.3.1 Insertar elementos en una lista abierta .......................................... 19
3.3.2 Eliminar elementos en una lista abierta ......................................... 19
3.4 LISTAS DOBLEMENTE ENLADAS (Listas dobles) ....................................... 24
3.4.1 Operaciones básicas con listas doblemente enlazadas .................. 24
3.5 Ejercicios con Listas enlazadas ................................................................ 28
4. Recursividad ................................................................................................... 28
4.1 Concepto de recursividad. ...................................................................... 28
4.2 Ejemplos ................................................................................................. 29
4.3 Uso de la recursividad. ............................................................................ 32
4.4 Ejercicios ................................................................................................. 34
5. Arboles ........................................................................................................... 35
5.1 Definición ................................................................................................ 35
5.2 Operaciones básicas con árboles ............................................................ 36
5.3 Recorridos por árboles............................................................................ 37
CO
N
TE
N
ID
O
5.3.1 Pre-orden .................................................................................................. 37
5.3.2 In-orden .................................................................................................... 38
5.3.3 Post-orden ................................................................................................ 38
5.4 Eliminar nodos en un árbol .......................................................................... 38
5.5 Arboles ordenados ....................................................................................... 39
5.6 Árboles binarios de búsqueda (ABB) ........................................................... 40
5.6.1 Definición .................................................................................................. 40
5.6.2 Operaciones en ABB ................................................................................. 40
5.6.3 Buscar un elemento .................................................................................. 41
5.6.4 Insertar un elemento ................................................................................ 41
5.6.5 Borrar un elemento .................................................................................. 42
Ejemplo 1: Borrar un nodo hoja .............................................................................. 43
Ejemplo 2: Borrar un nodo rama con intercambio de un nodo hoja. ............................ 43
Ejemplo 3: Borrar un nodo rama con intercambio de un nodo rama. .......................... 44
5.7 EJERCICIOS ................................................................................................... 48
6. Bibliografía de Referencia .............................................................................. 49
CO
N
TE
N
ID
O
4
Introducción
En la práctica, la mayor parte de información útil no aparece aislada en forma de datos simples, sino que 
lo hace de forma organizada y estructurada. Los diccionarios, guías, enciclopedias, etc., son colecciones 
de datos que serían inútiles si no estuvieran organizadas de acuerdo con unas determinadas reglas. 
Además, tener estructurada la información supone ventajas adicionales, al facilitar el acceso y el manejo 
de los datos. Por ello parece razonable desarrollar la idea de la agrupación de datos, que tengan un 
cierto tipo de estructura y organización interna.
La selección de una estructura de datos frente a otra, a la hora de programar es una decisión importante, 
ya que ello influye decisivamente en el algoritmo que vaya a usarse para resolver un determinado 
problema. El objetivo de este manual no es sólo la descripción de las distintas estructuras, sino también 
la comparación de las mismas en términos de utilidad para la programación. 
Empecemos recordando que un dato de tipo simple, no está compuesto de otras estructuras, que no 
sean los bits, y que por tanto su representación sobre el ordenador es directa, sin embargo existen 
unas operaciones propias de cada tipo, que en cierta manera los caracterizan. Una estructura de datos 
es, a grandes rasgos, una colección de datos (normalmente de tipo simple) que se caracterizan por 
su organización y las operaciones que se definen en ellos. Por tanto, una estructura de datos vendrá 
caracterizada tanto por unas ciertas relaciones entre los datos que la constituyen (ej. el orden de las 
componentes de un vector de números reales), como por las operaciones posibles en ella. Esto supone 
que podamos expresar formalmente, mediante un conjunto de reglas, las relaciones y operaciones 
posibles.
5
1. COLAS
1.1 Definición
Una cola es un tipo especial de lista abierta en la que sólo se puede insertar nodos en uno de los 
extremos de la lista y sólo se pueden eliminar nodos en el otro. Además, como sucede con las pilas, las 
escrituras de datos siempre son inserciones de nodos, y las lecturas siempre eliminan el nodo leído.
Este tipo de lista es conocido como lista FIFO (First In FirstOut), el primero en entrar es el primero en 
salir.
El símil cotidiano es una cola para comprar, por ejemplo, las entradas del cine. Los nuevos compradores 
sólo pueden colocarse al final de la cola, y sólo el primero de la cola puede comprar la entrada.
Las colas se representan por listas enlazadas (a) o por arrays (b). Se necesitan dos punteros o variables: 
frente y final, y la lista o array de n elementos. 
Fuente: Propia
El nodo típico para construir colas es el mismo para la construcción de listas:
struct nodo {
 int dato;
 struct nodo *siguiente;
}
Una cola, entonces, es una lista abierta. Así que sigue siendo muy importante que el programa nunca 
pierda el valor del puntero al primer elemento, igual que pasa con las listas abiertas. Además, debido al 
funcionamiento de las colas, también deberemos mantener un puntero para el último elemento de la 
cola, que será el punto donde insertemos nuevos nodos.
Teniendo en cuenta que las lecturas y escrituras en una cola se hacen siempre en extremos distintos, lo 
más fácil será insertar nodos por el final, a continuación del nodo que no tiene nodo siguiente, y leerlos 
desde el principio, hay que recordar que leer un nodo implica eliminarlo de la cola.
100 48264 119frente
frente final
final
a)
b)
6
1.2 Operaciones básicas con colas
De nuevo nos encontramos ante una estructura con muy pocas operaciones disponibles. Las colas sólo 
permiten agregar y leer elementos:
·	 Agregar: Inserta un elemento al final de la cola.
·	 Leer: Lee y elimina un elemento del principio de la cola.
1.2.1 Agregar un elemento
Las operaciones con colas son muy sencillas, prácticamente no hay casos especiales, salvo que la cola 
esté vacía.
1.2.1.1 Agregar elemento en una cola vacía
 
Cola vacía
Partiremos de que ya tenemos el nodo a insertar y, por supuesto un puntero que apunte a él, además 
los punteros que definen la cola, primero y último que valdrán NULO:
Fuente: Propia
 
Elemento encolado
El proceso es muy simple, bastará con que:
1. Hacer que nodo.siguiente apunte a NULO.
2. Que el puntero primero apunte a nodo.
3. Y que el puntero último también apunte a nodo.
1.2.1.2 Agregar elemento en una cola no vacía
Fuente: Propia
7
Cola no vacía
De nuevo partiremos de un nodo a insertar, con un puntero que apunte a él, y de una cola, en este caso, 
al no estar vacía, los punteros primero y último no serán nulos:
Elemento insertado en la cola
El proceso sigue siendo muy sencillo:
1. Hacemos que nodo.siguiente apunte a NULO.
2. Después que ultimo.siguiente apunte a DATO (último.nodo).
3. Y actualizamos último, haciendo que apunte a nodo.
1.2.1.3 Agregar elemento en una cola, caso general
Para generalizar el caso anterior, sólo necesitamos agregar una operación:
1. Hacemos que nodo.siguiente apunte a NULO.
2. Si último no es NULO, hacemos que ultimo.siguiente apunte a nodo.
3. Y actualizamos último, haciendo que apunte a nodo.
4. Si primero es NULO, significa que la cola estaba vacía, así que haremos que primero apunte también 
a nodo.
1.2.2 Eliminar un elemento de una cola
Ahora también existen dos casos, que la cola tenga un solo elemento o que tenga más de uno.
1.2.2.1 Eliminar un elemento en una cola con más de un elemento
Usaremos un puntero a un nodo auxiliar:
Cola con más de un elemento
1. Hacemos que nodo apunte al primer elemento de la cola, es decir a primero.
2. Asignamos a primero la dirección del segundo nodo de la pila: primero.siguiente.
3. Guardamos el contenido del nodo para devolverlo como retorno, recuerda que la operación de 
lectura en colas implican también borrar. 
4. Liberamos la memoria asignada al primer nodo, el que queremos eliminar.
Fuente: Propia
8
1.2.2.2 Eliminar un elemento en una cola con un solo elemento
Cola con un elemento
También necesitamos un puntero a un nodo auxiliar:
1. Hacemos que nodo apunte al primer elemento de la pila, es decir a primero.
 
Fuente: Propia
2. Asignamos NULO a primero, que es la dirección del segundo nodo teórico de la cola: primero.
siguiente.
3. Guardamos el contenido del nodo para devolverlo como retorno, recuerda que la operación de 
lectura en colas implican también borrar. 
4. Liberamos la memoria asignada al primer nodo, el que queremos eliminar.
5. Hacemos que último apunte a NULO, ya que la lectura ha dejado la cola vacía.
1.2.2.3 Eliminar un elemento en una cola caso general
1. Hacemos que nodo apunte al primer elemento de la pila, es decir a primero.
2. Asignamos a primero la dirección del segundo nodo de la pila: primero.siguiente.
3. Guardamos el contenido del nodo para devolverlo como retorno, recuerda que la operación de 
lectura en colas implican también borrar. 
4. Liberamos la memoria asignada al primer nodo, el que queremos eliminar.
5. Si primero es NULO, hacemos que ultimo también apunte a NULO, ya que la lectura ha dejado 
la cola vacía.
9
Colas en java usando vectores. Ejemplo
import javax.swing.*;
public class Colas {
 public static void main (String args[]){
 byte max=9,op=0;
 int i=0,fr=-1,fin=-1;
 int V []= new int[10];
 while(op!=4){
op=Byte.parseByte(JOptionPane.showInputDialog(“Digite un numero\n”+
 “1.Insertar\n”+
 “2.Eliminar\n”+
 “3.Mostrar\n”+
 “4.Salir”));
 switch(op){
 case 1:
 if(fin!=max){
 if(fr==-1){
 fin=fin+1;
 fr=fr+1;
 V[fin]= Byte.parseByte(JOptionPane.showInputDialog(“Digite el valor”));
 }else{
 fin=fin+1;
 V[fin]= Byte.parseByte(JOptionPane.showInputDialog(“Digite el valor”));
 }
 }else{
 JOptionPane.showMessageDialog(nulo, “Overflow”);
 }
 break;
 case 2:
 if(fin!=-1){
 if(fin==fr){
 fin=-1;
 fr=-1;
 }else{
 fr=fr+1;}
 }else{
 JOptionPane.showMessageDialog(nulo, “Underflow”);
 }
 break;
 case 3:
 if(fin!=-1){
 for(i=fr;i<=fin;i=i+1){
 JOptionPane.showMessageDialog(nulo,V[i]); 
 } 
 } else{
 JOptionPane.showMessageDialog(nulo, “Cola vacia”);
 }
 break;
 case 4:
 JOptionPane.showMessageDialog(nulo, “Gracias”);
 break;
}
 }
}
}
10
1.3 Aplicaciones del uso de Colas
Las colas se pueden utilizar habitualmente en muchas áreas de la informática. Quizás la aplicación más 
común de las colas es la organización de tareas de un ordenador. En general, los trabajos enviados a 
un ordenador son “encolados” por éste, para ir procesando secuencialmente todos los trabajos en el 
mismo orden en que se reciben. Cuando el ordenador recibe el encargo de realizar una tarea, ésta es 
almacenada al final de la cola de trabajos. En el momento que la tarea que estaba realizando el procesador 
acaba, éste selecciona la tarea situada al principio de la cola para ser ejecutada a continuación. Todo 
esto suponiendo la ausencia de prioridades en los trabajos. En caso contrario, existirá una cola para 
cada prioridad. 
Otra de los usos de una cola es, por ejemplo, a la hora de gestionar eficientemente los trabajos que 
deben ser enviados a una impresora (o a casi cualquier dispositivo conectado a un computador). De 
esta manera, la maquina controla el envío de trabajos al dispositivo, no enviando un trabajo hasta que 
la impresora no termine con el anterior 
1.4 Cola circular
 Una cola circular o anillo es una estructura de datos en la que los elementos están de forma circular 
y cada elemento tiene un sucesor y un predecesor. Los elementos pueden consultarse, agregarse y 
eliminarse únicamente desde la cabeza del anillo que es una posición distinguida. Esta avanza en el 
sentido de las agujas del reloj.
Fuente: Propia
En la figura mostrada muestra una cola circular con un solo dato almacenado. La variable final es la 
posición en donde se hizo la última inserción. Después que se ha producido una inserción, final se 
mueve circularmentea la derecha. La implementación del movimiento circular se realiza utilizando la 
“teda” de los restos:
11
Programa en Java cola circular
import javax.swing.*;
public class Colas_Circulares {
public static void main(String args[]){
 int OP=0;
 int VH[]= new int [4];
 int Max=3;
 int Last=-1, First=-1;
 String A= “\n”;
 while(OP!=5){
 OP=Integer.parseInt(JOptionPane.showInputDialog(“Menu de Operaciones\n”+”1.Insertar\n”+”2.Elimi 
 nar\n”+”3.Imprimir\n”+”4.Imprimir First & Last\n”+”5.Salir\n”+”Escoja Opcion”));
 switch(OP){
 case 1:
 if((Last==Max && First==0)||(First==Last+1)){
 JOptionPane.showMessageDialog(nulo, “La Cola esta Llena”);
 }else if(First==-1 && Last==-1){
 Last++; First++;
 VH[Last]= Integer.parseInt(JOptionPane.showInputDialog(“Ingrese Datos”));
 }else if(First!=-1 && Last!=Max){
 Last++;
 VH[Last]= Integer.parseInt(JOptionPane.showInputDialog(“Ingrese Datos”));
 }else if(Last==Max && First!=0){
 Last=0;
 }
 break;
 case 2:
 if(First==-1 && Last==-1){
 JOptionPane.showMessageDialog(nulo, “La Cola Esta Vacia”);
 }else if(First==Last){
 Last=-1;
 First=-1;
 JOptionPane.showMessageDialog(nulo, “Se ha Eliminado el Unico Elemento en la cola”);
 }else if(First!=Last){
 First++;
 JOptionPane.showMessageDialog(nulo, “Se ha Eliminado el Primer Elemento de la Cola”);
 }else if(Last==Max){
 Last=0;
 }
 break;
 case 3:
 if(Last!=-1 && First!=-1){
 for(int i=First;i<=Last;i++){
 A=A+VH[i]+”,”;
 }
 JOptionPane.showMessageDialog(nulo, “Los Elementos de la Cola son: “ + A);
 }else if(Last!=Max){
 for(int j=Last;j<Last;j++){
 A=A+VH[j]+”,”;
 }
12
 for(int x=First;x<=Max;x++){
 A=A+VH[x]+”,”;
 }
 JOptionPane.showMessageDialog(nulo, “Los Elemetos de la Cola son: “ + A);
 }else{
 JOptionPane.showMessageDialog(nulo, “La Cola Esta Vacia”);
 }
 break;
 case 4:
 if(Last!=-1 && First!=-1){
 JOptionPane.showMessageDialog(nulo, “El Primer Elemento de la Cola es: “ +VH[First]+ “ El Ultimo 
Elemento de la Cola es: “ +VH[Last]);
 }else{
 JOptionPane.showMessageDialog(nulo, “La Cola Esta Vacia”);
 }
 break;
 case 5:
 JOptionPane.showMessageDialog(nulo, “Gracias Por Utilizar Nuestro Programa, EXITOS!!!”);
 break;
 default:
 JOptionPane.showMessageDialog(nulo, “Ha Digitado una Opcion Fuera de Rango”);
 }
 }
}
}
1.5 Ejercicios Colas
1. Escriba una rutina que reciba una Cola C de números enteros y mueva sus elementos a una nueva 
cola, pero manteniendo el orden de salida de los elementos. Al finalizar la Cola C no debe contener 
elementos. 
2. Escriba una rutina que reciba una Cola C de números enteros y mueva sus elementos a una nueva cola, 
pero invirtiendo el orden de salida de los elementos. Al finalizar la Cola C no debe contener elementos. 
3. Escriba una rutina que reciba dos Colas C1 y C2 de números enteros y devuelva una nueva Cola con 
los elementos concatenados en el orden C1 y C2. Es de destacar que las Colas recibidas no deben ser 
sufrir ningún tipo de cambio o alteración. 
4. Escriba una rutina que reciba dos Colas C1 y C2 de números enteros y proceda a intercambiar sus 
elementos, pero manteniendo el orden de salida de los mismos. Al finalizar la rutina, la Cola C1 tendrá 
los elementos de la Cola C2 y esta a su vez tendrá los elementos de la Cola C1. 
5. Escriba una rutina que reciba una Cola C de números flotantes y devuelva una nueva Cola pero con 
los elementos invertidos, es decir el último de la Cola C, pasará a ser el primero de la nueva Cola. Es de 
destacar que la Cola C no debe sufrir ningún tipo de cambio o alteración. 
6. Escriba una rutina que reciba una Cola C de números flotantes y devuelva una Pila, manteniendo el 
orden de salida de los elementos. Es de destacar que la Cola C no debe sufrir ningún tipo de cambio o 
alteración.
13
7. Escribir un programa en el que generen 100 números aleatorios en el rango -25…. + 25 y se guarden 
en una cola. Una vez creada la cola, el usuario puede solicitar que se forme otra cola con los números 
negativos que tiene la cola original. 
8. Escribir un programa que ingrese dos colas del mismo tipo e indique si las dos colas son idénticas. 
9. Un pequeño supermercado dispone en la salida de tres cajas de pago. En el local hay 25 carritos de 
compra. Escribir un programa que simule el funcionamiento, siguiendo las siguientes reglas: 
a. SI cuando llega un cliente no hay ningún carrito disponible, espera a que lo haya. 
b. Ningún cliente se impaciente y abandona el supermercado sin pasar por alguna de las colas de las 
cajas. 
c. Cuando un cliente finaliza su compra, se coloca en la cola de la caja que hay menos gente, y no se 
cambia de cola. 
d. En el momento en que un cliente paga en la caja, su carrito de compra queda disponible. 
2. PILAS
2.1 Definición
Una pila es un tipo especial de lista abierta en la que sólo se pueden insertar y eliminar nodos en uno de 
los extremos de la lista. Estas operaciones se conocen como “push” y “pop”, respectivamente insertar 
y eliminar. Además, las escrituras de datos siempre son inserciones de nodos, y las lecturas siempre 
eliminan el nodo leído.
Estas características implican un comportamiento de lista LIFO (Last In First Out), el último en entrar es 
el primero en salir.
El símil del que deriva el nombre de la estructura es una pila de platos. Sólo es posible agregar platos en 
la parte superior de la pila, y sólo pueden tomarse del mismo extremo.
Fuente: Propia
Una pila es una lista abierta. Así que sigue siendo muy importante que nuestro programa nunca pierda 
el valor del puntero al primer elemento, igual que pasa con las listas abiertas.
Teniendo en cuenta que las inserciones y borrados en una pila se hacen siempre en un extremo, lo que 
consideramos como el primer elemento de la lista es en realidad el último elemento de la pila.
2.2 Operaciones básicas con pilas
Las pilas tienen un conjunto de operaciones muy limitado, sólo permiten las operaciones de “push” y 
“pop”:
·	 Push (Insertar): Agregar un elemento al final de la pila.
·	 Pop (Eliminar): Leer y eliminar un elemento del final de la pila.
14
2.2.1 Inserción de elementos
Las operaciones con pilas son muy simples, no hay casos especiales, salvo que la pila esté vacía.
2.2.1.1 Inserción en una pila vacía
Partiremos de que ya tenemos el nodo a insertar y, por supuesto un puntero que apunte a él, además 
el puntero a la pila valdrá NULO:
Fuente: Propia
Inserción en pila vacía
El proceso es muy simple, bastará con que:
1. nodo.siguiente apunte a NULO.
2. Pila apunte a nodo.
2.2.1.2 Insertar en una pila no vacía
Fuente: Propia
Push en pila no vacía
Podemos considerar el caso anterior como un caso particular de éste, la única diferencia es que podemos 
y debemos trabajar con una pila vacía como con una pila normal.
De nuevo partiremos de un nodo a insertar, con un puntero que apunte a él, y de una pila, en este caso 
no vacía:
Fuente: Propia
Resultado
El proceso sigue siendo muy sencillo:
1. Hacemos que nodo.siguiente apunte a Pila.
2. Hacemos que Pila apunte a nodo. 
15
2.2.2 Eliminación en una Pila
Eliminar (pop)
Ahora sólo existe un caso posible, ya que sólo podemos leer desde un extremo de la pila.
Partiremos de una pila con uno o más nodos, y usaremosun puntero auxiliar, nodo:
Fuente: Propia
Resultado
1. Hacemos que nodo apunte al primer elemento de la pila, es decir a Pila.
2. Asignamos a Pila la dirección del segundo nodo de la pila: Pila.siguiente.
3. Guardamos el contenido del nodo para devolverlo como retorno, recuerda que la operación pop 
equivale a leer y borrar. 
4. Liberamos la memoria asignada al primer nodo, el que queremos eliminar.
Si la pila sólo tiene un nodo, el proceso sigue siendo válido, ya que el valor de Pila.siguiente es NULO, y 
después de eliminar el último nodo la pila quedará vacía, y el valor de Pila será NULO.
16
Pilas en java ejemplo
import javax.swing.*;
public class Pilas {
 public static void main (String args[]){
 byte max=9,op=0;
 int tope=-1,i=0;
 byte V []= new byte[10];
 while(op!=4){ 
 op=Byte.parseByte(JOptionPane.showInputDialog(“Digite un numero\n”+
 “1.Insertar\n”+
 “2.Eliminar\n”+
 “3.Mostrar\n”+
 “4.Salir”));
 switch(op){
 case 1:
 if(tope!=max){
 tope=tope+1;
 V[tope]=Byte.parseByte(JOptionPane.showInputDialog(“Digite su valor”));
 }else{
 JOptionPane.showMessageDialog(nulo, “Overflow”);
 }
 break;
case 2:
 if(tope!=-1){
 tope=tope-1;
 }else{
 JOptionPane.showMessageDialog(nulo, “Underflow”);
 }
 break;
 case 3:
 if(tope!=-1){
 for(i=tope;i>=0;i=i-1){
 JOptionPane.showMessageDialog(nulo,V[i]); 
 } 
 } else{
 JOptionPane.showMessageDialog(nulo, “Pila vacia”);
 }
 break;
 case 4:
 JOptionPane.showMessageDialog(nulo, “Gracias”);
 break;
 }
 }
 }
}
17
2.5 Aplicaciones del uso de Pilas
Con la implementación de las pilas es posible el uso de la modulación (recursividad). La variable que 
llama al mismo procedimiento en el que está, habrá que guardarla así como el resto de variables de la 
nueva llamada, para a la vuelta de la recursividad ir sacándolas, esto es posible a la implementación de 
pilas. 
Las pilas también se utilizan en muchas aplicaciones que utilizamos con frecuencia. Por ejemplo, la gestión 
de ventanas en Windows (cuando cerramos una ventana siempre recuperamos la que teníamos detrás). Otro 
ejemplo es la evaluación general de cualquier expresión matemática para evitar tener que calcular el número de 
variables temporales que hacen falta. 
Por ejemplo: 
3 + 4 * (8 – 2 * 5) 
2.6 Ejercicios con Pilas
1. Escriba una rutina que reciba una Pila P de números enteros y mueva sus elementos a una nueva Pila, pero 
manteniendo el orden de salida de los mismos. Al finalizar la Pila P no debe contener elementos. 
2. Escriba una rutina que reciba una Pila P de números enteros y mueva sus elementos a una nueva Pila, pero 
invirtiendo el orden de salida de los mismos. Al finalizar la Pila P no debe contener elementos. 
3. Escriba una rutina que reciba dos Pilas P1 y P2 de números flotantes y apile las mismas en una nueva Pila 
resultante. Es de destacar que las Pilas recibidas no deben sufrir ningún tipo de cambio o alteración.
4. Escriba una rutina que reciba dos Pilas P1 y P2 de números enteros y proceda a intercambiar sus elementos, 
pero manteniendo el orden de salida de los elementos. Al finalizar la rutina, la Pila P1 tendrá los elementos 
de la Pila P2 y esta a su vez tendrá los elementos de la Pila P1. 
5. Escriba una rutina que reciba una Pila P de números enteros y devuelva una copia exacta de la misma. Es de 
destacar que la Pila P no debe sufrir ningún tipo de cambio o alteración. 
6. Escriba una rutina que reciba una Pila P de números flotantes y devuelva una nueva Pila pero con los 
elementos invertidos, es decir el último de la Pila P, pasará a ser el primero de la nueva Pila Es de destacar 
que la Pila P no debe sufrir ningún tipo de cambio o alteración. 
7. Escriba una rutina que reciba una Pila P de números flotantes y devuelva otra pila, manteniendo el orden 
de salida de los elementos. Es de destacar que la Pila P no debe sufrir ningún tipo de cambio o alteración.
8. En un archivo f están almacenados números enteros arbitrariamente grandes. La disposición es tal que hay 
un número entero por cada línea de F. Escribir un programa que muestre por pantalla la suma de todos los 
números enteros. Al resolver el problema habrá que tener en cuenta que, al ser enteros grandes, no pueden 
almacenarse en variables numéricas. 
9. Utilizar dos pilas para guardar los dos primeros números enteros, almacenándose digito a dígito. Al extraer 
los elementos de la pila, salen en orden inverso y, por lo tanto, de menor peso a mayor peso; se suman 
digito con digito y el resultado se guarda en una cola, también digito a digito. A partir de este primer paso 
se obtienen el siguiente número del archivo, se guarda en una pila y, a continuación, se suma digito a dígito 
con el número que se encuentra en la cola; el resultado se guarda en otra cola. El proceso se repite, nuevo 
número del archivo se mete en la pila, que se suma con el número actual de la cola.
18
Ejercicios Complementarios Pilas y Colas
1. Realizar un procedimiento que cuente la cantidad de elementos de una cola. Lo mismo para una 
pila y una lista. Las estructuras deben quedar en el estado original.
2. Realizar un procedimiento que invierta el orden de la cola. Lo mismo para una pila y una lista. 
3. Realizar un procedimiento que saque el elemento N de la cola. Lo mismo para una pila y una lista. 
Tener en cuenta que los demás elementos deben quedar en el mismo orden. 
4. Realizar un procedimiento que ingrese un elemento en la posición N de una cola. Lo mismo para 
una pila y una lista. Tener en cuenta que los demás elementos deben quedar en el mismo orden. 
5. Una cola prioridad tiene una estructura similar a la de una cola, con la diferencia que cada elemento 
tiene un campo que indica su prioridad. Los elementos se ingresan en la cola según el orden de 
prioridad. Realizar dos procedimientos, uno para ingresar un elemento en la cola prioridad y otro 
para extraerlo. Utilizar para ello un TDA COLA.
3. LISTAS ENLAZADAS
3.1 Definición
La forma más simple de estructura dinámica es la lista abierta. En esta forma los nodos se organizan 
de modo que cada uno apunta al siguiente, y el último no apunta a nada, es decir, el puntero del nodo 
siguiente vale NULO.
En las listas abiertas existe un nodo especial: el primero. Normalmente diremos que nuestra lista es un 
puntero a ese primer nodo y llamaremos a ese nodo la cabeza de la lista. Eso es porque mediante ese 
único puntero podemos acceder a toda la lista. 
Cuando el puntero que usamos para acceder a la lista vale NULO, diremos que la lista está vacía.
El nodo típico para construir listas tiene esta forma:
struct nodo {
 int dato;
 nodo *siguiente;
}
3.2 Declaraciones de tipos para manejar listas
Normalmente se definen varios tipos que facilitan el manejo de las listas, la declaración de tipos puede 
tener una forma parecida a esta:
struct nodo {
 int dato;
 nodo *siguiente;
}
Lista es el tipo para declarar listas, como puede verse, un puntero a un nodo y una lista son la misma 
cosa. En realidad, cualquier puntero a un nodo es una lista, cuyo primer elemento es el nodo apuntado.
19
3.3 Operaciones básicas con listas
Con las listas tendremos unas operaciones básicas que se pueden realizar:
·	 Agregar o insertar elementos.
·	 Buscar o localizar elementos.
·	 Borrar elementos.
·	 Moverse a través de una lista, anterior, siguiente, primero.
Cada una de estas operaciones tendrá varios casos especiales, por ejemplo, no será lo mismo insertar 
un nodo en una lista vacía, o al principio de una lista no vacía, o la final, o en una posición intermedia.
3.3.1 Insertar elementos en una lista abierta
Algunos casos de inserción en una lista se verán a continuación.
3.3.1.1 Insertar un elemento en una lista vacía
Este es uno de los casos más sencillo. Partiremosde que ya tenemos el nodo a insertar y, por supuesto 
un puntero que apunte a él, además el puntero a la lista valdrá NULO:
 
Fuente: Propia
El proceso es muy simple, bastará con que:
1. nodo.siguiente apunte a NULO.
2. Lista apunte a nodo.
3.3.1.2 Insertar un elemento en la primera posición de una lista
Fuente: Propia
Podemos considerar el caso anterior como un caso particular de éste, la única diferencia es que en el 
caso anterior la lista es una lista vacía, pero siempre podemos, y debemos considerar una lista vacía 
como una lista.
De nuevo partiremos de un nodo a insertar, con un puntero que apunte a él, y de una lista, en este caso 
no vacía:
Fuente: Propia
Insertado al principio de la lista
El proceso sigue siendo muy sencillo:
1. Hacemos que nodo.siguiente apunte a Lista.
2. Hacemos que Lista apunte a nodo.
20
3.3.1.3 Insertar un elemento en la última posición de una lista
Este es otro caso especial. Para este caso partiremos de una lista no vacía:
Fuente: Propia
Insertar al final
El proceso en este caso tampoco es excesivamente complicado:
1. Necesitamos un puntero que señale al último elemento de la lista. La manera de conseguirlo es 
empezar por el primero y avanzar hasta que el nodo que tenga como siguiente el valor NULO.
2. Hacer que nodo.siguiente sea NULO.
3. Hacer que ultimo.siguiente sea nodo.
 
Fuente: Propia
3.3.1.4 Insertar un elemento a continuación de un nodo cualquiera de una lista
De nuevo podemos considerar el caso anterior como un caso particular de este. Ahora el nodo “anterior” 
será aquel a continuación del cual insertaremos el nuevo nodo:
Insertar en medio
Suponemos que ya disponemos del nuevo nodo a insertar, apuntado por nodo, y un puntero al nodo a 
continuación del que lo insertaremos.
El proceso a seguir será:
1. Hacer que nodo.siguiente señale a anterior.siguiente.
2. Hacer que anterior.siguiente señale a nodo.
 
Fuente: Propia
Es muy importante que el programa nunca pierda el valor del puntero al primer elemento, ya que si no 
existe ninguna copia de ese valor, y se pierde, será imposible acceder al nodo y no podremos liberar el 
espacio de memoria que ocupa.
21
3.3.2 Eliminar elementos en una lista abierta
De nuevo podemos encontrarnos con varios casos, según la posición del nodo a eliminar.
3.3.2.1 Eliminar el primer nodo de una lista abierta
 
Eliminar primer nodo
Es el caso más simple. Partiremos de una lista con uno o más nodos, y usaremos un puntero auxiliar, 
nodo:
1. Hacemos que nodo apunte al primer elemento de la lista, es decir a Lista.
2. Asignamos a Lista la dirección del segundo nodo de la lista: Lista.siguiente.
3. Liberamos la memoria asignada al primer nodo, el que queremos eliminar.
Si no guardamos el puntero al primer nodo antes de actualizar Lista, después nos resultaría imposible 
liberar la memoria que ocupa. Si liberamos la memoria antes de actualizar Lista, perderemos el puntero 
al segundo nodo.
Fuente: Propia
Si la lista sólo tiene un nodo, el proceso es también válido, ya que el valor de Lista.siguiente es NULO, y 
después de eliminar el primer nodo la lista quedará vacía, y el valor de Lista será NULO.
Una operación que se suele usar para borrar listas completas es eliminar el primer nodo hasta que la 
lista esté vacía.
3.3.2.2 Eliminar un nodo cualquiera de una lista abierta
En todos los demás casos, eliminar un nodo se puede hacer siempre del mismo modo. Supongamos que 
tenemos una lista con al menos dos elementos, y un puntero al nodo anterior al que queremos eliminar. 
Y un puntero auxiliar nodo.
El proceso es parecido al del caso anterior:
1. Hacemos que nodo apunte al nodo que queremos borrar.
2. Ahora, asignamos como nodo siguiente del nodo anterior, el siguiente al que queremos eliminar: 
anterior.sig = nodo.sig
3. Eliminamos la memoria asociada al nodo que queremos eliminar.
 
Fuente: Propia
Si el nodo a eliminar es el último, es procedimiento es igualmente válido, ya que anterior pasará a ser el 
último, y anterior.siguiente valdrá NULO.
22
Listas Enlazadas en java ejemplo.
import javax.swing.*;
public class p1 {
 static class estudiante{
 String nombre;
float nota;
estudiante liga;
 }
public static void main (String args[]){
estudiante app=nulo,aux=nulo,aux1=nulo,aux2=nulo;
byte op=0;
 String refn;
while(op!=7){
op=Byte.parseByte(JOptionPane.showInputDialog(
 “Digite un su opcion\n”+
 “1.Crear lista\n”+
 “2.Insertar al principio\n”+
 “3.Insertar antes de una referencia\n”+
 “4.Insertar despues de una referencia\n”+
 “5.Eliminar con referencia\n”+
 “6.Imprimir\n” +
 “7.Salir”));
 switch(op){
 case 1:
 if(app==nulo){
app=new estudiante();
app.nombre=JOptionPane.showInputDialog(“Ingrese el noombre del estudiante”);
app.nota=Float.parseFloat(JOptionPane.showInputDialog(“Digite la nota”));
app.liga=nulo;
 }else{
JOptionPane.showMessageDialog(nulo, “La lista ya ha sido creada”);
}
 break;
 case 2:
 if(app!=nulo){
aux=new estudiante();
aux.nombre=JOptionPane.showInputDialog(“Ingrese el noombre del estudiante”);
aux.nota=Float.parseFloat(JOptionPane.showInputDialog(“Digite la nota”));
aux.liga=app;
app=aux;
 }else{
JOptionPane.showMessageDialog(nulo, “La lista no ha sido creada”);
}
 break;
 case 3:
 if (app!=nulo){ 
 refn=JOptionPane.showInputDialog(“ingrese en nombre del estudiantes”);
 aux=app;
 while(!aux.nombre.equals(refn)){
 aux2=aux;
 aux=aux.liga;}
 aux1=new estudiante();
 aux1.nombre=JOptionPane.showInputDialog(“ingrese en nombre del estudiantes”);
 aux1.nota=Float.parseFloat(JOptionPane.showInputDialog(“Digite la nota”));
 }else{
JOptionPane.showMessageDialog(nulo, “La lista no ha sido creada”);
} 
23
 break;
 case 4:
 if(app!=nulo){
aux=app;
refn=JOptionPane.showInputDialog(“Ingrese el nombre del estudiante”);
while(!aux.nombre.equals(refn)){
aux=aux.liga;
 }
 aux1= new estudiante();
app.nombre=JOptionPane.showInputDialog(“Ingrese el noombre del estudiante”);
app.nota=Float.parseFloat(JOptionPane.showInputDialog(“Digite la nota”));
 aux1.liga=aux.liga;
aux.liga=aux1;
 }else{
JOptionPane.showMessageDialog(nulo, “La lista no ha sido creada”);
}
 break;
 case 5:
 if(app==nulo){
aux=app;
refn=JOptionPane.showInputDialog(“Ingrese el nombre del estudiante”);
while(!aux.nombre.equals(refn)){
aux2=aux;
aux=aux.liga;
 }
 aux2.liga=aux.liga;
aux=nulo;
}
 break;
 case 6:
 aux=app;
 while(aux.liga!=nulo){
 JOptionPane.showMessageDialog(nulo, aux.nombre+” “+ aux.nota);
 aux=aux.liga;
 }
 break;
 case 7:
JOptionPane.showMessageDialog(nulo, “Gracias por utilizar el programa”);
break;
 }
 }
 } 
}
24
3.4 LISTAS DOBLEMENTE ENLADAS (Listas dobles)
Las listas doblemente enlazadas son estructuras de datos similares a las listas simples. La asignación de 
memoria es hecha al momento de la ejecución, la diferencia radica en que el enlace entre los elementos 
se hace con dos apuntadores (uno que apunta hacia el nodo anterior y otro apunta hacia el siguiente 
nodo).
 
Fuente: Propia
El puntero anterior del primer elemento debe apuntar hacia NULO. 
El puntero siguiente del último elemento debe apuntar hacia NULO. 
Para acceder a un elemento, la lista puede ser recorrida en ambos sentidos:
·	 comenzando por el inicio, el apuntador siguiente permite el desplazamiento hacia el próximo 
elemento.
·	 comenzando por el final, el apuntador anterior permite el desplazamiento hacia el elemento anterior.
El nodo típico para construir listas dobles tiene esta forma:
struct nodo {
 int dato;
 nodo *siguiente;
 nodo *anterior;
}
Para controlar la lista seconservan algunos elementos: el primer 
elemento, el último elemento y posiblemente el número de elementos. 
 Para ello, se pueden utilizar dos punteros principales:
El puntero inicio contendrá la dirección del primer elemento de la lista. 
El puntero fin contendrá la dirección del último elemento de la lista. 
 Cualquiera que sea la posición en la lista, los punteros inicio y fin apuntan siempre al primer y último 
elemento. 
3.4.1 Operaciones básicas con listas doblemente enlazadas
Las operaciones con listas doblemente enlazas son muy similares a las de listas simples, por lo tanto solo se 
indicara los pasos a seguir en cada una de ellas.
3.4.1.1 Insertar un elemento en una lista doble
Antes de cualquier otra operación sobre la lista, se inicializa el puntero inicio y el puntero fin con el valor NULO. 
Para agregar un elemento a la lista hay varias situaciones:
1. Inserción en una lista vacía
2. Inserción al inicio de la lista
3. Inserción al final de la lista
4. Inserción antes de un elemento
5. Inserción después de un elemento
25
3.4.1.1 Inserción en una lista vacía
Pasos:
·	 Asignación de memoria para el nuevo elemento
·	 Rellenar el campo de datos del nuevo elemento
·	 El puntero anterior del nuevo elemento apuntará hacia NULO (ya que la inserción es hecha en una 
lista vacía utilizamos la dirección del puntero inicio que vale NULO)
·	 El puntero siguiente del nuevo elemento apuntará hacia NULO (ya que la inserción es hecha en una 
lista vacía se utiliza la dirección del puntero fin que vale NULO)
·	 Los punteros inicio y fin apuntaran hacia el nuevo elemento
·	 El tamaño es actualizado
 
3.4.1.2 Inserción al inicio de la lista
Pasos:
·	 Asignación de memoria al nuevo elemento
·	 Rellenar el campo de datos del nuevo elemento
·	 El puntero anterior del nuevo elemento apunta hacia NULO
·	 El puntero siguiente del nuevo elemento apunta hacia el 1er elemento
·	 El puntero anterior del 1er elemento apunta hacia el nuevo elemento
·	 El puntero inicio apunta hacia el nuevo elemento
·	 El puntero fin no cambia
·	 El tamaño es incrementado
3.4.1.3 Inserción al final de la lista
Pasos:
·	 Asignación de memoria al nuevo elemento
·	 Rellenar el campo de datos del nuevo elemento
·	 El puntero siguiente del nuevo elemento apunta hacia NULO
·	 El puntero anterior del nuevo elemento apunta hacia el último elemento (es el puntero fin que 
contiene por ahora su dirección)
·	 El puntero siguiente del último elemento apuntará hacia el nuevo elemento
·	 El puntero fin apunta hacia el nuevo elemento
·	 El puntero inicio no cambia
3.4.1.4 Inserción antes de un elemento de la lista
La inserción se efectuara antes de cierta posición pasado como argumento a la función. 
La posición indicada no debe ser ni el primer ni el último elemento. En ese 
caso hay que utilizar las funciones de inserción al inicio y/o al final de la lista. 
26
Pasos:
·	 Asignación de memoria al nuevo elemento
·	 Rellenar el campo de datos del nuevo elemento
·	 Elegir una posición en la lista (la inserción se hará después de la posición elegida)
·	 El puntero siguiente del nuevo elemento apunta hacia el elemento actual.
·	 El puntero anterior del nuevo elemento apunta hacia la dirección hacia la que apunta el puntero 
anterior del elemento actual.
·	 El puntero siguiente del elemento que precede al elemento actual apuntará hacia el nuevo elemento
·	 El puntero anterior del elemento actual apunta hacia el nuevo elemento
·	 El puntero fin no cambia
·	 El puntero inicio cambia si la posición elegida es la posición 1
3.4.1.5 Inserción después de un elemento de la lista
La posición indicada no debe ser el último elemento. En ese caso hay que utilizar la función de 
inserción al final de la lista. 
Pasos:
·	 Asignación de memoria al nuevo elemento
·	 Rellenar el campo de datos del nuevo elemento
·	 Elegir una posición en la lista (la inserción se hará después de la posición elegida)
·	 El puntero siguiente del nuevo elemento apunta hacia la dirección hacia la que apunta el puntero 
siguiente del elemento actual 
·	 El puntero anterior del nuevo elemento apunta hacia el elemento actual.
·	 El puntero anterior del elemento que va después del elemento actual apuntará hacia el nuevo 
elemento.
·	 El puntero siguiente del elemento actual apunta hacia el nuevo elemento
·	 El puntero inicio no cambia
·	 El puntero fin cambia si la posición elegida es la posición del último elemento (el tamaño de la lista)
3.4.2. Eliminación de un elemento de la lista
 
En comparación a la lista enlazada simple en el que la eliminación solo puede ser hecha después que un 
elemento ha sido designado, las listas doblemente enlazadas son más flexibles gracias a los 2 punteros 
que permiten guardar la ubicación de la lista, tanto hacia atrás como hacia delante.
Para eliminar un elemento de la lista hay varias situaciones:
·	 1. Eliminación al inicio de la lista
·	 2. Eliminación al final de la lista
·	 3. Eliminación antes de un elemento
·	 4. Eliminación después de un elemento
·	 5 Eliminación de un elemento
27
En el caso de listas doblemente enlazadas la eliminación en cualquier posición no presenta ningún 
problema gracias a los punteros anterior y siguiente, que permiten conservar el enlace entre los 
elementos de la lista.
·	 Si deseamos eliminar el elemento al inicio de la lista será el elemento apuntado por inicio.
·	 Si deseamos eliminar el elemento al inicio de la lista será el elemento apuntado por final.
·	 Si deseamos eliminar cualquier elemento entonces elegimos su posición en la lista.
3.4.2.1 Eliminación en la lista doble del primer elemento
Pasos:
·	 El puntero inicio contendrá la dirección contenida por el puntero siguiente del primer elemento 
que deseamos eliminar (si este puntero vale NULO entonces actualizamos el puntero fin ya que 
estamos en el caso de una lista con un solo elemento, si no hacemos apuntar el puntero anterior 
del segundo elemento hacia NULO).
3.4.2.2 Eliminación en la lista doble del último elemento
Pasos:
·	 El puntero fin contendrá la dirección del último elemento.
·	 Hacemos apuntar al puntero siguiente del penúltimo elemento (es el elemento hacia el que 
apunta el puntero anterior del último elemento), hacia NULO.
·	 Actualizamos el puntero fin.
3.4.2.3 Eliminación en la lista doble de cualquier elemento
Pasos:
·	 El puntero sup_elemento contendrá la dirección del elemento a eliminar.
·	 El puntero siguiente del elemento que antecede al elemento a eliminar apunta hacia la dirección 
contenida en el puntero siguiente del elemento a eliminar.
·	 El puntero anterior del elemento que va después del elemento a eliminar apunta hacia la dirección 
contenida en el puntero anterior del elemento a eliminar.
28
3.5 Ejercicios con Listas enlazadas
1. Implementar una lista enlazada de datos enteros con las funciones básicas
2. Implementar una lista enlazada de datos enteros que calcule el mayor de los datos e indique la 
posición en que se encuentre.
3. Implementar una lista enlazada de datos enteros que calcule el dato mínimo y cuente la cantidad de 
veces que se repita.
4. Implementar una lista enlazada de datos enteros que sume los datos de una lista recursivamente.
5. Implementar una lista enlazada de datos enteros que sume los datos pares de una lisa recursivamente.
6. Implementar una lista enlazada de datos enteros que visualice los datos pares de la lista recursivamente.
7. Implementar una lista enlazada de datos enteros que muestre los números primos.
8. Implementar una lista enlazada de datos enteros que ordene los datos de la lista.
9. Implementar una lista enlazada de datos enteros que verifique si esta ordenada.
10. Implementar una lista enlazada de datos enteros que la invierta.
11. Implementar una lista enlazada de datos enteros que busque un dato de la lista recursivamente.
12. Implementar una lista enlazada de datos enteros que elimine un dato recursivamente.
13. Implementar una lista enlazada de datos enteros que duplique los datos de la lista y los almacene 
en otra lista4. Recursividad
4.1 Concepto de recursividad.
• La recursividad es una técnica de programación muy potente que puede ser utilizada en lugar de la 
iteración.
• Permite diseñar algoritmos recursivos que dan soluciones elegantes y simples, y generalmente bien 
estructuradas y modulares, a problemas de gran complejidad.
Es una técnica que nos permite que un algoritmo se invoque a sí mismo para resolver una versión más 
pequeña del problema original que le fue encomendado
public void f_rec(...)
…
{
…
f_rec(…)
…
}
El caso es que las definiciones recursivas aparecen con frecuencia en matemáticas, e incluso en la vida 
real. Un ejemplo: basta con apuntar una cámara al monitor que muestra la imagen que muestra esa 
cámara. El efecto es verdaderamente curioso, en especial cuando se mueve la cámara alrededor del 
monitor.
En matemáticas, tenemos múltiples definiciones recursivas:
- Números naturales:
 (1) 1 es número natural.
 (2) el siguiente número de un número natural es un número natural
29
- El factorial: n!, de un número natural (incluido el 0):
 (1) si n = 0 entonces: 0! = 1
 (2) si n > 0 entonces: n! = n · (n-1)!
Asimismo, puede definirse un programa en términos recursivos, como una serie de pasos básicos, o 
paso base (también conocido como condición de parada), y un paso recursivo, donde vuelve a llamarse 
al programa. En una computadora, esta serie de pasos recursivos debe ser finita, terminando con un 
paso base. Es decir, a cada paso recursivo se reduce el número de pasos que hay que dar para terminar, 
llegando un momento en el que no se verifica la condición de paso a la recursividad. Ni el paso base ni 
el paso recursivo son necesariamente únicos.
Por otra parte, la recursividad también puede ser indirecta, si tenemos un procedimiento P que llama a 
otro Q y éste a su vez llama a P. También en estos casos debe haber una condición de parada.
4.2 Ejemplos 
a. Factorial.
En matemáticas es frecuente definir un concepto en función del proceso usado para generarlo. Por 
ejemplo, una descripción matemática de n! es:
n! = 1 si n = 0
n⋅(n-1) ⋅....⋅1 si n > 0
También se puede definir de forma más sencilla:
n! = 1 si n = 0
n⋅(n-1)! si n > 0
Esta segunda definición es recursiva, puesto que se expresa un método factorial en términos de sí 
mismo. A partir de esta definición, es fácil obtener un algoritmo recursivo para calcular el factorial de 
un número natural n.
public static int factorialR(int n) {
int fact;
if (n==0)
 fact=1;
else
fact=n*factorial(n-1);
return fact ;
}
De esto se pueden sacar varias conclusiones:
1. El método se invoca a sí mismo (esto es lo que lo convierte en recursivo).
2. Cada llamada recursiva se hace con un parámetro de menor valor que el de la anterior llamada. 
Así, cada vez se está invocando a otro problema idéntico pero de menor tamaño.
3. Existe un caso degenerado en el que se actúa de forma diferente, esto es, ya no se utiliza la 
recursividad. Lo importante es que la forma en la que el tamaño del problema disminuye asegura 
que se llegará a este caso degenerado o caso base. Esto es necesario, porque de lo contrario se 
estaría ejecutando indefinidamente. 
30
• Para determinar si un método recursivo está bien diseñado se utiliza el método de las tres preguntas:
1. La pregunta Caso-Base: Existe una salida no recursiva o caso base del y éste funciona correctamente 
para él?
2. La pregunta Invocar más pequeño Cada llamada recursiva se refiere a un caso más pequeño del 
problema original?
3. La pregunta Caso-General. Suponiendo que la(s) llamada(s) recursiva(s) funciona(n) correctamente, 
así como el caso base, funciona correctamente todo el método?.
Si por ejemplo, le aplicamos esto al método factorial(n), podemos comprobar cómo las respuestas a las 
3 preguntas son afirmativas, con lo que podemos deducir que el algoritmo recursivo está bien diseñado.
b. Multiplicación de conejos.
Supongamos que partimos de una pareja de conejos recién nacidos, y queremos calcular cuántas parejas 
de conejos forman la familia al cabo de n meses si:
1. Los conejos nunca mueren.
2. Un conejo puede reproducirse al comienzo del tercer mes de vida.
3. Los conejos siempre nacen en parejas macho-hembra. Al comienzo de cada mes, cada pareja macho-
hembra, sexualmente madura, se reproduce en exactamente un par de conejos macho-hembra. Para 
una n pequeña, por ejemplo 6, la solución se puede obtener fácilmente a mano:
Mes 1: 1 pareja, la inicial.
Mes 2: 1 pareja, ya que todavía no es sexualmente madura.
Mes 3: 2 parejas; la original y una pareja de hijos suyos.
Mes 4: 3 parejas; la original, una pareja de hijos suyos nacidos ahora y la pareja de hijos suyos nacidos 
en el mes anterior.
Mes 5: 5 parejas; la original, una pareja de hijos suyos nacidos ahora, las dos parejas nacidas en los 
meses 3 y 4, y una pareja de hijos de la pareja nacida en el mes 3.
Mes 6: 8 parejas; las 5 del mes anterior, una pareja de hijos de la original, una pareja de hijos de la 
nacida en el mes 3 y una pareja de hijos nacida en el mes 4.
Si deseamos saber el número de parejas al cabo de n meses, para un n cualquiera, podemos construir 
un algoritmo recursivo fácilmente a partir de la siguiente relación:
Parejas(n) = 1 si n <= 2
Parejas(n-1)+Parejas(n-2) si n > 2
En esta relación Parejas(n-1) son las parejas vivas en el mes n-1, y Parejas(n-2) son las parejas que nacen 
en el mes n a partir de las que había en el mes n-2.
La serie de números Parejas (1), Parejas (2), Parejas (3),... es conocida como la Serie de Fibonacci, la cual 
modela muchos fenómenos naturales.
31
La función recursiva quedaría:
public static int parejas(int n){
 int par;
if (n<=2)
 par=1;
else
 par=parejas(n-1)+parejas(n-2);
return par;
}
c. Recursión indirecta.
A continuación se expone un ejemplo de programa que utiliza recursión indirecta, y nos dice si un 
número es par o impar. Al igual que el programa anterior, hay otro método mucho más sencillo de 
determinar si un número es par o impar, basta con determinar el resto de la división entre dos. Por 
ejemplo: si hacemos par(2) devuelve (cierto). Si hacemos impar(4) devuelve (falso).
 public static boolean par(int n)
{
 if (n == 0) return true;
 return impar(n-1); 
 }
public static boolean impar(int n)
{
 if (n == 0) return false;
 return par(n-1); 
}
Ejemplo: Si hacemos la llamada impar(3) hace las siguientes llamadas:
par(2)
impar(1)
par(0) . devuelve 1 (cierto)
Por lo tanto 3 es un número impar.
Qué pasa si se hace una llamada recursiva que no termina?
Cada llamada recursiva almacena los parámetros que se pasaron al procedimiento, y otras variables 
necesarias para el correcto funcionamiento del programa. Por tanto si se produce una llamada recursiva 
infinita, esto es, que no termina nunca, llega un momento en el que no quedará memoria para almacenar 
más datos, y en ese momento se abortará la ejecución del programa. Para probar esto se puede intentar 
hacer esta llamada en el programa factorial definido anteriormente: 
factorialR(-1);
Por supuesto no hay que pasar parámetros a una función que estén fuera de su dominio, pues el 
factorialR está definido solamente para números naturales, pero es un ejemplo claro.
32
4.3 Uso de la recursividad.
Se evidenció que la recursión es una técnica potente de programación para resolver, mediante 
soluciones simples y claras, problemas de incluso gran complejidad. Sin embargo, la recursión también 
tiene algunas desventajas desde el punto de vista de la eficiencia. Muchas veces un algoritmo iterativo 
es más eficiente que su correspondiente recursivo. Existen dos factores que contribuyen a ello
a. La sobrecarga asociada con las llamadas a los métodos.
• Este factor es propio de los métodos en general, aunque es mayor con la recursividad, ya que una 
simple llamada inicial a un método puede generar un gran número de llamadas recursivas.
• Aunque el uso de la recursión, como herramienta de modularidad, puede clarificar programas 
complejos que compensaría la sobrecarga adicional, no debemos usarla recursividad por el gusto de 
usarla. Por ejemplo, el método factorialR presentada antes no debería usarse en la práctica.
Se puede fácilmente escribir una función iterativa Factorial tan clara como la recursiva y sin la sobrecarga 
de ésta.
public int factorial(int n){
int cont, fact;
fact=1;
for (cont=2; cont<=n; cont++)
fact=fact*cont;
return fact;
}
Podemos encontrar algunas diferencias interesantes entre FactorialR y FactorialI, que se presentarán 
por lo general entre métodos recursivos e iterativos.
• El método iterativo utiliza una construcción cíclica (for, while,…) para controlar la ejecución, mientras 
que la solución recursiva utiliza una estructura de selección.
• La versión iterativa necesita un par de variables locales, mientras que la versión recursiva sólo una.
b. La ineficiencia inherente de algunos métodos recursivos.
Esta ineficiencia es debida al método empleado para resolver el problema concreto que se esté 
abordando.
Por ejemplo, en el método presentado para resolver el problema de la “multiplicación de conejos”, 
apreciamos un gran inconveniente: los mismos valores son calculados varias veces. Por ejemplo, para 
calcular Parejas R(7), tenemos que calcular ParejasR(3) cinco veces. Mientras más grande sea n, mayor 
ineficiencia.
Se puede construir una solución iterativa basada en la misma relación, que actúa hacia delante en lugar 
de hacia atrás, y calcula cada valor sólo una vez.
33
public int parejasII(int n){
int R, R1, R2, i;
R1=1;
R2=1;
R=1;
for (i=3; i<=n; i++){
R=R1+R2;
R2=R1;
R1=R;
}
return R;
}
El hecho de que la recursividad tenga estas dos desventajas, no quiere decir que sea una mala técnica y 
que no se deba utilizar, sino que hay que usarla cuando realmente sea necesaria:
El verdadero valor de la recursividad es como herramienta para resolver problemas para los que no hay 
soluciones iterativas simples.
¿Cuándo utilizar la recursión?
No se debe utilizar cuando la solución iterativa sea clara a simple vista. Sin embargo, en otros casos, 
obtener una solución iterativa es mucho más complicado que una solución recursiva, y es entonces 
cuando se puede plantear la duda de si merece la pena transformar la solución recursiva en otra 
iterativa. En realidad la recursión se basa en almacenar en una pila los valores de las variables locales 
que haya para un procedimiento en cada llamada recursiva. Esto reduce la claridad del programa. Aun 
así, hay que considerar que el compilador transformará la solución recursiva en una iterativa, utilizando 
una pila, para cuando compile al código de la computadora.
Por otra parte, casi todos los esquemas de vuelta atrás y divide y vencerás son recursivos, pues de 
alguna manera parece mucho más natural una solución recursiva.
En general mucho más sencillo escribir un programa recursivo que su equivalente iterativo.
34
 4.4 Ejercicios
1. Escriba una definición recursiva de una función que tiene un parámetro n de tipo entero y que 
devuelve el n-ésimo número de Fibonacci. Los números de Fibonacci se definen de la siguiente manera:
F0 = 1
F1 = 1
Fi+2 = Fi + Fi+1
2. La forma para calcular cuantas maneras diferentes tengo para elegir r cosas distintas de un conjunto 
de n cosas es:
C(n,r) = n! (r!*(n-r)!)
Donde la función factorial se define como
n! = n *(n-1)*(n-2)*…*2*1
Descubra una versión recursiva de la fórmula anterior y escriba una función recursiva que calcule el 
valor de dicha fórmula.
3. Escriba una función recursiva que ordene de menor a mayor un arreglo de enteros basándose en la 
siguiente idea: coloque el elemento más pequeño en la primera ubicación, y luego ordene el resto del 
arreglo con una llamada recursiva.
4. Escribir una función recursiva que devuelva la suma de los primeros N enteros
5. Escribir un programa que encuentre la suma de los enteros positivos pares desde N hasta 2. Chequear 
que si N es impar se imprima un mensaje de error.
6. Escribir un programa que calcule el máximo común divisor (MCD) de dos enteros positivos. Si M >= N 
una función recursiva para MCD es
MCD = M si N =0
MCD = MCD (N, M mod N) si N <> 0
El programa le debe permitir al usuario ingresar los valores para M y N desde la consola. Una función 
recursiva es entonces llamada para calcular el MCD. El programa entonces imprime el valor para el 
MCD. Si el usuario ingresa un valor para M que es < que N el programa es responsable de switchear los 
valores.
7. Programe un método recursivo que transforme un número entero positivo a notación binaria.
8. Programe un método recursivo que transforme un número expresado en notación binaria a un 
número entero.
9. Programe un método recursivo que calcule la suma de un arreglo de números enteros.
10. Programe un método recursivo que invierta los números de un arreglo de enteros.
11. Cuál es el resultado de esta función para distintos valores de X?
Static int f(int x)
{
 if (x >100)
 {
 return (x-10);
}
else
{
 return(f(f(x+11)));
}
}
12. Implemente una función recursiva que nos diga si una cadena es palíndromo.
35
5. Árboles
5.1 Definición
Un árbol es una estructura no lineal en la que cada nodo puede apuntar a uno o varios nodos.
También se suele dar una definición recursiva: un árbol es una estructura en compuesta por un dato y 
varios árboles.
Esto son definiciones simples. Pero las características que implican no lo son tanto.
 
Fuente: Propia
Definiremos varios conceptos. En relación con otros nodos:
·	 Nodo hijo: cualquiera de los nodos apuntados por uno de los nodos del árbol. En el ejemplo, ‘L’ 
y ‘M’ son hijos de ‘G’.
·	 Nodo padre: nodo que contiene un puntero al nodo actual. En el ejemplo, el nodo ‘A’ es padre 
de ‘B’, ‘C’ y ‘D’.
Los árboles con los que trabajaremos tienen otra característica importante: cada nodo sólo puede ser 
apuntado por otro nodo, es decir, cada nodo sólo tendrá un padre. Esto hace que estos árboles estén 
fuertemente jerarquizados, y es lo que en realidad les da la apariencia de árboles.
En cuanto a la posición dentro del árbol:
·	 Nodo raíz: nodo que no tiene padre. Este es el nodo que usaremos para referirnos al árbol. En el 
ejemplo, ese nodo es el ‘A’.
·	 Nodo hoja: nodo que no tiene hijos. En el ejemplo hay varios: ‘F’, ‘H’, ‘I’, ‘K’, ‘L’, ‘M’, ‘N’ y ‘O’.
·	 Nodo rama: aunque esta definición apenas la usaremos, estos son los nodos que no pertenecen 
a ninguna de las dos categorías anteriores. En el ejemplo: ‘B’, ‘C’, ‘D’, ‘E’, ‘G’ y ‘J’.
Otra característica que normalmente tendrán nuestros árboles es que todos los nodos contengan el 
mismo número de punteros, es decir, usaremos la misma estructura para todos los nodos del árbol. Esto 
hace que la estructura sea más sencilla, y por lo tanto también los programas para trabajar con ellos.
Tampoco es necesario que todos los nodos hijos de un nodo concreto existan. Es decir, que pueden 
usarse todos, algunos o ninguno de los punteros de cada nodo.
36
Un árbol en el que en cada nodo o bien todos o ninguno de los hijos existe, se llama árbol completo.
En una cosa, los árboles se parecen al resto de las estructuras que hemos visto: dado un nodo cualquiera 
de la estructura, podemos considerarlo como una estructura independiente. Es decir, un nodo cualquiera 
puede ser considerado como la raíz de un árbol completo.
Existen otros conceptos que definen las características del árbol, en relación a su tamaño:
·	 Orden: es el número potencial de hijos que puede tener cada elemento de árbol. De este modo, 
diremos que un árbol en el que cada nodo puede apuntar a otros dos es de orden dos, si puede 
apuntar a tres será de orden tres, etc.
·	 Grado: el número de hijos que tiene el elemento con más hijos dentro del árbol. En el árbol del 
ejemplo, el grado es tres, ya que tanto ‘A’ como ‘D’ tienen tres hijos, y no existen elementos con 
más de tres hijos.
·	 Nivel: se define para cada elemento del árbol como la distancia a la raíz, medida en nodos. El 
nivel de la raíz es cero y el de sus hijos uno. Así sucesivamente. En el ejemplo, el nodo ‘D’ tiene 
nivel 1, el nodo ‘G’tiene nivel 2, y el nodo ‘N’, nivel 3.
·	 Altura: la altura de un árbol se define como el nivel del nodo de mayor nivel. Como cada nodo 
de un árbol puede considerarse a su vez como la raíz de un árbol, también podemos hablar de 
altura de ramas. El árbol del ejemplo tiene altura 3, la rama ‹B› tiene altura 2, la rama ‹G› tiene 
altura 1, la ‹H› cero, etc.
Los árboles de orden dos son bastante especiales, de hecho les dedicaremos varios capítulos. Estos 
árboles se conocen también como árboles binarios.
Frecuentemente, aunque tampoco es estrictamente necesario, para hacer más fácil moverse a través 
del árbol, agregaremos un puntero a cada nodo que apunte al nodo padre. De este modo podremos 
avanzar en dirección a la raíz, y no sólo hacia las hojas.
Es importante conservar siempre el nodo raíz ya que es el nodo a partir del cual se desarrolla el árbol, 
si perdemos este nodo, perderemos el acceso a todo el árbol.
El nodo típico de un árbol difiere de los nodos que hemos visto hasta ahora para listas, aunque sólo en 
el número de nodos. Veamos un ejemplo de nodo para crear árboles de orden tres:
struct nodo {
 int dato;
 struct nodo *rama1;
 struct nodo *rama2;
 struct nodo *rama3;
}
5.2 Operaciones básicas con árboles
Salvo que trabajemos con árboles especiales, como los que veremos más adelante, las inserciones serán 
siempre en punteros de nodos hoja o en punteros libres de nodos rama. Con estas estructuras no es tan 
fácil generalizar, ya que existen muchas variedades de árboles.
37
De nuevo tenemos casi el mismo repertorio de operaciones de las que disponíamos con las listas:
·	 Agregar o insertar elementos.
·	 Buscar o localizar elementos.
·	 Borrar elementos.
·	 Moverse a través del árbol.
·	 Recorrer el árbol completo.
Los algoritmos de inserción y borrado dependen en gran medida del tipo de árbol que estemos 
implementando, de modo que por ahora los pasaremos por alto y nos centraremos más en el modo de 
recorrer árboles.
5.3 Recorridos por árboles
El modo evidente de moverse a través de las ramas de un árbol es siguiendo los punteros, del mismo 
modo en que nos movíamos a través de las listas.
Esos recorridos dependen en gran medida del tipo y propósito del árbol, pero hay ciertos recorridos que 
usaremos frecuentemente. Se trata de aquellos recorridos que incluyen todo el árbol.
Hay tres formas de recorrer un árbol completo, y las tres se suelen implementar mediante recursividad. 
En los tres casos se sigue siempre a partir de cada nodo todas las ramas una por una.
Supongamos que tenemos un árbol de orden tres, y queremos recorrerlo por completo.
Partiremos del nodo raíz:
RecorrerArbol(raiz);
La función RecorrerArbol, aplicando recursividad, será tan sencilla como invocar de nuevo a la función 
RecorrerArbol para cada una de las ramas:
void RecorrerArbol(Arbol a) {
 if(a == NULO) return;
 RecorrerArbol(a.rama[0]);
 RecorrerArbol(a.rama[1]);
 RecorrerArbol(a.rama[2]);
}
Lo que diferencia los distintos métodos de recorrer el árbol no es el sistema de hacerlo, sino el momento 
que elegimos para procesar el valor de cada nodo con relación a los recorridos de cada una de las ramas.
Los tres tipos son: Pre-orden, In-orden y Post-orden.
5.3.1 Pre-orden
En este tipo de recorrido, el valor del nodo se procesa antes de recorrer las ramas:
void PreOrden(Arbol a) {
 if(a == NULO) return;
 Procesar(dato);
 RecorrerArbol(a.rama[0]);
 RecorrerArbol(a.rama[1]);
 RecorrerArbol(a.rama[2]);
}
Si seguimos el árbol del ejemplo en pre-orden, y el proceso de los datos es sencillamente mostrarlos por 
pantalla, obtendremos algo así:
A B E K F C G L M D H I J N O
38
5.3.2 In-orden
En este tipo de recorrido, el valor del nodo se procesa después de recorrer la primera rama y antes 
de recorrer la última. Esto tiene más sentido en el caso de árboles binarios, y también cuando existen 
ORDEN-1 datos, en cuyo caso procesaremos cada dato entre el recorrido de cada dos ramas (este es el 
caso de los árboles-b):
void InOrden(Arbol a) {
 if(a == NULO) return;
 RecorrerArbol(a.rama[0]);
 Procesar(dato);
 RecorrerArbol(a.rama[1]);
 RecorrerArbol(a.rama[2]);
}
Si seguimos el árbol del ejemplo en in-orden, y el proceso de los datos es sencillamente mostrarlos por 
pantalla, obtendremos algo así:
K E B F A L G M C H D I N J O
5.3.3 Post-orden
En este tipo de recorrido, el valor del nodo se procesa después de recorrer todas las ramas:
void PostOrden(Arbol a) {
 if(a == NULO) return;
 RecorrerArbol(a.rama[0]);
 RecorrerArbol(a.rama[1]);
 RecorrerArbol(a.rama[2]);
 Procesar(dato);
}
Si seguimos el árbol del ejemplo en post-orden, y el proceso de los datos es sencillamente mostrarlos 
por pantalla, obtendremos algo así:
K E F B L M G C H I N O J D A
5.4 Eliminar nodos en un árbol
El proceso general es muy sencillo en este caso, pero con una importante limitación, sólo podemos 
borrar nodos hoja:
El proceso sería el siguiente:
1. Buscar el nodo padre del que queremos eliminar.
2. Buscar el puntero del nodo padre que apunta al nodo que queremos borrar.
3. Liberar el nodo.
4. padre.nodo[i] = NULO;
39
Cuando el nodo a borrar no sea un nodo hoja, diremos que hacemos una “poda”, y en ese caso 
eliminaremos el árbol cuya raíz es el nodo a borrar. Se trata de un procedimiento recursivo, aplicamos 
el recorrido PostOrden, y el proceso será borrar el nodo.
El procedimiento es similar al de borrado de un nodo:
1. Buscar el nodo padre del que queremos eliminar.
2. Buscar el puntero del nodo padre que apunta al nodo que queremos borrar.
3. Podar el árbol cuyo padre es nodo.
4. padre.nodo[i] = NULO;
En el árbol del ejemplo, para podar la rama ‘B’, recorreremos el subárbol ‘B’ en postorden, eliminando 
cada nodo cuando se procese, de este modo no perdemos los punteros a las ramas apuntadas por cada 
nodo, ya que esas ramas se borrarán antes de eliminar el nodo.
De modo que el orden en que se borrarán los nodos será:
K E F y B
5.5 Árboles ordenados
A partir del siguiente capítulo sólo hablaremos de árboles ordenados, ya que son los que tienen más 
interés desde el punto de vista de TAD, y los que tienen más aplicaciones genéricas.
Un árbol ordenado, en general, es aquel a partir del cual se puede obtener una secuencia ordenada 
siguiendo uno de los recorridos posibles del árbol: inorden, preorden o postorden.
En estos árboles es importante que la secuencia se mantenga ordenada aunque se añadan o se eliminen 
nodos.
Existen varios tipos de árboles ordenados, que veremos a continuación:
·	 Árboles binarios de búsqueda (ABB): son árboles de orden 2 que mantienen una secuencia 
ordenada si se recorren en inorden.
·	 Árboles AVL: son árboles binarios de búsqueda equilibrados, es decir, los niveles de cada rama 
para cualquier nodo no difieren en más de 1.
·	 Árboles perfectamente equilibrados: son árboles binarios de búsqueda en los que el número de 
nodos de cada rama para cualquier nodo no difieren en más de 1. Son por lo tanto árboles AVL 
también.
·	 Árboles 2-3: son árboles de orden 3, que contienen dos claves en cada nodo y que están también 
equilibrados. También generan secuencias ordenadas al recorrerlos en inorden.
·	 Árboles-B: caso general de árboles 2-3, que para un orden M, contienen M-1 claves.
40
5.6 Árboles binarios de búsqueda (ABB)
5.6.1 Definición
Se trata de árboles de orden 2 en los que se cumple que para cada nodo, el valor de la clave de la raíz del 
subárbol izquierdo es menor que el valor de la clave del nodo y que el valor de la clave raíz del subárbol 
derecho es mayor que el valor de la clave del nodo.
 
Árbol binario de búsqueda
Fuente: Propia
5.6.2 Operaciones en ABB
El repertorio de operaciones que se pueden realizar sobre un ABB es parecido al que realizábamos 
sobre otras estructuras de datos, más alguna otra propia de árboles:
·	 Buscar un elemento.
·	 Insertar un elemento.
·	 Borrar un elemento.
·	 Movimientos a través del árbol:
o Izquierda.
o Derecha.
o Raíz.
·	 Información:
o Comprobar siun árbol está vacío.
o Calcular el número de nodos.
o Comprobar si el nodo es hoja.
o Calcular la altura de un nodo.
o Calcular la altura de un árbol.
41
5.6.3 Buscar un elemento
Partiendo siempre del nodo raíz, el modo de buscar un elemento se define de forma recursiva.
·	 Si el árbol está vacío, terminamos la búsqueda: el elemento no está en el árbol.
·	 Si el valor del nodo raíz es igual que el del elemento que buscamos, terminamos la búsqueda 
con éxito.
·	 Si el valor del nodo raíz es mayor que el elemento que buscamos, continuaremos la búsqueda 
en el árbol izquierdo.
·	 Si el valor del nodo raíz es menor que el elemento que buscamos, continuaremos la búsqueda 
en el árbol derecho.
El valor de retorno de una función de búsqueda en un ABB puede ser un puntero al nodo encontrado, o 
NULO, si no se ha encontrado.
5.6.4 Insertar un elemento
Para insertar un elemento nos basamos en el algoritmo de búsqueda. Si el elemento está en el árbol no 
lo insertaremos. Si no lo está, lo insertaremos a continuación del último nodo visitado.
Necesitamos un puntero auxiliar para conservar una referencia al padre del nodo raíz actual. El valor 
inicial para ese puntero es NULO.
·	 Padre = NULO
·	 nodo = Raíz
·	 Bucle: mientras actual no sea un árbol vacío o hasta que se encuentre el elemento.
o Si el valor del nodo raíz es mayor que el elemento que buscamos, continuaremos la 
búsqueda en el árbol izquierdo: Padre=nodo, nodo=nodo.izquierdo.
o Si el valor del nodo raíz es menor que el elemento que buscamos, continuaremos la 
búsqueda en el árbol derecho: Padre=nodo, nodo=nodo.derecho.
·	 Si nodo no es NULO, el elemento está en el árbol, por lo tanto salimos.
·	 Si Padre es NULO, el árbol estaba vacío, por lo tanto, el nuevo árbol sólo contendrá el nuevo 
elemento, que será la raíz del árbol.
·	 Si el elemento es menor que el Padre, entonces insertamos el nuevo elemento como un nuevo 
árbol izquierdo de Padre.
·	 Si el elemento es mayor que el Padre, entonces insertamos el nuevo elemento como un nuevo 
árbol derecho de Padre.
Este modo de actuar asegura que el árbol sigue siendo ABB.
42
5.6.5 Borrar un elemento
Para borrar un elemento también nos basamos en el algoritmo de búsqueda. Si el elemento no está en 
el árbol no lo podremos borrar. Si está, hay dos casos posibles:
1. Se trata de un nodo hoja: en ese caso lo borraremos directamente.
2. Se trata de un nodo rama: en ese caso no podemos eliminarlo, puesto que perderíamos todos 
los elementos del árbol de que el nodo actual es padre. En su lugar buscamos el nodo más a la 
izquierda del subárbol derecho, o el más a la derecha del subárbol izquierdo e intercambiamos 
sus valores. A continuación eliminamos el nodo hoja.
Necesitamos un puntero auxiliar para conservar una referencia al padre del nodo raíz actual. El valor 
inicial para ese puntero es NULO.
·	 Padre = NULO
·	 Si el árbol está vacío: el elemento no está en el árbol, por lo tanto salimos sin eliminar ningún 
elemento.
·	 (1) Si el valor del nodo raíz es igual que el del elemento que buscamos, estamos ante uno de los 
siguientes casos:
o El nodo raíz es un nodo hoja:
§	 Si ‘Padre’ es NULO, el nodo raíz es el único del árbol, por lo tanto el puntero al 
árbol debe ser NULO.
§	 Si raíz es la rama derecha de ‘Padre’, hacemos que esa rama apunte a NULO.
§	 Si raíz es la rama izquierda de ‘Padre’, hacemos que esa rama apunte a NULO.
§	 Eliminamos el nodo, y salimos.
o El nodo no es un nodo hoja:
§	 Buscamos el ‘nodo’ más a la izquierda del árbol derecho de raíz o el más a la 
derecha del árbol izquierdo. Hay que tener en cuenta que puede que sólo exista 
uno de esos árboles. Al mismo tiempo, actualizamos ‘Padre’ para que apunte al 
padre de ‘nodo’.
§	 Intercambiamos los elementos de los nodos raíz y ‘nodo’.
§	 Borramos el nodo ‘nodo’. Esto significa volver a (1), ya que puede suceder que 
‘nodo’ no sea un nodo hoja. (Ver ejemplo 3)
·	 Si el valor del nodo raíz es mayor que el elemento que buscamos, continuaremos la búsqueda 
en el árbol izquierdo.
·	 Si el valor del nodo raíz es menor que el elemento que buscamos, continuaremos la búsqueda 
en el árbol derecho.
43
Ejemplo 1: Borrar un nodo hoja
En el árbol de ejemplo, borrar el nodo 10.
1. Localizamos el nodo a borrar, al tiempo que mantenemos un puntero a ‘Padre’.
2. Hacemos que el puntero de ‘Padre’ que apuntaba a ‘nodo’, ahora apunte a NULO.
3. Borramos el ‘nodo’.
 
Fuente: Propia
Borrar un nodo hoja
Ejemplo 2: Borrar un nodo rama con intercambio de un nodo hoja.
En el árbol de ejemplo, borrar el nodo 4.
1. Localizamos el nodo a borrar (‘raíz’).
2. Buscamos el nodo más a la derecha del árbol izquierdo de ‘raíz’, en este caso el 3, al tiempo que 
mantenemos un puntero a ‘Padre’ a ‘nodo’.
3. Intercambiamos los elementos 3 y 4.
4. Hacemos que el puntero de ‘Padre’ que apuntaba a ‘nodo’, ahora apunte a NULO.
5. Borramos el ‘nodo’.
 
Fuente: Propia
44
Ejemplo 3: Borrar un nodo rama con intercambio de un nodo rama.
Para este ejemplo usaremos otro árbol. En éste borraremos el elemento 6.
 
Fuente: Propia
1. Localizamos el nodo a borrar (‘raíz’).
2. Buscamos el nodo más a la izquierda del árbol derecho de ‘raíz’, en este caso el 12, ya que el 
árbol derecho no tiene nodos a su izquierda, si optamos por la rama izquierda, estaremos en un 
caso análogo. Al mismo tiempo que mantenemos un puntero a ‘Padre’ a ‘nodo’.
3. Intercambiamos los elementos 6 y 12.
4. Ahora tenemos que repetir el bucle para el nodo 6 de nuevo, ya que no podemos eliminarlo.
 
Fuente: Propia
5. Localizamos de nuevo el nodo a borrar (‘raíz’).
6. Buscamos el nodo más a la izquierda del árbol derecho de ‘raíz’, en este caso el 16, al mismo 
tiempo que mantenemos un puntero a ‘Padre’ a ‘nodo’.
7. Intercambiamos los elementos 6 y 16.
8. Hacemos que el puntero de ‘Padre’ que apuntaba a ‘nodo’, ahora apunte a NULO.
9. Borramos el ‘nodo’.
 
Fuente: Propia
Este modo de actuar asegura que el árbol sigue siendo ABB
45
Árboles ABB en Java.
import javax.swing.*;
public class NewClass {
 static class nodo{
 int dato;
 nodo ligad;
 nodo ligai;
 }
 public static void Insercion(int datoi,nodo aux) {
 nodo aux1;
 if(aux.dato>datoi){
 if(aux.ligai==nulo){
 aux1 =new nodo();
 aux1.dato= datoi;
 aux1.ligai=nulo;
 aux1.ligad=nulo;
 aux.ligai=aux1;
 JOptionPane.showMessageDialog(nulo,”el dato ha sido insertado”);
 }else{
 aux=aux.ligai;
 Insercion(datoi, aux);
 }
 }else{
 if(aux.ligad==nulo){
 aux1 =new nodo();
 aux1.dato= datoi;
 aux1.ligai=nulo;
 aux1.ligad=nulo;
 aux.ligad=aux1;
 JOptionPane.showMessageDialog(nulo,”el dato ha sido insertado”);
 }else{
 aux=aux.ligad;
 Insercion(datoi,aux);
 }
 }
 }
public static void Busqueda(int datoi,nodo aux) {
 if(aux.dato==datoi){
 JOptionPane.showMessageDialog(nulo,”el numero existe”);
 }else{
 if(datoi<aux.dato){
 if(aux.ligai==nulo){
 JOptionPane.showMessageDialog(nulo, “el numero no existe”);
 }else{
 Busqueda(datoi,aux.ligai);
 }
 }else{
 if(aux.ligad==nulo){
 JOptionPane.showMessageDialog(nulo, “el numero no existe”);
 }else{
 Busqueda(datoi,aux.ligad);
 }
 }
 }
}
public static void Eliminar(int datoi, nodo aux) {
46
 nodo aux1,aux2;
 aux1=aux.ligai;
 aux2=aux.ligad;
 if(aux1.dato!=datoi && aux2.dato!=datoi){
 if(datoi<aux.dato){
 if(aux1==nulo){
 JOptionPane.showMessageDialog(nulo, “el numero no existe”);
 }else{
 Eliminar(datoi,aux1);
 }
 }else{
 if(aux2==nulo){
 JOptionPane.showMessageDialog(nulo,