Estructura de Datos - Taller de Arboles

ESTRUCTURAS DE DATOS

TALLER SOBRE ARBOLES

1. Dados los siguientes arboles binarios :

[pic 1][pic 2]

• Halle la altura de cada uno
• Relacione las hojas
• Mencione dos (2) ejemplos de caminos de cada uno
• Navèguelos en Preorden, Inorden y Postorden

1. Convierta los dos arboles binarios en uno solo
2. Recorrer el nuevo arbol en Preorden, Inorden y Posorden
3. Genere un àrbol AVL a partir de la siguiente secuencia de adiciòn de nodos :

2 – 7 – 25 – 1 – 17 – 3 – 19 – 36 – 100

Muestre el proceso completo de transformaciòn.

1. Genere un àrbol AVL a partir de la siguiente secuencia de adiciòn de nodos :

20 – 28 – 22 – 25 – 27 – 10 – 21 – 4 - 3

Muestre el proceso completo de transformaciòn.

1. CONSTRUYA UN ARBOL AVL DADA LA SIGUIENTE SECUENCIA DE LLAVES DE NODOS A SER ADICIONADOS . DEBE MOSTRAR EL PROCEDIMIENTO DETALLADO.

14 – 6 – 24 – 35 – 59 – 17 – 21 – 32 – 4 – 7 – 15 – 22

RECORRARO INORDEN, POSTORDEN, PREORDEN

}

Respuesta a las preguntas del Taller

1.R/  

a. La altura de cada arbol corresponde al maximo numero de niveles de todos los nodos de cada arbol.

• La altura del primer arbol es : 5  
• La altura del segundo arbol es : 5

b. Las hojas o terminales de cada arbol hace referencia al nodo que no tiene ramificaciones o hijos.

• Las hojas del primer arbol son:  G, H,I,K
• Las hojas del segundo arbol son: 12, 19, 67

c. La longitud de camino de un nodo X cualquiera equivale al numero de arcos que se deben recorrer para llegar desde la raiz hasta un nodo X cualquiera, teniendo presente que el nodo raiz del arbol tiene valor de camino 1.

Dos ejemplos de camino de cada uno serian:

Ejemplos de camino del primer arbol:

• El nodo H del primer arbol tiene longitud de camino 4.
• El nodo K del primer arbol tiene longitud de camino 5.

Ejemplos de camino del segundo arbol:

•    El nodo 9 del segundo arbol tiene longitud de camino 3.
• El nodo 76 del segundo arbol tiene longitud de camino 2.

d .Recorridos de los Arboles.

Recorridos del primer arbol seria:

PRE-ORDEN: A,B,D,G,E,H,I,C,F,J,K

IN-ORDEN: G,D,B,H,E,I,A,C,J,K,F

POST-ORDEN: G,D,H,I,E,B,K,J,F,C,A

Recorridos del segundo arbol seria:

...