Estructuras No Lineales

Estructura de datos

Unidad IV

Estructuras No Lineales

Rubi veronica chimal Cuxin.

Ingeniería en sistemas computacionales

INSTITUTO TECNOLÓGICO SUPERIOR DE FELIPE CARRILLO PUERTO

Estructuras No Lineales

IntroducciónEn esta unidad se debe conocer, identificar y aplicar las estructuras no lineales en la solución de problemas del mundo real. Para poder aprender de ello se necesita consultar en las fuentes bibliográficas la terminología sobre árboles como también practicar ejercicios y buscar información ayudara para su mayor comprensión. Utilizando un lenguaje de programación podemos implementar las operaciones básicas (insertar, eliminar, buscar) en un árbol binario de búsqueda, así como los recorridos en PreOrden, InOrden y PostOrden. En si podemos decir que aprenderemos conceptos y aplicaciones de por ejemplo: Concepto de árbol y su clasificación de árboles al igual las operaciones básicas sobre árboles binarios que sin duda son herramientas que sirven y servirán en nuestra vida escolar.

Estructuras No Lineales

Un árbol es una estructura de datos homogénea, dinámica y no lineal, en la que cada nodo (elemento) puede tener varios nodos posteriores, pero sólo puede tener un nodo anterior.

Un árbol es dinámico porque su estructura puede cambiar durante la ejecución de un programa. Y no lineal, ya que cada nodo del árbol puede contener varios nodos que dependan de él.La estructura de un árbol se forma de nodos y arcos (línea que une dos nodos), el primero de los nodos del árbol recibe el nombre de raíz, del cual se desprenden los nodos interiores y de éstos los nodos llamados hoja, que son los nodos que se encuentran al final del árbol; todos ellos en conjunto forman un árbol.

Clasificación de árboles.

 Los árboles se clasifican de la siguiente manera: Árboles binarios. Distintos Similares Equivalentes Equilibrado Completo

 Operaciones Básicas sobre árboles binarios.

 Las operaciones que se pueden aplicar a un árbol binario son las siguientes:

Creación de un árbol  Un árbol se forma de una serie de nodos y un nodo se integra de una serie de campos.

Ejercicio. Construir una clase que permita crear objetos que se comporten como un nodo de un árbol.

public class NodoB

{Object elemento; NodoB padre, izquierdo, derecho; //métodos

            }

Estructuras No Lineales

Inserción de un nodo nuevo.La operación de inserción permite agregar un nuevo nodo hoja al árbol, pero antes de agregarlo, debemos tomar en cuenta como se hace el acomodo u organización de los nodos dentro de la estructura del árbol. El primer nodo que entra en el árbol se le conoce como nodo raíz, del cual se desprendes los nodos intermedio y hojas.

Eliminación de un nodo.

La operación de eliminación de un nodo consiste en borrar el nodo del árbol binario de una forma definitiva, para este proceso la relación del nodo que se quiere eliminar con otros nodos debe desaparecer, pero que sucede con los nodos que dependen del nodo que se quiere eliminar. Para esto analizaremos los tres casos de eliminación en un árbol binario:

1. Eliminación de una hoja,2. Eliminación de un padre con un hijo o subárbol y3. Eliminación de un padre con dos hijos o subárboles.

 La eliminación de una hoja, es simple, solo es necesario encontrar el padre y establecer en nulo la relación con el nodo hoja.

La eliminación de un padre con un hijo, también es simple, solo se requiere conocer quién es el nodo anterior al padre y establecer una relación con el nodo hijo y que el nodo hijo establezca la relación con el que será su nuevo padre.

La eliminación de un padre con dos hijos, no es tan simple como las anteriores ya que en este caso la eliminación del padre genera dos nodos hijos que posiblemente no se puedan relacionar con el nodo anterior al padre, ya que se puede romper la integridad del árbol binario y agregar tres hojas a un padre.

Recorrido del árbol.

Recorrer significa visitar  cada uno de los nodos de un árbol exactamente una sola vez, este proceso puede interpretarse como poner todos los nodos en una línea o linealizar el árbol.

Existen tres formas de efectuar el recorrido y todas son de manera recursiva:

a) Recorrido en PreOrden

Estructuras No Lineales

         Visitar la raíz

         Recorrer el subárbol izquierdo

         Recorrer el subárbol derecho

b) Recorrido en InOrden

         Recorrer el subárbol izquierdo

         Visitar la raíz

         Recorrer el subárbol derecho

c) Recorrido en PostOrden

         Recorrer el subárbol izquierdo

         Recorrer el subárbol derecho

         Visitar la raíz

Balanceo del árbol.Un árbol binario se encuentra balanceado si la diferencia en la altura de los dos subárboles de cualquier nodo en el árbol es cero o uno.

Estructuras No Lineales

Conclusión

Conocimos, identificamos y aplicamos las estructuras no lineales en la solución de problemas del mundo real. Al igual conocimos un poco acerca de las teorías de esta unidad así como el aprendizaje utilizando un lenguaje de programación podemos implementar las operaciones básicas (insertar, eliminar, buscar) en un árbol binario de búsqueda, así como los recorridos en PreOrden, InOrden y PostOrden.