Estructura De Datos

Opción 1: Teoría de árboles binarios de búsqueda El grupo colaborativo realizará una revisión bibliográfica a cerca del tema de árboles binarios de búsqueda, para que tenga herramientas conceptuales para el desarrollo de la actividad.

En un documento de texto de una página, defina que es un árbol binario de búsqueda (ABB), indique las condiciones que debe cumplir un árbol binario de búsqueda, cual es el orden que deben llevar sus nodos, cuáles son sus restricciones, cual es la utilidad de los ABB.

ARBOLES BINARIOS DE BUSQUEDA (ABB)

Un árbol binario de búsqueda (ABB) es un árbol binario con la propiedad de que todos los elementos almacenados en el subárbol izquierdo de cualquier nodo x son menores que el elemento almacenado en x ,y todos los elementos almacenados en el subárbol derecho de x son mayores que el elemento almacenado en x.

Si el árbol está organizado de modo que para todo nodo ni, todas las claves de los nodos del subárbol izquierdo de ni son menores que la clave ni, y todas las claves del subárbol derecho de ni son mayores que la clave de ni, entonces el árbol es de búsqueda.

Lo ideal es que los árboles tengan altura mínima para conseguir un orden logarítmico.

Operaciones básicas en árboles

• Añadir o insertar elementos.

• Buscar o localizar elementos.

• Borrar elementos.

• Moverse a través del árbol.

• Recorrer el árbol completo.

Recorridos en árboles

Pre-orden

• Nodo raíz

• Subárbol izquierdo

• Subárbol derecho 1) A-B-D-E-C-F

In-orden

• Subárbol izquierdo

• Nodo raíz 2) D-B-E-A-C-F

• Subárbol derecho

Post-orden

• Subárbol izquierdo

• Subárbol derecho

• Nodo raíz 3) D-E-B-F-C-A

Posteriormente, en una segunda página del documento, el grupo diseñará la

Gráfica del árbol que muestre el resultado del árbol binario de búsqueda con los

datos que se relacionan a continuación: Es importante tener en cuenta el orden de

los nodos. La grafica del árbol puede ser diseñada en cualquier herramienta de su

preferencia, si lo desea puede hacerla en Word. Una vez diseñada la grafica

identifique sus partes, es decir la Raíz, el subárbol izquierdo y el subárbol

derecho.

Datos para diseñar la gráfica

Preorden = [17 , 11 , 8 , 16 , 15 , 22 , 19 , 66 , 28 , 74]

Inorden = [8 , 11 , 15 , 16 , 17 , 19 , 22 , 28 , 66 , 74]

Postorden = [8 , 15 , 16 , 11 , 19 , 28 , 74 , 66 , 22 , 17]

...