Árboles Binarios de Búsqueda (ABB) en C++: Implementación y Operaciones

Contar el Número de Nodos en un ABB

El siguiente código en C++ muestra cómo contar el número de nodos en un árbol binario de búsqueda (ABB).

template<class DATO>
const int ABB<DATO>::NumeroNodos()
{
    contador = 0;
    auxContador(raiz); // Función auxiliar
    return contador;
}

La función NumeroNodos utiliza una función auxiliar recursiva, auxContador, para realizar el conteo.

template<class DATO>
void ABB<DATO>::auxContador(Nodo<DATO> *nodo)
{
    contador++;  // Otro nodo
    // Continuar recorrido
    if(nodo->izquierdo) auxContador(nodo->izquierdo);
    if(nodo->derecho)  auxContador(nodo->derecho);
}

La función auxContador recorre el árbol en preorden, incrementando el contador por cada nodo visitado.

Calcular la Altura de un ABB

El siguiente código calcula la altura de un ABB, que se define como la altura de su nodo de mayor altura.

template<class DATO>
const int ABB<DATO>::AlturaArbol()
{
    altura = 0;
    auxAltura(raiz, 0); // Función auxiliar
    return altura;
}

La función AlturaArbol utiliza una función auxiliar recursiva, auxAltura, para calcular la altura.

template<class DATO>
void ABB<DATO>::auxAltura(Nodo<DATO> *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;
}

La función auxAltura recorre el árbol en postorden, actualizando la altura solo en los nodos hoja cuya altura sea mayor que la altura actual del árbol.

Insertar un Dato en un ABB

El siguiente código muestra cómo insertar un nuevo dato en un ABB.

template<class DATO>
void ABB<DATO>::Insertar(const DATO dat)
{
    Nodo<DATO> *padre = NULL;
    actual = raiz;
    // Buscar el dato 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 el dato ya existe, no se hace nada
    if(!Vacio(actual)) return;
    // Si el árbol está vacío, el nuevo nodo será la raíz
    if(Vacio(padre)) raiz = new Nodo<DATO>(dat);
    // Si el dato es menor que el padre, se inserta a la izquierda
    else if(dat < padre->dato) padre->izquierdo = new Nodo<DATO>(dat);
    // Si el dato es mayor que el padre, se inserta a la derecha
    else if(dat > padre->dato) padre->derecho = new Nodo<DATO>(dat);
}

La función Insertar busca la posición correcta para el nuevo dato y lo inserta como un nuevo nodo hoja.

Eliminar un Elemento de un ABB

El siguiente código muestra cómo eliminar un elemento de un ABB.

template<class DATO>
void ABB<DATO>::Borrar(const DATO dat)
{
    Nodo<DATO> *padre = NULL;
    Nodo<DATO> *nodo;
    DATO aux;
    actual = raiz;
    // Buscar el dato 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)
                    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
                padre = actual;
                // Buscar el nodo que reemplazará al actual
                if(actual->derecho) {
                    nodo = actual->derecho;
                    while(nodo->izquierdo) {
                        padre = nodo;
                        nodo = nodo->izquierdo;
                    }
                } else {
                    nodo = actual->izquierdo;
                    while(nodo->derecho) {
                        padre = nodo;
                        nodo = nodo->derecho;
                    }
                }
                // Intercambiar los valores
                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;
        }
    }
}

La función Borrar busca el nodo a eliminar y lo elimina, manteniendo la estructura del ABB. Se consideran tres casos: eliminar un nodo hoja, eliminar un nodo con un hijo y eliminar un nodo con dos hijos.