Scribd
Cargar
66 vistas6 páginas

Construcción y Análisis de Árboles Binarios

Este documento describe cómo construir un árbol binario de búsqueda a partir de una lista de nodos desordenados. Explica cómo ordenar los nodos de menor a mayor y seleccionar el nodo central como raíz. Luego, repite el proceso de manera recursiva en los subárboles izquierdo y derecho. También compara un árbol binario con uno convencional, señalando que el primero no puede tener más de dos hijos por nodo y sus nodos deben estar ordenados. Por último, explica el recorrido preorden paso a paso

Cargado por

Hernan Zuleta
Derechos de autor
© © All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como DOCX, PDF, TXT o lee en línea desde Scribd
66 vistas6 páginas

Construcción y Análisis de Árboles Binarios

Este documento describe cómo construir un árbol binario de búsqueda a partir de una lista de nodos desordenados. Explica cómo ordenar los nodos de menor a mayor y seleccionar el nodo central como raíz. Luego, repite el proceso de manera recursiva en los subárboles izquierdo y derecho. También compara un árbol binario con uno convencional, señalando que el primero no puede tener más de dos hijos por nodo y sus nodos deben estar ordenados. Por último, explica el recorrido preorden paso a paso

Cargado por

Hernan Zuleta
Derechos de autor
© © All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como DOCX, PDF, TXT o lee en línea desde Scribd

Á rboles

Estructura de Datos
Instituto IACC
xx/xx/20xx
Desarrollo

1.- 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.

Para poder diseñ ar el á rbol binario de bú squeda, primero ordene los nodos de menor a
mayor:

Nodos: 1, 3, 4, 7, 8, 9, 10, 12, 13, 15, 20, 22, 23, 30, 34, 40, 45, 48, 51, 53.

Luego de esto, tome como nodo raíz el nodo 20 al ser un valor que se encontraba por la
mediana de la totalidad:

Nodos: 1, 3, 4, 7, 8, 9, 10, 12, 13, 15, 20, 22, 23, 30, 34, 40, 45, 48, 51, 53.

Luego de este punto, repito el mismo procedimiento en los sub-á rboles siguientes:

Nodos: 1, 3, 4, 7, 8, 9, 10, 12, 13, 15, 20, 22, 23, 30, 34, 40, 45, 48, 51, 53.

Después de esto, busque seguir con un método similar, buscando la manera de acomodar
los nodos para respetar el orden de un á rbol binario de bú squeda. Esto significa, un nodo
con valor menos a la izquierda y/o uno con valor mayor a la derecha. Logrando la
construcció n del ABB mostrado.
2.- Utilizando la siguiente imagen desarrolle las actividades señ aladas:

a.- Indique si representa un á rbol binario o un á rbol convencional. Señ ale 2 argumentos
que justifiquen su respuesta.

El á rbol entregado en la imagen corresponde a un á rbol binario, ya que cada sub-á rbol no
posee má s de dos nodos hijos, y también agrego, que no corresponde a un á rbol binario de
bú squeda, dado que en el á rbol asignado se repiten nodos. Y este caso no se da en los
á rboles binarios de bú squeda. Ya que una de las características del segundo tipo de á rbol,
es que no se pueden repetir el valor de nodos en él.

b.- Confeccione una tabla comparativa entre ambos tipos de Á rboles que contenga a lo
menos 2 elementos a comparar.

Á rbol Convencional Á rbol Binario


Cantidad de Nodos Puede tener má s de 2 nodos No puede tener má s de 2
nodos
Orden de sus Nodos No posee un ordenamiento Sus nodos deben estar
especifico organizados de manera que
los nodos de menos valor
queden a la izquierda del
nodo Padre o Raíz, y los
mayores a la derecha.
3) 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.

Para realizar el recorrido en pre-orden a la figura entregada en la pregunta nú mero 1, se


debe de comenzar por el nodo Raíz:

Nodos: 20.

Luego de esto para establecer un recorrido en pre-orden se debe recorrer el á rbol por el
nodo izquierdo bajando por los sub-á rboles correspondientes hasta llegar a una hoja:

Nodos: 20, 9, 4, 3, 1.
Una vez alcanzada una hoja del ultimo sub-á rbol izquierdo de en este recorrido, se cuenta
el hijo derecho volviendo por los sub-arboles recorridos, en el caso que uno de estos hijos
derechos se divida en un nuevo sub-á rbol, se repite el descenso por los hijos izquierdos,
hasta volver al nodo Raíz:

Nodos: 20, 9, 4, 3, 1, 8, 7, 10, 13, 12, 15.

En este punto se repite la misma secuencia con los nodos pertenecientes a los sub-á rboles
del nodo Raíz ubicados a la derecha:

Nodo: 20, 9, 4, 3, 1, 8, 7, 10, 13, 12, 15, 34, 23, 22, 30, 40, 48, 45, 53, 51.

Bibliografía
IACC. (2019) Árboles II. Estructuras de Datos. Semana 8
https://www.lucidchart.com/pages/es

También podría gustarte