Arboles estructurales
Enviado por zwany • 14 de Octubre de 2018 • Tarea • 606 Palabras (3 Páginas) • 99 Visitas
Desarrollo. Realiza lo siguiente:
• Lleva a cabo una investigación en el Centro de Información Digital y en Internet, sobre los siguientes temas y su aplicación:
o Estructuras de árbol
Los arboles son las estructuras de datos más utilizados, también una de las más complejas. Se caracterizan por almacenar sus nodos en forma jerárquica y no en forma lineal como pueden ser las listas ligadas. Su estructura se conforma de:
Nodos: cada elemento que contiene un árbol
Nodo raíz: solo un nodo puede ser raíz y es el primer nodo
Nodo padre: todos aquellos nodos que tienen un hijo
Nodo hermano: son los que comparten a un mismo padre común dentro de la estructura
Nodo hoja: son los que al menos tienen un hijo y no son la raíz
Nivel: se refiere a cada generación dentro del árbol, cada generación tiene un número de niveles distintos que las demás generaciones.
Un árbol vacío tiene 0 niveles
El nivel de la raíz es 1
El nivel de cada nodo se calculado contando cuantos nodos existen sobre él, hasta llegar a su raíz +1, de forma inversa también se podría, contar cuantos nodos existen desde la raíz hasta el nodo buscado +1.
La altura: número máximo de niveles de un árbol, se calcula mediante recursividad tomando el nivel más grande de los dos sub-arboles.
Altura= Max (altura (hijo 1), altura (hijo 2), altura (hijo N)) +1
Peso: numero de nodos que tiene un árbol, es importante porque nos da la idea del tamaño y del espacio de memoria que pueda ocupar en tiempo de ejecución
Peso= peso(hijo1) +peso(hijo2) +peso (hijo N) +1
Orden: es el número máximo de hijos que puede tener un nodo
Grado: número mayor de hijos que tiene algunos de los nodos del árbol y este esta limitado por el orden, el cual indica el número máximo de hijos que puede tener un nodo. Este se calcula contando de forma recursiva el numero de hijos de cada subárbol hijo y el número de hijos en el nodo actual para tomar el mayor.
Grado= Max (contarHijos(hijo1), contarHijos(hijo2), contarHijos(hijo N), contarHijos(this)).
Sub-árbol: se le conoce a todo árbol generado a partir de una sección determinada del árbol. Por lo que podemos decir que un árbol es un nodo raíz con N sub-arboles.
o Árboles generadores
Un árbol T es un árbol generador de un grafo G si T es un subgrafo de G que contiene todos los vértices de G. Es así como el grafo que contiene a T debe ser conexo, pues de lo contrario no existiría un subgrafo que contuviera todos sus vértices. En general un grafo G tendrá varios arboles generadores, como el ejemplo:
o Recorridos de árboles
Los recorridos son algoritmos que nos permiten recorrer un árbol en un orden especifico, los recorridos nos pueden
...