Árbol Binario

ÁRBOL BINARIO

Un árbol es conjunto de nodos que cumple con las relaciones padre, hijo y hermano.
llamamos hijos de un nodo a todos los nodos que podemos llegar directamente por medio de un apuntador, llamaremos padre al nodo del cual proviene el nodo hijo. Existe un nodo que no tiene padre y le llamamos raíz del árbol.
Hasta ahora el análisis de estructura de datos se ha limitado a los arboles en que cada nodo tiene como máximo dos descendientes o hijos, es decir, a los arboles binarios. Esto resulta perfectamente apropiado si , por ejemplo, se requiere representar relaciones familiares en las que cada persona se encuentre relacionada con sus padres. Pero si la relación es a la inversa necesitamos una estructura que asocie a cada padre un numero arbitrario de hijos.
Un árbol es una estructura jerárquica de datos que imita la forma de un árbol, un conjunto de nodos conectados. Un nodo es la unidad sobre la que se construye el árbol y puede tener ceros o mas nodos hijos conectados a él. Se dice que un nodo a es padre de un nodo b si existe un enlace desde a hasta b. Solo puede haber un único nodo sin padres, que llamaremos raíz. Un nodo que no tiene hijos se conoce como hoja y a los demás nodos se les conoce como ramas.Formalmente,un árbol se puede definir de manera recursiva, se utiliza la recursión para definir un árbol porque es una característica inherente a los mismos.

UML NODO -ARBOL

UML ARBOL

SOLUCIÓN EN JAVA

Nodo correspondiente de Árbol

Aquí se encuentra los atributos de la clase NodoArbol y los constructores de la clase.

Aquí se encuentra los atributos de la clase encapsulados.

Árbol Binario

Aquí se encuentra el atributo de la clase, el constructor de la clase y el get y set.

Aquí se encuentra el método insertar que crea el nodo que vamos a insertar y el método  inOrden donde recorre el subarbol izquierdo, visita la raiz y recorre el subarbol derecho.

Aquí se encuentra el metodo preOrden donde visita la raiz, recorre el subarbol izquierdo y recorre el subarbol derecho y postOrden donde recorre el subarbol izquierdo, recorre el subarbol derecho y visita la raiz.

Prueba Árbol

Aquí se muestra la clase PruebaArbol.

En las siguientes pantallas se muestra el resultado de los tres recorridos: inOrden, preOrden y postOrden.

CONCLUSIÓN

Nosotros llegamos a la conclusión de que este proyecto puede ser útil en múltiples áreas ya que los arboles son estructuras compuestas por nodos, utilizadas para la solución de una gran variedad problemas, ya que pueden implementarse fácilmente en un ordenador.

Ademas el uso de los arboles permite a los usuarios mejorar o modificar el programa de acuerdo a las necesidades que se tengan haciéndolo ya sea, con una interfaz mucho mas dinámica a la ya existente o implementa mejoras que ninguna otra aplicación antes tuviera de acuerdo a sus propiedades.

   

Cola

COLA

Una cola es una lista de elementos en la que estos se introducen por un extremo y se eliminan por otro.los elementos se eliminan en el mismo orden en el que se insertaron.
por lo tanto el primer elemento que entra ala cola sera el primero en salir.debido a esta característica, las colas también reciben el nombre de estructuras FIFO(Firts-In,Firts-Out: primero en entrar, primero en salir).
Existen numerosos casos de colas en la vida real: las personas esperando para usar un talefono publico(la primera persona de la cola sera la primera que use el talefono) las personas que esperan para ser atendidas en la caja de un banco (la primera persona de la cola sera la primera en ser ).

UML NODO-COLA

UML-COLA

SOLUCIÓN EN JAVA

Nodo correspondiente de cola

Aquí se encuentra los atributos de la clase Nodo y los constructores de la clase.

Aquí se encuentra los atributos de la clase encapsulados.

Cola

Aquí se encuentra los atributos de la clase Cola: frente donde sera el extremo en el cual se eliminaran elementos; fin: sera el extremo en el cual se harán las inserciones y luego después encapsulados.

Aquí se encuentra el constructor de la clase Cola, el método inserta donde consiste en incrementar el puntero al final de la cola y agregar el nuevo valor y elimina donde consiste en asignar a una variable de trabajo por el puntero frente y desplazar a este apuntando al siguiente elemento.

Resultado cola

Aquí se muestra el código para mostrar el resultado.

En las siguientes pantallas se muestran el resultado de los datos eliminados.

CONCLUSIÓN

nosotros llegamos ala conclusión que una cola es un TDA dedicado al almacenamiento y manipulación de elementos, su funcionalidad es siempre la misma independientemente de la implementan que se haya utilizado, su funcionalidad cumple con la regla FIFO (el orden de la salida

de los elementos es el mismo que el de la entrada), esto se debe a que las colas están bien diseñadas para devolver los elementos ordenados tal como llegan. Para esto las colas poseen un punto de acceso y otro de salida que lógicamente están ubicados en extremos opuestos. Siempre vemos que el elemento esta primero al frente.

Pila

PILA

Una pila es una lista de elementos a la cual se puede insertar o eliminar elementos solo por uno de los extremos.Ya que las pilas son LIFO(Last in - First Out) ultimo en entrar primero en salir.Son aquellas que solo tiene 2 operaciones, Push(Inserción) y Pop(Eliminación) la cual solo se puede efectuar por un extremo llamado Top. Sin Embargo se le pueden aplicar todas las operaciones al igual que a las listas.

En consecuencia, los elementos de una pila serán eliminados en orden inverso al que se insertaron.Es decir el ultimo elemento que se mete en la pila es el primero que se saca.Existen numerosos casos prácticos en los que se utiliza el concepto de pila: pila de platos, pilas de latas en un supermercado, etc.

