Plantilla de Árbol Binario de Búsqueda en C++

 

1. Estructura General

Clase ArbolABB:
Contiene:

• Una clase interna Nodo para representar los nodos del árbol.

• Punteros raiz y actual para gestionar navegación e inserción.

• Atributos contador y altura como variables auxiliares.

2. Funcionalidades Implementadas

Función	Propósito
Insertar	Inserta elementos respetando el orden ABB.
Borrar	Elimina un nodo (caso hoja, un hijo, dos hijos).
Buscar	Devuelve true/false si encuentra un valor.
InOrden	Recorrido simétrico (izq - nodo - der).
PreOrden	Recorrido en preorden (nodo - izq - der).
PostOrden	Recorrido en postorden (izq - der - nodo).
NumeroNodos	Cuenta todos los nodos del árbol.
AlturaArbol	Devuelve la altura máxima (nivel más profundo).
Altura	Devuelve la profundidad de un nodo específico.

---

3. Comentario Didáctico y de Diseño

• Uso de clases anidadas: correcta encapsulación del nodo.

• Constructores y destructores: bien definidos. El destructor aplica poda recursiva.

• Manejo de memoria dinámica: correcto con new y delete, aunque no se usa smart pointers (esto puede modernizarse con std::unique_ptr).

• No se reutiliza código entre los recorridos (inorden, preorden, postorden), aunque puede unificarse con una función recursiva con estrategia como parámetro.

• Evita duplicados en inserción, lo cual es adecuado para ABB (ver línea if (!Vacio(actual)) return;).

• Inserta múltiples nodos en main, algunos duplicados, pero no se agregan.

Observaciones Técnicas y Mejora

 Fortalezas

• Correcto manejo de punteros y recursión.

• Inclusión de funciones para métricas del árbol (número de nodos, altura).

• Bien estructurado y comentado.

 Posibles mejoras

1. Modernización de C++:

   • Reemplazar NULL por nullptr.

   • Usar std::function<int&(int&)> en vez de punteros a funciones crudas.

   • Uso de unique_ptr para gestión automática de memoria.

2. Robustez del recorrido:

   • Validar que nodo no sea NULL en InOrden, PreOrden y PostOrden antes de acceder a sus punteros hijos.

3. Separar responsabilidades:

   • Las funciones auxContador, auxAltura, etc., podrían estar mejor encapsuladas si fueran estáticas o externas (dependiendo del uso).

4. Control de excepciones:

   • No hay manejo para errores como acceso a actual->dato sin validar si actual != NULL.

5. Optimización del borrado:

   • El método Borrar intercambia valores en vez de reorganizar punteros, lo cual es válido pero puede ser menos claro. Puede aplicarse una implementación con sustituto directo.

Ejemplo de Estructura del Árbol Insertado

                10

              /    \

             5      12

            / \       \

           4   7       14

          /   / \     /  \

         3   6   9   13  15

        /         /

       2         8

      /

     1

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342

