Investigación sobre árboles y su aplicación
Enviado por Daizon Sandoval • 4 de Febrero de 2020 • Apuntes • 595 Palabras (3 Páginas) • 95 Visitas
[pic 1]
Nombre: | David Adrián Sandoval Mercado |
Matrícula: | 14000398 |
Nombre de la Evidencia de Aprendizaje: | Investigación sobre árboles y su aplicación |
Fecha de entrega: | 08/10/19 |
Nombre del Módulo: | Matemáticas computacionales |
Nombre del asesor: | Ma. Dolores Sánchez Ramírez |
[pic 2]
La estructura de árbol esta compuesta de las mismas partes que contiene un árbol en la naturaleza, es decir que se compone de las siguientes partes: Raíz, ramas(aristas), nodos y las hojas.
El nodo típico de un árbol difiere de los nodos para el manejo de las listas, aunque solo en el número de nodos.
[pic 3]
Explicándolo más detalladamente diríamos que un árbol consiste en un nodo al cual denominamos como Raíz y una lista de subárboles, si el orden de los subárboles importa, entonces formara una lista se denomina como árbol ordenado. En caso de lo contrario los subárboles forman un conjunto y se denomina como árbol no ordenado.
Se definen también como nodos hijos a los nodos raíces de los subárboles, un nodo sin hijos también se le denominaría simplemente como hojas o externo en caso de lo contrario se le denominaría como nodo interno.
[pic 4]
Se dice que de un grafo es posible obtener un árbol que permite mantener conectados los nodos del grafo a todo esto le podemos decir que nos da un Árbol generados.
Existen dos formas para obtener el árbol generador:
- Búsqueda a lo ancho
- búsqueda en profundidad
Búsqueda a lo ancho
En este procedimiento se comienza en la raíz y se examinan los hijos de la misma de izquierda a derecha, si la información buscada no se encuentra en ese nivel se procede a buscar en el siguiente nivel de la misma forma, de izquierda a derecha y así hasta encontrar la información deseada.
Cuando se busca de la manera mencionada y no se encuentra dicha información se recomienda mandar un mensaje que diga “información inexistente” entonces tenemos que solo se busca por los anchos cuando el árbol es balanceado o tenga pocos niveles.
[pic 5]
Imagen ejempló Búsqueda a lo ancho.
Búsqueda de profundidad
En este se comienza con el nodo de raíz, después se busca el hijo de la izquierda y si este nodo tiene hijos se continua se continua con el de la izquierda y así sucesivamente hasta llegar a la parte mas baja del árbol. Si este nodo ya no tiene hijo izquierdo se continua con el hijo de la derecha hasta llegar a la hoja. Si no se encuentra la información se recorre el camino andado hasta el nodo inmediato interior que tenga hijos cuyos hijos no hayan sido inspeccionados, dando preferencia al de más a la izquierda. Cuando se llega nuevamente a la hoja, regresa hasta el nodo inmediata anterior que tenga hijos sin inspeccionar y así sucesivamente hasta encontrar la información deseada.
...