Estructura de datos
Daniela Cocio HernándezInforme19 de Diciembre de 2020
543 Palabras (3 Páginas)1.324 Visitas
Árboles
Daniela Cocio Hernández
Estructura de datos
Instituto IACC
21 de diciembre
Desarrollo
- Usando los siguientes datos construya un árbol binario de búsqueda y grafíquelo utilizando la herramienta que estime conveniente e insértelo en su documento (describa paso a paso su construcción)
Nodos: 22, 15, 3, 8, 40, 45, 13, 20, 30, 1, 7, 34, 48, 53, 9, 23, 12, 51, 4, 10.
Nodo en orden creciente: 1, 3, 4, 7, 8, 9, 10, 12, 13, 15, 20, 22, 23, 30, 34, 40, 45, 48, 51, 53.
[pic 1]
Paso 1: Contabilizar la cantidad de nodos entregados.
Paso 2: Ordene los nodos de menor a mayor, considerando los nodos centrales para dejar como nodo raíz en este caso contamos con los nodos 15 y 20, teniendo en cuenta la cantidad de nodos mayores y menores, decido dejar como nodo central el nodo 15, para poder dejar el árbol de forma equilibrada.
Paso 3: Construcción del árbol del subárbol izquierdo. Aplico el mismo la misma lógica de ubicar los números centrales y considerar la construcción de tal forma que cada nodo tenga 2 descendientes, considerando las ramas izquierdas y derechas.
Paso 4: Construcción del subárbol derecho. Elijo el número 20 para iniciar el la construcción del subárbol derecho dado que es el menor de los números más altos, pero cumple el criterio de ser mayor que el nodo raíz y luego comienzo el orden de los números mayores siguiendo la lógica que los nodos menores se ubican hacia la izquierda y los nodos mayores hacia la derecha.
- Utilizando la siguiente imagen desarrolle las actividades señaladas:
[pic 2]
- Indique si representa un árbol binario o un árbol convencional. Señale 2 argumentos que justifiquen su respuesta.
El árbol representado es un árbol binario, dado que los nodos principal o raíz tiene como máximo dos subárboles, el izquierdo y el derecho; además los nodos hijo no tienen más de 2 nodos como descendientes.
- Confeccione una tabla comparativa entre ambos tipos de árboles que contenga a lo menos 2 elementos a comparar.
Árbol convencional | Árbol binario | |
Segundo nivel de nodos | Puede tener más de dos subárboles | Puede tener como máximo dos subárboles. Siempre es necesario distinguir entre el subárbol izquierdo y derecho. |
Organización de datos | Los nodos se agregan de acuerdo al orden que se van dando y al espacio que se desee que ocupe en el árbol. | De acuerdo a la inserción de nodos estos se ubicarán de tal forma que en el subárbol izquierdo irán los nodos con datos menores que el nodo raíz y por otro lado en el subárbol derecho se ubicarán nodos con valores mayores al nodo raíz. Esto se aplica en el caso de árbol binario de búsqueda. |
Operación búsqueda | Más lento en comparación de un árbol binario de búsqueda | Es más rápido dado que al saber que dato buscar y saber si este es menor o mayor a la raíz, no debe recorrer el árbol entero para encontrar el elemento deseado. |
- Utilizando los nodos presentados en la pregunta 1 explique de qué forma se realiza un recorrido pre orden. Establecer paso a paso el procedimiento utilizado.
Consiste en visitar sucesivamente y desplegar el dato del nodo actual, luego el hijo izquierdo y luego el hijo derecho.
[pic 3]
Por ende, el paso n° 1 seria, visitar el nodo raíz: 15.
Luego el subárbol izquierdo en el siguiente orden: 9,8,4,1,3,7,10,12,13.
Por último, visitar el subárbol derecho: 20,30,22,23,34,40,48,45,51,53.
Bibliografía
[pic 4]
...