Arboles Binarios

Arboles Binarios


¿que es un á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"). Si algún hijo tiene como referencia a null, es decir que no almacena ningún dato, entonces este es llamado un nodo externo. En el caso contrario el hijo es llamado un nodo interno. Usos comunes de los árboles binarios son los árboles binarios de búsqueda, los montículos binarios y Codificación de Huffman.

En el siguiente video podeis ver una aplicación que crea arboles binarios y los muestra en pantalla:

Enlace de descarga de ejemplo: http://jsbsan.blogspot.com.es/2012/08/ejemplo-de-uso-de-arbol-binario-el.html

Fifo y Lifo

Listas Fifo y Lifo

¿que es una lista fifo?

Primero en Entrar, Primero en Salir, en inglés First In, First Out (FIFO), es un concepto utilizado en estructuras de datos, contabilidad de costes y teoría de colas. Guarda analogía con las personas que esperan en una cola y van siendo atendidas en el orden en que llegaron, es decir, que "la primera persona que entra es la primera persona que sale".
También se le denomina «primero en llegar, primero en ser atendido», en inglés: First Come, First Served (FCFS).

https://es.wikipedia.org/wiki/First_in,_first_out

¿y que es una lista lifo?

El término LIFO es el acrónimo inglés de Last In, First Out (“último en entrar, primero en salir”), también conocido como FILO que es la sigla de First In, Last Out (“primero en entrar, último en salir”). Puede tener distintos significados según el contexto.

https://es.wikipedia.org/wiki/Last_in,_first_out

Para implementar este tipo de listas en gambas3,  lo haremos de forma genérica, vamos a usar este diagrama uml para que veais más claro como se organizará el código fuente y sus clases:

En el ide de gambas3, se queda de esta manera:

Clase ApiLista:


PUBLIC SUB anadir(Obj AS Variant)

END


PUBLIC FUNCTION extraer() AS Variant

END


PUBLIC FUNCTION getlongitud() AS Integer

END




Clase colaFifo:

' Gambas class file

INHERITS ApiLista

PRIVATE primero AS Nodo
PRIVATE ultimo AS Nodo
PRIVATE longitud AS Integer

PUBLIC SUB anadir(obj AS Variant)


DIM aux AS NEW Nodo
aux.objeto = obj
IF longitud = 0 THEN
primero = aux
ELSE
ultimo.siguiente = aux
ENDIF


ultimo = aux
longitud += 1


END




PUBLIC FUNCTION extraer() AS Variant

DIM obj AS Variant
IF longitud = 0 THEN
RETURN -111 'cola vacia

ELSE
obj = primero.objeto
primero = primero.siguiente
longitud -= 1
RETURN obj
ENDIF

END


PUBLIC FUNCTION getlongitud() AS Integer

RETURN longitud

END




Clase pilaLiFo:

' Gambas class file

INHERITS ApiLista


PRIVATE top AS Nodo
PRIVATE longitud AS Integer


PUBLIC SUB anadir(obj AS Variant)


DIM aux AS NEW Nodo
aux.objeto = obj
aux.siguiente = top
top = aux
longitud += 1


END



PUBLIC FUNCTION extraer() AS Variant
DIM obj AS Variant


IF top = NULL THEN
RETURN NULL ' lista vacia
ENDIF


obj = top.objeto
top = top.siguiente
longitud -= 1
RETURN obj

END


PUBLIC FUNCTION getlongitud() AS Integer


RETURN longitud


END





Clase Nodo:

PUBLIC objeto AS Variant
PUBLIC siguiente AS Nodo





En el Formulario FMain: 


Crearemos unas listas tipo pilaLifo y colaFifo, añadiremos algunos elementos y luego lo extraeremos, mostrandolo en un textarea.

PUBLIC SUB Form_Open()

DIM i AS Integer
DIM elementos AS Integer


DIM pila AS NEW pilaLiFO
DIM cola AS NEW colaFifo



' Añadimos los mismos elementos a la pila y la cola.
FOR i = 0 TO 9
pila.anadir("AB" & Str$(I))
cola.anadir("AC" & Str$(I))
NEXT


' Extraer Pila
TextArea1.text = "Orden de Extraccion de la pila LIFO:\n"


elementos = pila.getlongitud()


FOR i = 0 TO elementos - 1
TextArea1.text &= " [" & pila.extraer() & "] "
NEXT


TextArea1.text &= "\n-------\n"
'Extraer en Cola
TextArea1.text &= "Orden de Extraccion de la cola FIFO:\n"




elementos = cola.getlongitud()


FOR i = 0 TO elementos - 1
TextArea1.text &= " [" & cola.extraer() & "] "
NEXT



END

Ejemplo funcionando:

Código Fuente:

Alojado en google drive

Nota:
Extensión para libreoffice para colorear código fuente:
http://extensions.libreoffice.org/extension-center/coooder