UML NODO-PILA

 UML PILA

SOLUCIÓN EN JAVA

Nodo correspondiente de pila

Aquí se muestra los atributos de la clase Nodo y los correspondientes constructores de la clase.

Aquí se muestra los atributos encapsulados.

Pila

Aquí se muestra el atributo de la clase Pila y el método Push donde es la operación de inserción, consiste en incrementar el tope de la pila y agregar el nuevo valor en esa posición.

Aquí se encuentra el método de eliminación Pop donde consiste en quitar el valor que se encuentra almacenado en el tope de la pila y disminuir en uno el valor del tope.

Resultado pila

Aquí  se muestra el código para mostrar el resultado.

En las siguientes pantallas se muestran los resultados correspondientes.

CONCLUSIÓN PILA

Nosotros llegamos ala conclusión que una pila es una lista ordenada o estructura de datos en la que el modo de acceso a sus elementos es de tipo LIFO “ultimo en entrar, primero en salir” que permite almacenar y recuperar datos,que se aplica en el área de informática debido a su simplicidad y ordenación de la propia estructura.
Por ejemplo el manejo de los datos se cuenta con dos operaciones básicas que son apilar (push), que coloca un objeto en la pila, y su operación inversa, retirar (o des apilar pop), que retira el ultimo elemento apilado.

Las pila suelen emplearse en estos contextos:

-Evaluación de expresiones (notación palanca inversa).
-Reconocedores sintéticos de lenguajes independientes de contextos.
-Implementacion de recursividad.

Lista

INTRODUCCIÓN

La información que se procesa en la computadora, es un conjunto de datos, que pueden ser simples o estructurados. Los datos simples son aquellos que ocupan sólo una localidad de memoria,mientras que los estructurados son un conjunto de casillas de memoria a las cuales hacemos referencia mediante un identificador único.Debido a que por lo general tenemos que tratar con conjuntos de datos y no con datos simples (enteros, reales, booleanos, etc.) que por sí solos no nos dicen nada, ni nos sirven de mucho, es necesario tratar con  estructuras de datos adecuadas a cada necesidad.
Las estructuras de datos son una colección de datos cuya organización se caracteriza por las funciones de acceso que se usan para almacenar y acceder a elementos individuales de datos.
Una estructura de datos se caracteriza por lo siguiente:

• Pueden descomponerse en los elementos que la forman.

• La manera en que se colocan los elementos dentro de la estructura afectará la forma en que se realicen los accesos a cada elemento.

• La colocación de los elementos y la manera en que se accede a ellos puede ser encapsulada.

OBJETIVOS

El objetivo por el cual fue el presente trabajo de estructura de datos, es el establecer un material de apoyo y consulta para ti que eres alumno de ingeniería en informática y de sistemas o de cualquier otra área a fin en la cual se imparta la materia de Estructura de Datos. Una vez que hayas terminado de revisar detenidamente este material, serás capaz de establecer estructuras lógicas de datos que te permitan hacer un uso más eficiente del espacio de memoria, de minimizar los tiempos de acceso, así como de lograr formas más efectivas de inserción y eliminación de datos en estructuras de almacenamiento. Ahora que ya sabes en lo que te puede ayudar este blog, puedes empezar a hacer uso de él, consultando todas tu tareas y dudas que tengas acerca de la materia.

LISTA

Una lista es una estructura de datos homogénea y dinamica, que va a estar formada por una secuencia de elementos, donde cada uno de ellos va seguido de otro o de ninguno.Homogénea: Todos los elementos que la forman tienen el mismo tipo base.Dinámica: Puede crecer o decrecer en tiempo de ejecución según nuestras necesidades.dos listas pueden ser diferentes si:No tienen el mismo número de elementos:

UML

UML NODO-LISTA

S0LUCION EN JAVA

Nodo correspondiente de lista

Aquí se muestra los atributos de la clase Nodo y los constructores de la clase misma.

Aquí se muestra los atributos encapsulados de la clase Nodo.

Lista

Aquí se encuentra el atributo de la clase Lista, el constructor correspondiente y el método inserta inicio donde hace la inserción de un nuevo elemento al inicio de la lista

Aquí se encuentra el método insertafinal donde es cuando interesa agregar un nuevo elemento al final de la lista y el método insartaantes donde la inserción de un nuevo elemento antes de un nodo que almacena cierta dato dado como referencia.

Aquí se encuentra el método insertadespues donde la insercion de un nuevo elemento después de un nodo que almacena cierta dato como referencia.

Aquí se encuentra el método imprimir y el método eliminaalinicio donde el nodo que se va a eliminar debe ser apuntado por una variable auxiliar, luego debe redefinir el primero con la direccion del sucesor y finalmente se libera la porción de memoria ocupada por el nodo.

Aquí se encuentra el método eliminafinal donde se debe recorrer la lista hasta llegar al elemento deseado y el método eliminax donde recorre la lista hasta llegar al elemento buscado y una vez encontrado se debe establecer la liga entre su predecesor y su sucesor y liberar el espacio de memoria ocupada por dicho nodo.

Menú de Operaciones Lista

En las siguientes pantallas, se muestra el código para mostrar en pantalla el resultado de la Lista mediante un Menú de Operaciones.

CONCLUSIÓN

Nosotros llegamos a la conclusión  que las Listas son estructura de datos dinámicas que poseen nodos, los cuales contienen información de algún dato y punteros que apuntan o hacen referencia a otro nodo de lista.

Aparecen en los interfaces de usuarios para facilitar al operador en la manipulación de muchos elementos se crean utilizando métodos similares.