Matemáticas Computacionales EVIDENCIA: Investigación sobre árboles y su aplicación

MATERIA: Matemáticas Computacionales

EVIDENCIA: Investigación sobre árboles y su aplicación

ESTRUCTURAS DE ARBOL

En computación, un árbol es un tipo abstracto de datos, con una estructura jerárgica similar a un árbol, con un valor en la raíz y subárboles con un nodo padre.

Nodo: Cada elemento del árbol

Raíz: Primer nodo de un árbol

Padre: Nodos que tienen al menos un hijo

Hijo: Nodos que tienen un padre

Hermano: aquellos nodos que comparten padre

Rama: Aquellos que no son la raíz y tienen al menos un hijo

Hoja: Aquellos que no tienen hijos, siempre están en el extremo de la estrucutura

[pic 1][pic 2]

ARBOLES GENERADORES

De un grafo conexo es posible obtener un árbol (eliminando aristas redundantes) que permite mantener conectados a todos los nodos del grafo; este árbol recibe el nombre de árbol generador. Existen dos formas en que es posible obtener el árbol generador:

         -Búsqueda a lo ancho.

         -Búsqueda en profundidad.

Búsqueda de lo ancho: Empezamos en la raíz y después se examinan todos los hijos de la misma de izquierda a derecha. Si la información que se busca no se encuentra en ese nivel, se procede a buscar en el siguiente nivel también de izquierda a derecha, y así sucesivamente hasta encontrar la información.      

Búsqueda en Profundidad: Empezamos en el nodo raíz, después se busca en el hijo de la izquierda y si este nodo tiene hijos se continúa con el de la izquierda y así sucesivamente hasta llegar a la parte más baja del árbol. Si este nodo ya no tiene hijo izquierdo, se continúa con el hijo de la derecha hasta llegar a la hoja. Si no se ha encontrado la información, se recorre el camino andado hasta el nodo inmediato anterior que tenga hijos y cuyos hijos no hayan sido inspeccionados, dando preferencia al de más a la izquierda Cuando se llega nuevamente a la hoja, se regresa hasta el nodo inmediata anterior que tenga hijos sin inspeccionar y así sucesivamente hasta encontrar la información.      

RECORRIDO DE ARBOLES

Este es el proceso de visitar, de manera sistémica, cada uno de los nodos en las estructuras de datos del árbol, pueden ser en Preorden (raíz, izquierdo, derecho), Inorden (izquierdo, raíz, derecho) o Postorden (Izquierdo, derecho, raíz).

[pic 3]

PREORDEN: A, B, C, D, E, F, G, H, I

POSTORDEN: D, E, F,D ,B ,I ,H ,G , A

INORDEN: C, B, E, D, F, A, I, H, G

REFERENCIAS

ÁRBOL (INFORMÁTICA)

En el texto: (Es.wikipedia.org, 2019)

Bibliografía: Es.wikipedia.org. (2019). Árbol (informática). [online] Available at: https://es.wikipedia.org/wiki/Árbol_(informática) [Accessed 18 Jul. 2019

...