Colecciones

Las colecciones son parecidas a los arrays, pero en vez de usar un número como indice, usa una cadena de texto  para acceder al valor guardado (tipo variant), creando internamente una tabla hash en la cual se pueden buscar rápidamente pares clave-valor.



 Para definirla se usa:

[Dim | Public | Private ] nombre As New  Collection

Y con el operador punto (.) podemos acceder a las propiedades y sus métodos asociados para usarlas:

Propiedades
Count	Devuelve el número de elementos que tiene
Key	Devuelve la clave del último elemento leido o enumerado
Length	Igual que count
Métodos
Add	Añade un elemento nombre.Add(value as Variant, key as string)
Clear	Elimina todos los elementos. nombre.clear()
Copy	Retorna una copia de la colección: nombre2=nombre.copy()
Exist	Devuelve "true" si hay algun elemento que use esa clave: nombre.exist("clave") -> devuelve "false" o "true"
Remove	Elimina un elemento de la coleccion indicando la clave nombre.remove("clave")

Para más información:
http://gambaswiki.org/wiki/comp/gb/collection


Ejemplo:
Programa que nos proporcionas datos de los planetas Mercurio,Venus y Tierra, mediante el uso de colecciones.

' Gambas module file

'Ejemplo de uso de colecciones

'Planetas:

'datos obtenidos de la wikipedia: http://es.wikipedia.org/wiki/Anexo:Datos_de_los_planetas_del_Sistema_Solar

'

'Estructura que uso para guardar información

Public Struct informacion

DistanciaAlSol As Float

radio As Float

PeriodoDeRotacion As Float

TemperaturaMedia As Float

ComposicionAtmosfero As String

End Struct

Public planeta As New Collection 'creo e instancio el objeto "planeta", de la clase Collection

Public Sub Main()

Dim opcion As String 'variable que uso para que el usuario introduzca la opcion

datos 'subrutina que carga en la coleccion los datos de los planetas

'-------------

'incio el menu

'-------------

opcion = "1"

While (opcion <> "0")

'{

Print "Menu de Planetas"

Print "----------------"

Print "0- Salir "

Print "1- Mercurio"

Print "2- Venus"

Print "3- Tierra"

Print "Escribe el numero del planteta para decirte sus datos:"

Input opcion

Select opcion

'{

Case "1"

escribe(planeta["Mercurio"]) 'uso la funcion escribe para escribir los datos de la coleccion

Case "2"

escribe(planeta["Venus"])

Case "3"

escribe(planeta["Tierra"])

'}

End Select

'}

Wend

Print "--------------------"

Print "- fin del programa -"

Print "--------------------"

End

Public Sub datos()

Dim info As Informacion

info = New Informacion'instancio el objeto info

'--------------------------------

'Planeta: Mercurio

info.ComposicionAtmosfero = "He Na P"

info.DistanciaAlSol = 57909175

info.PeriodoDeRotacion = 58

info.radio = 2439.64

info.TemperaturaMedia = 166.85

planeta.Add(info, "Mercurio") 'info, lo añado a la coleccion, con la clave "Mercurio"

info = New Informacion 'instancio otra vez el objeto info, para poderlo usar vacio de datos anteriores

'--------------------------------

'Planeta: Venus

info.ComposicionAtmosfero = "96% CO2, 3 % N2, 0,1% H2O"

info.DistanciaAlSol = 108208930

info.PeriodoDeRotacion = -243

info.radio = 6051.59

info.TemperaturaMedia = 456.84

planeta.Add(info, "Venus") 'info, lo añado a la coleccion, con la clave "Venus"

 

info = New Informacion'instancio otra vez el objeto info, para poderlo usar vacio de datos anteriores

'--------------------------------

'Planeta:

info.ComposicionAtmosfero = "78% N2, 21% O2, 1% Ar"

info.DistanciaAlSol = 149597880

info.PeriodoDeRotacion = 0.9972

info.radio = 6378.15

info.TemperaturaMedia = 14.85

planeta.Add(info, "Tierra") 'info, lo añado a la coleccion, con la clave "Tierra"

End

Public Sub escribe(informa As Informacion)

Print "Composicion Atmosferica: "; informa.ComposicionAtmosfero

Print "Distancia al sol: "; Format(informa.DistanciaAlSol, "#,.##")

Print "Periodo de rotación: "; Format(informa.PeriodoDeRotacion, "#,.##")

Print "radio: "; Format(informa.radio, "#,.##")

Print "temperatura media: "; informa.TemperaturaMedia

End

Descarga del ejemplo completo: Enlace


Ejemplo de Ciudades y Temperaturas: Blog de Shell: Gambas-basico - las colecciones


Ejemplo Completo de Listin Telefonico usando colecciones: Enlace Pdf y Enlace Código Fuente