• Author / Uploaded
• Javier Adarme Dàvila

Citation preview

TALLER DE ARBOLES DE BUSQUEDA BINARIA 1. Hacer la prueba de escritorio (Construir tabla) del algoritmo ABB. Ingrese los siguientes nodos y vaya mostrando el árbol de búsqueda binaria cada vez que ingrese un nodo. 50 en la dirección X0.

30 en la dirección X1.

70 en la dirección X2.

15 en la dirección X3.

40 en la dirección X4.

55 en la dirección X5.

80 en la dirección X6.

10 en la dirección X7.

20 en la dirección X8.

35 en la dirección X9.

52 en la dirección X10.

60 en la dirección X11.

32 en la dirección X12.

18 en la dirección X14.

X0

X1

X1

50

X2

X3

X5

X10

30

X4

X5

X6

55

X11

X10

NULL

X2

NULL

NULL

NULL

70

X6

X7

X7

80

NULL

60

NULL

X11

52

X3

NULL

15

X8

X8

10

NULL

32

NULL

X12

NULL

X4

X14 X13

X9

40

NULL

X9

20

NULL

X12

35

NULL

X14

NULL

18

NULL

Elimine los siguientes nodos y vaya mostrando el árbol de búsqueda binaria cada vez que elimine un nodo: Elimine nodo con el valor de 60.

Elimine nodo con el valor de 20.

Elimine nodo con el valor de 30.

La tabla a construir es de la siguiente forma: borrar_nodos() insertar()

desplegar() eliminar_nodo()

main()

raiz raiz

aux1 aux2 aux3 raiz

valor aux1 aux2 temp b

raiz valor resp

X0

X6

X0

NULL NULL X0

60

X11

X5

X11

X0

X10

X1

NULL X0

20

X8

X3

X8

X5

X2

NULL X0

30

X1

X3

X1

X2

X3

NULL X1

false

60

S

20

S

30

X9

X4

NULL X1

X4

X5

NULL X2

X14

X6

NULL X2

X7

X7

NULL X3

X3

X8

NULL X3

X1

X9

NULL X4

X0

X10

NULL X5

X11

NULL X5

X12

NULL X9

X14

NULL X8

IMPORTANTE: en la tabla anterior solo se registraron los valores finales que tomaban cada una de las variables en su correspondiente método. 2. Modificar la función 𝒊𝒏𝒔𝒆𝒓𝒕𝒂𝒓() de tal manera que no permita agregar nodos repetidos y despliegue el mensaje “El nodo a insertar ya existe”. void insertar() { NodoArbol *aux1, *aux2, *aux3; aux1 = new NodoArbol(NULL, NULL); aux2 = raiz; aux3 = NULL; bool encontrado = false; cout > aux1->info; while (aux2 != NULL) { aux3 = aux2; if (aux1->info > aux2->info) aux2 = aux2->derecha; else aux2 = aux2->izquierda; if (aux1->info == aux3->info) encontrado = true; } if (encontrado == false) { if (aux3 == NULL) raiz = aux1; else { if (aux1->info < aux3->info) aux3->izquierda = aux1; else aux3->derecha = aux1; } } else cout derecha = temp->derecha; else { if (temp->derecha != NULL)aux2->izquierda = temp->derecha; else aux2->izquierda = NULL;

7. Decir de qué manera la función 𝒅𝒆𝒔𝒑𝒍𝒆𝒈𝒂𝒓() recorre el árbol. R/: Inorden, se recorre en inorden el subárbol izquierdo del nodo raíz, se visita el nodo raíz del árbol y finalmente se recorre en inorden el subárbol derecho del nodo raíz. 8. Implementar la función 𝒅𝒆𝒔𝒑𝒍𝒆𝒈𝒂𝒓() utilizando otra forma de recorrido. R/: Al igual que se realizó en el ejercicio 4, aquí podemos hacer lo mismo, invertir el orden de recursividad, por lo que ahora el árbol se recorrerá Inorden converso, se recorre en inorden el subárbol derecho del nodo raíz, se visita el nodo raíz del árbol y finalmente se recorre en inorden el subárbol izquierdo del nodo raíz. void listar(NodoArbol *raiz) { if (raiz != NULL) { listar(raiz->derecha);

cout info izquierda); } }

9. Implementar la función 𝒅𝒆𝒔𝒑𝒍𝒆𝒈𝒂𝒓() utilizando el recorrido nivel por nivel (Búsqueda por amplitud). Funciona con la librería #include la cual permite crear colas (filas) de una forma ya programada void listar_nivel_por_nivel(NodoArbol *raiz) { // Caso inicial if (raiz == NULL) return; // Crea una cola vacia para el recorrido por amplitud queue colas; // Agrega la raiz e inicializa la altura de la cola colas.push(raiz); while (true) { // contadorNodos (tamaño de la cola) indica el numero de // nodos en el nivel actual. int contadorNodos = colas.size(); if (contadorNodos == 0) break; // Retira todos los nodos del nivel actual y agrega todos // los nodos del siguiente nivel while (contadorNodos > 0) { NodoArbol *nodo = colas.front(); cout info izquierda != NULL) colas.push(nodo->izquierda); if (nodo->derecha != NULL) colas.push(nodo->derecha); contadorNodos--; } cout