Implementación de Recorridos y Operaciones en Árboles Binarios AVL en C++

Implementación de Árboles Binarios AVL

Recorridos del Árbol

A continuación, se presentan las funciones para realizar recorridos en un árbol AVL, aplicando una función func con el prototipo: template<class DATO> void func(DATO&);.

Inorden

template<class DATO>
void AVL<DATO>::InOrden(void (*func)(DATO&, int), Nodo<DATO> *nodo, bool r)
{
   if(r) nodo = raiz;
   if(nodo->izquierdo) InOrden(func, nodo->izquierdo, false);
   func(nodo->dato, nodo->FE);
   if(nodo->derecho) InOrden(func, nodo->derecho, false);
}

Preorden

template<class DATO>
void AVL<DATO>::PreOrden(void (*func)(DATO&, int), Nodo<DATO> *nodo, bool r)
{
   if(r) nodo = raiz;
   func(nodo->dato, nodo->FE);
   if(nodo->izquierdo) PreOrden(func, nodo->izquierdo, false);
   if(nodo->derecho) PreOrden(func, nodo->derecho, false);
}

Postorden

template<class DATO>
void AVL<DATO>::PostOrden(void (*func)(DATO&, int), Nodo<DATO> *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, nodo->FE);
}

Operaciones de Búsqueda y Altura

Buscar un valor en el árbol

template<class DATO>
bool AVL<DATO>::Buscar(const DATO dat)
{
   actual = raiz;
   while(!Vacio(actual)) {
      if(dat == actual->dato) return true; // Dato encontrado
      else if(dat > actual->dato) actual = actual->derecho;
      else if(dat < actual->dato) actual = actual->izquierdo;
   }
   return false; // No está en el árbol
}

Calcular la altura de un nodo específico

template<class DATO>
int AVL<DATO>::Altura(const DATO dat)
{
   int altura = 0;
   actual = raiz;
   while(!Vacio(actual)) {
      if(dat == actual->dato) return altura; // Dato 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 el árbol
}

Gestión de Nodos y Estructura

Contar el número de nodos

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

// Función auxiliar recursiva (preorden) para contar nodos
template<class DATO>
void AVL<DATO>::auxContador(Nodo<DATO> *nodo)
{
   contador++;  // Otro nodo
   if(nodo->izquierdo) auxContador(nodo->izquierdo);
   if(nodo->derecho)   auxContador(nodo->derecho);
}

Calcular la altura total del árbol

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

// Función auxiliar recursiva (postorden) para calcular la altura máxima
template<class DATO>
void AVL<DATO>::auxAltura(Nodo<DATO> *nodo, int a)
{
   if(nodo->izquierdo) auxAltura(nodo->izquierdo, a+1);
   if(nodo->derecho)   auxAltura(nodo->derecho, a+1);
   // Si es un nodo hoja y su altura es mayor que la actual, actualizamos
   if(EsHoja(nodo) && a > altura) altura = a;
}