INTRODUCCIÓN
En esta trabajo repasaremos la estructura
de Arboles binarios, Pilas y Colas, sus definiciones, forma gráfica, métodos,
casos de uso práctico en informática y los códigos en lenguajes de JAVA y
PYTHON.
ÁRBOL
BINARIO.
En
ciencias de la computación, un árbol binario es una estructura de datos en la
cual cada nodo puede tener un hijo izquierdo y un hijo derecho. No pueden tener
más de dos hijos (de ahí el nombre "binario").
Además un árbol cuenta con las siguientes características:
tamaño (número de nodos), altura (desde el primer nodo hijo hasta el último
nodo hijo del árbol).
A
continuación se muestra de forma gráfica un árbol binario:
Recorrido
de un árbol binario
Existen
tres formas de recorrer un árbol binario.
- Preorden: (raíz,
izquierdo, derecho). Para recorrer un árbol binario no vacío en preorden,
hay que realizar las siguientes operaciones recursivamente en cada nodo,
comenzando con el nodo de raíz:
1.
Visite
la raíz
2.
Atraviese el sub-árbol
izquierdo
3.
Atraviese el sub-árbol
derecho
- Inorden:
(izquierdo, raíz,
derecho). Para recorrer un árbol binario no vacío en inorden (simétrico),
hay que realizar las siguientes operaciones recursivamente en cada nodo:
1.
Atraviese el sub-árbol
izquierdo
2.
Visite
la raíz
3.
Atraviese el sub-árbol
derecho
- Postorden:
(izquierdo, derecho, raíz). Para
recorrer un árbol binario no vacío en postorden, hay que realizar las
siguientes operaciones recursivamente en cada nodo:
1.
Atraviese el sub-árbol
izquierdo
2.
Atraviese el sub-árbol
derecho
3.
Visite
la raíz
COLAS
Una cola es una estructura de datos, caracterizada por ser una
secuencia de elementos en la que la operación de inserción (push) se realiza
por un extremo y la operación de extracción (pop) por el otro. También se le
llama estructura FIFO
(del inglés First In First Out), debido a que el primer elemento en entrar será
también el primero en salir.
A
continuación se muestra de forma gráfica una cola:
Dentro de las operaciones que se pueden
ejecutar con una cola están las siguientes:
- Crear: se crea la cola vacía.
- Encolar (añadir, entrar, insertar): se añade un elemento a la cola. Se añade al final de esta.
- Desencolar (sacar, salir, eliminar): se elimina el elemento frontal de la cola, es decir, el primer elemento que entró.
- Frente (consultar, front): se devuelve el elemento frontal de la cola, es decir, el primer elemento que entró.
PILAS
Una pila (stack en inglés) es una lista
ordenada o estructura de datos en la que el modo de acceso a sus elementos es
de tipo LIFO (del inglés Last In First Out, último en entrar, primero en salir)
que permite almacenar y recuperar datos.
A
continuación se muestra de forma gráfica una pila:
Dentro de las operaciones que se pueden
ejecutar con una cola están las siguientes:
- Crear: se crea la pila vacía. (constructor)
- Tamaño: regresa el número de elementos de la pila (size).
- Apilar: se añade un elemento a la pila (push).
- Desapilar: se elimina el elemento frontal de la pila.(pop)
- Cima: devuelve el elemento que está en la cima de la pila (top).
- Vacía: devuelve cierto si la pila está sin elementos o falso en caso de que contenga uno (empty).
Cuál
es el uso práctico que se le dan a estas estructuras de datos ¿?
Árbol
Binario
- Las tablas de enrutamiento que usan los routers para calcular la ruta más corta a la hora de transmitir información de un punto a otro.
Colas
- Personas comprando en un supermercado,
- Esperando para entrar a ver un partido de fútbol,
- Esperando en el cine para ver una película, una pequeña peluquería, etc.
- La idea esencial es que son todas líneas de espera.
Pilas
- Implementación de recursividad en programación.
Código en PYTHON - ARBOL BINARIO
class
Nodo:
def __init__(self, elemento):
self.elemento
= elemento
self.derecha
= None
self.izquierda
= None
class arbolBinario:
def
__init__(self):
self.raiz
= None
def
insertar(self, x):
nuevo
= Nodo(x)
if(self.raiz
== None):
self.raiz
= nuevo
else:
anterior
= None
reco
= self.raiz
while
(reco != None):
anterior
= reco
if
(x < reco.elemento):
reco
= reco.izquierda
else:
reco
= reco.derecha
if
(x < anterior.elemento):
anterior.izquierda
= nuevo
else:
anterior.derecha
= nuevo
def
imprimirPre2(self,reco):
if(reco != None):
print
(reco.elemento)
self.imprimirPre2(reco.izquierda)
self.imprimirPre2(reco.derecha)
def imprimirPre(self):
self.imprimirPre2(self.raiz)
def
imprimirEnOrden2(self,reco):
if(reco
!= None):
self.imprimirEnOrden2(reco.izquierda)
print
(reco.elemento)
self.imprimirEnOrden2(reco.derecha)
def
imprimirEnOrden(self):
self.imprimirEnOrden2(self.raiz)
def
imprimirPost2(self,reco):
if(reco
!= None):
self.imprimirPost2(reco.izquierda)
self.imprimirPost2(reco.derecha)
print
(reco.elemento)
def imprimirPost(self):
self.imprimirPost2(self.raiz)
class Principal:
arbolBinario
= arbolBinario()
arbolBinario.insertar(100)
arbolBinario.insertar(25)
arbolBinario.insertar(70)
arbolBinario.insertar(55)
arbolBinario.insertar(200)
print
("PreOrden")
arbolBinario.imprimirPre()
print
("EnOrden")
arbolBinario.imprimirEnOrden()
print
("PostOrden")
arbolBinario.imprimirPost()
Código
en PYTHON – COLA
class
Nodo:
def __init__(self,
elemento):
self.elemento
= elemento
self.siguiente
= None
class
Cola:
def __init__(self):
self.raiz
= None
self.fin
= None
def insertar(self, x):
nuevo
= Nodo(x)
if
(self.raiz == None):
self.raiz
= nuevo
else:
self.fin.siguiente
= nuevo
self.fin
= nuevo
def quitar(self):
if(self.raiz
!= None):
aux
= self.raiz.elemento
self.raiz
= self.raiz.siguiente
return
aux
else:
return
None
def imprimirCola(self):
c
= self.raiz
while
c != None:
print
(c.elemento)
c
= c.siguiente
class
Principal:
cola = Cola()
cola.insertar(5)
cola.insertar(10)
cola.insertar(20)
cola.insertar(30)
cola.imprimirCola()
print ("Extraemos
un elemento de la Cola",cola.quitar())
cola.imprimirCola()
Código
en PYTHON – PILA
#!/usr/bin/env
python
class
Nodo:
def __init__(self,
elemento):
self.elemento
= elemento
self.siguiente
= None
class
Pila:
def __init__(self):
self.raiz
= None
def insertar(self, x):
nuevo
= Nodo(x)
if (self.raiz == None):
nuevo.siguiente
= None
else:
nuevo.siguiente
= self.raiz
self.raiz
= nuevo
def quitar(self):
if(self.raiz
!= None):
aux
= self.raiz.elemento
self.raiz
= self.raiz.siguiente
return
aux
else:
return
None
def imprimirPila(self):
p
= self.raiz
while
p!= None:
print
(p.elemento)
p
= p.siguiente
class
Principal:
pila = Pila()
pila.insertar(5)
pila.insertar(10)
pila.insertar(20)
pila.insertar(30)
pila.imprimirPila()
print ("Extraemos
un elemento de la Pila",pila.quitar())
pila.imprimirPila()
input()
Código
en JAVA – ARBOL BINARIO
import
java.util.Scanner;
public
class abb {
private class nodoArbol {
private abb hd;
private abb hi;
private int dato;
private void nodoArbol(){
hd = null;
hi = null;
dato = 0;
}
}
public nodoArbol raiz;
public void abb(){
nodoArbol raiz = new nodoArbol();
}
public boolean esVacio(){
return (raiz == null);
}
public void insertar(int a){
if (esVacio()) {
nodoArbol nuevo = new nodoArbol();
nuevo.dato = a;
nuevo.hd = new abb();
nuevo.hi = new abb();
raiz = nuevo;
}
else {
if (a > raiz.dato) {
(raiz.hd).insertar(a);
}
if (a < raiz.dato){
(raiz.hi).insertar(a);
}
}
}
public void preOrder(){
if (!esVacio()) {
System.out.print( raiz.dato +
", " );
raiz.hi.preOrder();
raiz.hd.preOrder();
}
}
public void inOrder(){
if (!esVacio()) {
raiz.hi.inOrder();
System.out.print( raiz.dato +
", " );
raiz.hd.inOrder();
}
}
public void posOrder(){
if (!esVacio()) {
raiz.hd.posOrder();
raiz.hi.posOrder();
System.out.print( raiz.dato +
", " );
}
}
public static void
main(String[] args) {
abb Arbol = new abb();
int opcion;
Scanner in = new Scanner(System.in);
do
{
System.out.println("********************************************");
System.out.println("********************MENU********************");
System.out.println("********************************************");
System.out.println("Presione
1 para agregar un elemento al Arbol");
System.out.println("Presione 2 para imprimir preOrder");
System.out.println("Presione 3 para imprimir inOrder");
System.out.println("Presione 4 para imprimir posOrder");
System.out.println("Presione 9 para salir de la lista");
opcion = in.nextInt();
switch(opcion){
case 1:
System.out.println("Ingresa un numero");
int n =
in.nextInt();
Arbol.insertar(n);
break;
case 2:
System.out.println("Imprimir preOrder");
Arbol.preOrder();
break;
case 3:
System.out.println("Imprimir inOrder");
Arbol.inOrder();
break;
case 4: System.out.println("Imprimir
posOrder");
Arbol.posOrder();
break;
}
}while(opcion != 9);
}
}
Código
en JAVA – COLA
class
Cola {
class Nodo
{
int
elemento;
Nodo
siguiente;
public
Nodo(int elemento)
{
this.elemento
= elemento;
siguiente
= null;
}
}
Nodo raiz;
Nodo fin;
public Cola()
{
raiz
= fin = null;
}
public void insertar (int elemento)
{
Nodo
a;
a
=new Nodo(elemento);
if(colaVacia())
{
raiz
= a;
}
else
{
fin.siguiente
= a;
}
fin
= a;
}
public boolean colaVacia()
{
if(raiz
== null)
{
return
true;
}
else
{
return
false;
}
}
public int quitar()
{
int
aux;
if(!colaVacia())
{
aux
= raiz.elemento;
raiz
= raiz.siguiente;
}
else
{
return
-1;
}
return
aux;
}
public void borrarCola()
{
while(raiz
!=null)
{
raiz
= raiz.siguiente;
}
System.gc();
}
public void imprimirCola()
{
Nodo
imp = raiz;
System.out.println("Listado
de todos los elementos de la cola");
while(imp!=null)
{
System.out.print(imp.elemento+"-");
imp
= imp.siguiente;
}
System.out.println();
}
public static void main (String[] args) {
Cola
cola1 = new Cola();
cola1.insertar(5);
cola1.insertar(10);
cola1.insertar(20);
cola1.insertar(30);
cola1.imprimirCola();
System.out.println("Extraemos
uno de la cola: "+cola1.quitar());
cola1.imprimirCola();
}
}
Código en JAVA – PILA
class Pila {
class Nodo{
int
elemento;
Nodo
siguiente;
public Nodo(int
elemento)
{
this.elemento
= elemento;
siguiente
= null;
}
}
Nodo raiz;
public Pila() {
raiz
= null;
}
public void insertar (int x)
{
Nodo
nuevo;
nuevo
= new Nodo(x);
if(pilaVacia())
{
nuevo.siguiente
= null;
}
else
{
nuevo.siguiente
= raiz;
}
raiz
= nuevo;
}
public int quitar()
{
if(!pilaVacia())
{
int
aux = raiz.elemento;
raiz
= raiz.siguiente;
return aux;
}
else
{
return
Integer.MIN_VALUE;
}
}
public boolean pilaVacia()
{
if(raiz == null)
{
return
true;
}
else
{
return
false;
}
}
public void imprimirPila()
{
Nodo
P = raiz;
System.out.println("Listado
de todos los elementos de la pila");
while(P!=null)
{
System.out.print(P.elemento+"-");
P
= P.siguiente;
}
System.out.println();
}
public static void main (String[] args)
{
Pila
pila1 = new Pila();
pila1.insertar(5);
pila1.insertar(10);
pila1.insertar(20);
pila1.insertar(30);
pila1.imprimirPila();
System.out.println("Extraemos
uno de la pila: "+pila1.quitar());
pila1.imprimirPila();
}
}
No hay comentarios:
Publicar un comentario