Arboles en Estruturas de Datos

Introducción

Un árbol en informática se puede definir como una estructura de datos no lineal. La cual tiene como objetivo mayor representar datos con una relación jerárquica entre sus elementos, algunos ejemplos pueden ser registros, árboles genealógicos o tablas de contenidos. Nos profundizaremos en un tipo de árbol especial, llamado árbol binario, el cual es fácilmente implementado en lacomputadora; se toma en cuenta que un árbol es posee varias restricciones. También se va a ampliar sobre árboles más generales y puntos con relación a los árboles binarios; entre estos tenemos a la terminología, los árboles binarios complementos, árboles binarios de búsqueda, búsqueda e inserción en árboles binarios de búsqueda, árboles generales, representación de árboles generales en un programa ycorrespondencia entre los árboles generales y árboles binarios.



Justificación

Árboles en informática son de suma importancia para entender como una estructura de datos es formada y como funciona. Puede ser una excelente base para entender como datos son relacionados y estructurados jerárquicamente para su mejor análisis y procesamiento.
La aplicación de arboles binarios nos ayuda aentender una estructura de datos de forma sistemática, para poder visualizar cada fase y para tener un recorrido perfecto y deseado.

Árboles
Una de las estructuras de datos más importantes en programación es el árbol. Pueden usarse los árboles para representar la información en una estructura jerárquica. Los árboles pueden procesarse en forma recursiva y son muy adaptables a pruebasmatemáticas. El estudio de árboles ilustra las conexiones entre varios temas de la matemática discreta y ofrece oportunidades para aprovechar la matemática formal en la programación práctica.
La idea de estructura jerárquica es muy usada en la práctica. Por ejemplo, los libros son a menudo organizados como una sucesión de capítulos cada uno de los cuales son una sucesión de secciones que puede tenersubdivisiones, y así sucesivamente. Una empresa puede organizarse como las colecciones de unidades comerciales cada uno de las cuales pueden tener varias secciones. Las secciones, a su vez, pueden tener secciones múltiples, y así sucesivamente. El software es organizado como una colección de módulos cualquiera que pueden constituirse de varios módulos, con el nivel de refinamiento que los diseñadoresencuentren apropiado. En cierto nivel, los módulos se expresan en unidades básicas como los objetos, los métodos, o procedimientos. En otros términos, las estructuras jerarquías proporcionan una eficaz la manera de organizar la información. Los árboles proporcionan una capacidad enorme para expresar la idea de jerarquía. Ellos son objetos formales, matemáticos.
Definiciones
Un árbol o bien es unárbol vacío o es un nodo junto con una sucesión de árboles. Sea A un conjunto cualquiera:
1. nil∈ Arbol(A)
2. (cons a a1 a2… an)∈ Arbol(A) si (a∈ A)∧ (a1, a2,… ,an ∈ Arbol(A))
La definición es inductiva. El punto de arranque para la definición inductiva es el árbol vacío. La definición no dice lo que un árbol vacío es; esto queda como un término indefinido, y la existencia del árbol vacío seacepta como un axioma. El término “nodo” no se define, y la existencia de nodos para construir árboles también se toma como un axioma. Más adelante cuando se usen árboles para representar entidades matemáticas específicas diremos exactamente qué entidades comprenden el la información que contiene cada nodo que compone el árbol que se está construyendo.

El primer nodo que se agrega a un árbol novacío es la raíz del árbol. Cada miembro individual de la sucesión de árboles en la que se divide un árbol no vacío se denomina hijo.
Un árbol no vacío cuya la sucesión asociada de árboles está vacía se llama hoja. Una hoja sola es el tipo más simple de árbol no vacío. En este árbol la raíz es una hoja. En un árbol más complejo, es decir, uno que consiste en un nodo con hijos, la raíz no es...