Investigación sobre árboles y su aplicación

Enrique Isaías Bravo Pérez

17005148

Matemáticas computacionales v1

Investigación sobre árboles y su aplicación

09/07/2018

Haydee Segura Valverde

Estructuras de árbol:

Los árboles son las estructuras de datos más usadas y a su vez de las más complejas, están caracterizadas por almacenar nodos en forma jerárquica y no lineal.

Los arboles están formados o estructurados por nodos, nodos raíz, nodo padre, nodo hijo, nodo hermano, nodo hoja, nodo rama.

Los arboles también tienen otras propiedades utilizadas en diferentes ámbitos, los cuales son el nivel, la altura, el peso, el orden, el grado, el sud-árbol, el árbol n-ario, el árbol binario, árbol binario lleno, árbol binario perfecto y otros más que pueden servir para diferentes servicios.

Arboles generadores:

Un grafo generador es un subgrafo mínimo conexo de un grafo conexo en el sentido de que a partir de un subgrafo conexo el cual no sea un árbol generador, una o más de sus aristas pueden eliminarse, de manera que el grafo resultante aún sea un subgrafo conexo.

Para encontrar el árbol generador existen dos formas, una es la búsqueda a lo ancho y la otra seria búsqueda en profundidad.

En búsqueda a lo ancho se comienza en la raíz y se examinan todos los hijos de izquierda a derecha de un nivel, en caso de que en la búsqueda no se encuentre la información requerida proseguimos a buscar en el siguiente nivel igual de izquierda a derecha y así hasta encontrar la información.

En búsqueda en profundidad se comienza en la raíz y después se busca en el hijo de la izquierda y si tiene hijos este nodo continuamos con el de la izquierda y en caso de no tener más hijos del lado izquierdo continuamos con el de la derecha hasta llegar a la hoja, en caso de no encontrar la información se sigue al siguiente nodo dando preferencia al lado izquierdo siguiendo el camino andado.

Recorridos de árboles: Pre orden, Inorden, Postorden

“Pre orden: (raíz, izquierdo, derecho).

Para recorrer un árbol binario no vacío en pre orden, 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”

(Wikipedia, 2018)

“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”

(Wikipedia, 2018)

“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:

...