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 X2 X3 X4
X1 50 X2 X3 30 X4 X5 70 X6 X7 15 X8 X9 40 NULL
X5 X6 X7 X8 X9
X10 55 X11 NULL 80 NULL NULL 10 NULL X14 20 NULL X12 35 NULL
X10 X11 X12 X13 X14
NULL 52 NULL NULL 60 NULL NULL 32 NULL 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 60 S
X10 X1 NULL X0 20 X8 X3 X8 20 S
X5 X2 NULL X0 30 X1 X3 X1 false 30
X2 X3 NULL X1
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 << "Ingrese el valor del nodo a insertar: ";
cin >> 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 << "El nodo a agregar ya existe" << endl;
}
3. Decir de qué manera el destructor (~ABB()) de la clase ABB recorre el árbol.
R/: Postorden. Se recorre en postorden el subárbol izquierdo del nodo raíz, luego se recorre
en postorden el subárbol derecho del nodo raíz y finalmente se elimina el nodo raíz del árbol.
4. Proponer e implementar otra forma de recorrer el árbol dentro del destructor.
R/: La otra forma sencilla de implementar otra forma de recorrer el árbol dentro del destructor
es simplemente invirtiendo las llamadas a la función recursiva por lo cual queda en postorden
converso. Se recorre en postorden el subárbol derecho del nodo raíz, recorre en postorden el
subárbol izquierdo del nodo raíz y finalmente se elimina el nodo raíz del árbol.
~ABB() {
cout << "Se ingreso al destructor" << endl;
borrar_nodos(raiz);
cout << "Se salio del destructor" << endl;
system("pause");
}
void borrar_nodos(NodoArbol *raiz) {
if (raiz != NULL) {
//Aqui se invirtio el orden de llamada recursiva
borrar_nodos(raiz->derecha);
borrar_nodos(raiz->izquierda);
cout << "Destructor de " << raiz->info << endl;
delete raiz;
}
}
5. Decir con que nodo se reemplaza el nodo eliminado (con el sucesor o con el predecesor) cuando
se elimina un nodo que tiene (2) hijos.
R/: En el algoritmo dado se reemplaza con el predecesor.
6. Si en el punto anterior el remplazo se hizo con el sucesor modifique la función 𝑒𝑙𝑖𝑚𝑖𝑛𝑎𝑟_𝑛𝑜𝑑𝑜()
haciendo el remplazo con el predecesor o viceversa.
R/: En el algoritmo dado el reemplazo se hizo realmente con el predecesor y no con el sucesor,
por lo que el algoritmo solo estaba implementado para trabajar con el predecesor, por lo
tanto, el siguiente trozo de código muestra cómo realizar algo similar pero usando el sucesor.
aux2 = aux1; //con el sucesor
temp = aux1->derecha;
b = true;
while (temp->izquierda != NULL) {
aux2 = temp;
temp = temp->izquierda;
b = false;
}
aux1->info = temp->info;
if (b == true) aux1->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 << raiz->info << endl;
listar(raiz->izquierda);
}
}
9. Implementar la función 𝒅𝒆𝒔𝒑𝒍𝒆𝒈𝒂𝒓() utilizando el recorrido nivel por nivel (Búsqueda por
amplitud).
Funciona con la librería #include <queue> 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<NodoArbol *> 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 << nodo->info << " ";
colas.pop();
if (nodo->izquierda != NULL)
colas.push(nodo->izquierda);
if (nodo->derecha != NULL)
colas.push(nodo->derecha);
contadorNodos--;
}
cout << endl;
}
}