// Plantilla de Arbol Binario de Búsqueda en C++ #include <iostream> using namespace std; class ArbolABB { private: //// Clase local de Lista para Nodo de ArbolBinario: class Nodo { public: // Constructor: Nodo(const int dat, Nodo *izq=NULL, Nodo *der=NULL) : dato(dat), izquierdo(izq), derecho(der) {} // Miembros: int dato; Nodo *izquierdo; Nodo *derecho; }; // Punteros de la lista, para cabeza y nodo actual: Nodo *raiz; Nodo *actual; int contador; int altura; public: // Constructor y destructor básicos: ArbolABB() : raiz(NULL), actual(NULL) {} ~ArbolABB() { Podar(raiz); } // Insertar en árbol ordenado: void Insertar(const int dat); // Borrar un elemento del árbol: void Borrar(const int dat); // Función de búsqueda: bool Buscar(const int dat); // Comprobar si el árbol está vacío: bool Vacio(Nodo *r) { return r==NULL; } // Comprobar si es un nodo hoja: bool EsHoja(Nodo *r) { return !r->derecho && !r->izquierdo; } // Contar número de nodos: const int NumeroNodos(); const int AlturaArbol(); // Calcular altura de un int: int Altura(const int dat); // Devolver referencia al int del nodo actual: int &ValorActual() { return actual->dato; } // Moverse al nodo raiz: void Raiz() { actual = raiz; } // Aplicar una función a cada elemento del árbol: void InOrden(void (*func)(int&) , Nodo *nodo=NULL, bool r=true); void PreOrden(void (*func)(int&) , Nodo *nodo=NULL, bool r=true); void PostOrden(void (*func)(int&) , Nodo *nodo=NULL, bool r=true); private: // Funciones auxiliares void Podar(Nodo* &); void auxContador(Nodo*); void auxAltura(Nodo*, int); }; // Poda: borrar todos los nodos a partir de uno, incluido void ArbolABB::Podar(Nodo* &nodo) { // Algoritmo recursivo, recorrido en postorden if(nodo) { Podar(nodo->izquierdo); // Podar izquierdo Podar(nodo->derecho); // Podar derecho delete nodo; // Eliminar nodo nodo = NULL; } } // Insertar un int en el árbol ABB void ArbolABB::Insertar(const int dat) { Nodo *padre = NULL; actual = raiz; // Buscar el int en el árbol, manteniendo un puntero al nodo padre while(!Vacio(actual) && dat != actual->dato) { padre = actual; if(dat > actual->dato) actual = actual->derecho; else if(dat < actual->dato) actual = actual->izquierdo; } // Si se ha encontrado el elemento, regresar sin insertar if(!Vacio(actual)) return; // Si padre es NULL, entonces el árbol estaba vacío, el nuevo nodo será // el nodo raiz if(Vacio(padre)) raiz = new Nodo(dat); // Si el int es menor que el que contiene el nodo padre, lo insertamos // en la rama izquierda else if(dat < padre->dato) padre->izquierdo = new Nodo(dat); // Si el int es mayor que el que contiene el nodo padre, lo insertamos // en la rama derecha else if(dat > padre->dato) padre->derecho = new Nodo(dat); } // Eliminar un elemento de un árbol ABB void ArbolABB::Borrar(const int dat) { Nodo *padre = NULL; Nodo *nodo; int aux; actual = raiz; // Mientras sea posible que el valor esté en el árbol while(!Vacio(actual)) { if(dat == actual->dato) { // Si el valor está en el nodo actual if(EsHoja(actual)) { // Y si además es un nodo hoja: lo borramos if(padre) // Si tiene padre (no es el nodo raiz) // Anulamos el puntero que le hace referencia if(padre->derecho == actual) padre->derecho = NULL; else if(padre->izquierdo == actual) padre->izquierdo = NULL; delete actual; // Borrar el nodo actual = NULL; return; } else { // Si el valor está en el nodo actual, pero no es hoja // Buscar nodo padre = actual; // Buscar nodo más izquierdo de rama derecha if(actual->derecho) { nodo = actual->derecho; while(nodo->izquierdo) { padre = nodo; nodo = nodo->izquierdo; } } // O buscar nodo más derecho de rama izquierda else { nodo = actual->izquierdo; while(nodo->derecho) { padre = nodo; nodo = nodo->derecho; } } // Intercambiar valores de no a borrar u nodo encontrado // y continuar, cerrando el bucle. El nodo encontrado no tiene // por qué ser un nodo hoja, cerrando el bucle nos aseguramos // de que sólo se eliminan nodos hoja. aux = actual->dato; actual->dato = nodo->dato; nodo->dato = aux; actual = nodo; } } else { // Todavía no hemos encontrado el valor, seguir buscándolo padre = actual; if(dat > actual->dato) actual = actual->derecho; else if(dat < actual->dato) actual = actual->izquierdo; } } } // Recorrido de árbol en inorden, aplicamos la función func, que tiene // el prototipo: // void func(int&); void ArbolABB::InOrden(void (*func)(int&) , Nodo *nodo, bool r) { if(r) nodo = raiz; if(nodo->izquierdo) InOrden(func, nodo->izquierdo, false); func(nodo->dato); if(nodo->derecho) InOrden(func, nodo->derecho, false); } // Recorrido de árbol en preorden, aplicamos la función func, que tiene // el prototipo: // void func(int&); void ArbolABB::PreOrden(void (*func)(int&), Nodo *nodo, bool r) { if(r) nodo = raiz; func(nodo->dato); if(nodo->izquierdo) PreOrden(func, nodo->izquierdo, false); if(nodo->derecho) PreOrden(func, nodo->derecho, false); } // Recorrido de árbol en postorden, aplicamos la función func, que tiene // el prototipo: // void func(int&); void ArbolABB::PostOrden(void (*func)(int&), Nodo *nodo, bool r) { if(r) nodo = raiz; if(nodo->izquierdo) PostOrden(func, nodo->izquierdo, false); if(nodo->derecho) PostOrden(func, nodo->derecho, false); func(nodo->dato); } // Buscar un valor en el árbol bool ArbolABB::Buscar(const int dat) { actual = raiz; // Todavía puede aparecer, ya que quedan nodos por mirar while(!Vacio(actual)) { if(dat == actual->dato) return true; // int encontrado else if(dat > actual->dato) actual = actual->derecho; // Seguir else if(dat < actual->dato) actual = actual->izquierdo; } return false; // No está en árbol } // Calcular la altura del nodo que contiene el int dat int ArbolABB::Altura(const int dat) { int altura = 0; actual = raiz; // Todavía puede aparecer, ya que quedan nodos por mirar while(!Vacio(actual)) { if(dat == actual->dato) return altura; // int encontrado else { altura++; // Incrementamos la altura, seguimos buscando if(dat > actual->dato) actual = actual->derecho; else if(dat < actual->dato) actual = actual->izquierdo; } } return -1; // No está en árbol } // Contar el número de nodos const int ArbolABB::NumeroNodos() { contador = 0; auxContador(raiz); // FUnción auxiliar return contador; } // Función auxiliar para contar nodos. Función recursiva de recorrido en // preorden, el proceso es aumentar el contador void ArbolABB::auxContador(Nodo *nodo) { contador++; // Otro nodo // Continuar recorrido if(nodo->izquierdo) auxContador(nodo->izquierdo); if(nodo->derecho) auxContador(nodo->derecho); } // Calcular la altura del árbol, que es la altura del nodo de mayor altura. const int ArbolABB::AlturaArbol() { altura = 0; auxAltura(raiz, 0); // Función auxiliar return altura; } // Función auxiliar para calcular altura. Función recursiva de recorrido en // postorden, el proceso es actualizar la altura sólo en nodos hojas de mayor // altura de la máxima actual void ArbolABB::auxAltura(Nodo *nodo, int a) { // Recorrido postorden if(nodo->izquierdo) auxAltura(nodo->izquierdo, a+1); if(nodo->derecho) auxAltura(nodo->derecho, a+1); // Proceso, si es un nodo hoja, y su altura es mayor que la actual del // árbol, actualizamos la altura actual del árbol if(EsHoja(nodo) && a > altura) altura = a; } // Función de prueba para recorridos del árbol void Mostrar(int &d) { cout << d << ","; } int main() { // Un árbol de enteros ArbolABB ArbolInt; // Inserción de nodos en árbol: ArbolInt.Insertar(10); ArbolInt.Insertar(5); ArbolInt.Insertar(12); ArbolInt.Insertar(4); ArbolInt.Insertar(7); ArbolInt.Insertar(3); ArbolInt.Insertar(6); ArbolInt.Insertar(9); ArbolInt.Insertar(8); ArbolInt.Insertar(11); ArbolInt.Insertar(14); ArbolInt.Insertar(13); ArbolInt.Insertar(2); ArbolInt.Insertar(1); ArbolInt.Insertar(15); ArbolInt.Insertar(10); ArbolInt.Insertar(17); ArbolInt.Insertar(18); ArbolInt.Insertar(16); cout << "Altura de arbol " << ArbolInt.AlturaArbol() << endl; // Mostrar el árbol en tres ordenes distintos: cout << "InOrden: "; ArbolInt.InOrden(Mostrar); cout << endl; cout << "PreOrden: "; ArbolInt.PreOrden(Mostrar); cout << endl; cout << "PostOrden: "; ArbolInt.PostOrden(Mostrar); cout << endl; // Borraremos algunos elementos: cout << "N nodos: " << ArbolInt.NumeroNodos() << endl; ArbolInt.Borrar(5); cout << "Borrar 5: "; ArbolInt.InOrden(Mostrar); cout << endl; ArbolInt.Borrar(8); cout << "Borrar 8: "; ArbolInt.InOrden(Mostrar); cout << endl; ArbolInt.Borrar(15); cout << "Borrar 15: "; ArbolInt.InOrden(Mostrar); cout << endl; ArbolInt.Borrar(245); cout << "Borrar 245: "; ArbolInt.InOrden(Mostrar); cout << endl; ArbolInt.Borrar(4); cout << "Borrar 4: "; ArbolInt.InOrden(Mostrar); ArbolInt.Borrar(17); cout << endl; cout << "Borrar 17: "; ArbolInt.InOrden(Mostrar); cout << endl; // Veamos algunos parámetros cout << "N nodos: " << ArbolInt.NumeroNodos() << endl; cout << "Altura de 1 " << ArbolInt.Altura(1) << endl; cout << "Altura de 10 " << ArbolInt.Altura(10) << endl; cout << "Altura de arbol " << ArbolInt.AlturaArbol() << endl; cin.get(); return 0; }