Ensamblador

Escrito el 27 de Mayo de 2010 en español con un tamaño de 5,21 KB

ARBOL BINARIO AVL 5

// Recorrido de árbol en inorden, aplicamos la función func, que tiene
// el prototipo:
// template<class DATO> void func(DATO&);
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);
}
// Recorrido de árbol en preorden, aplicamos la función func, que tiene
// el prototipo:
// template<class DATO> void func(DATO&);
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);
}
// Recorrido de árbol en postorden, aplicamos la función func, que tiene
// el prototipo:
// template<class DATO> void func(DATO&);
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);
}
// Buscar un valor en el árbol
template<class DATO>
bool AVL<DATO>::Buscar(const DATO dat)
{
   actual = raiz;
   // Todavía puede aparecer, ya que quedan nodos por mirar
   while(!Vacio(actual)) {
      if(dat == actual->dato) return true; // dato 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 dato dat
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 árbol
}

ARBOL BINARIO AVL 6

// 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 para contar nodos. Función recursiva de recorrido en
//   preorden, el proceso es aumentar el contador
template<class DATO>
void AVL<DATO>::auxContador(Nodo<DATO> *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.
template<class DATO>
const int AVL<DATO>::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
template<class DATO>
void AVL<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;
}

Entradas relacionadas: