Tree_Ex.h

Ir a la documentación de este archivo.

// Tree_Ex.h (c) 2004 adolfo@di-mare.com

/** \file Tree_Ex.h
    Algunas funciones de ejemplos de uso de la clase Arbol.
*/

#ifndef Tree_Ex_h
#define Tree_Ex_h

#include "Tree_L.h"

#include <iostream>
#include <iomanip>
#include <cassert>
#include <string>

/// Definido por la biblioteca C++ estándar
namespace std {} // Está acá para que Doxygen lo documente

using namespace std; // cout

void Print( Tree& T, unsigned indent=0, unsigned num=0 );
void Ztree_Print( Tree & T, string s="", unsigned level = 0, bool last_child = true);

unsigned My_Count(Tree& T);
unsigned Count_Children ( Tree & T );

void Mirror( Tree& T );
bool Ancestor( Tree & Child, Tree & Father );

unsigned Height( Tree & T );
unsigned Depth(  Tree & T );

/** Incrementa \c "n" en el número de hijos que tiene el sub-árbol cuya raíz es \c "T"

    - Cambia el valor de \c "n"
    - No cuenta a la raíz de \c "T"
    - Usualmente se invoca así: \code { n = 1; My_Count0(T, n); } \endcode

    \pre <code> ! T. Empty() </code>
*/
void My_Count0(Tree& T, unsigned & n) {
    for (unsigned i=T.Leftmost_N(); i <= T.Rightmost_N(); ++i) {
        if (! T.Child(i).Empty() ) {
            ++n; // cuenta a este hijo
            My_Count0( T.Child(i), n );
        }
    }
}

/// Retorna la cantidad de valores almacenados en el árbol
unsigned My_Count(Tree& T) {
    if (T.Empty()) {
        return 0;
    } else {
        unsigned n = 1; // comienza contando en uno...
        My_Count0(T, n); // ... porque Count0() no cuenta la raíz
        return n;
    }
}

/// Retorna la cantidad de hijos de "T"
unsigned Count_Children ( Tree & T ) {
        Tree L_Child = T.Leftmost();
    if ( L_Child.Empty() ) {
        return 0; // como no hay hijo más izquierdo ==> se terminó el trabajo
    }

    unsigned n = 1;
    Tree R_Child = T.Rightmost();
    Tree&  Child = L_Child;
    for (;;) {
        if (Child == R_Child) {
            break;
        } else {
            ++n;
        }
        Child = Child.Right_Sibling();
    }
    return n;
}
/// Compara recursivamente los árboles \c "p" y \c "q"
bool Comp(Tree& p, Tree& q) {
    if ( p.Same(q) ) {
        return true;
    }
    if ( p.Empty() || q.Empty() ) { // son diferentes...
        return false; // ...pues sólo 1 está vácio
    }
    if ( p.Child_Number() != q.Child_Number() ) {
        return false; // valor diferente en la raíz
    }
    if ( ! (p.Data() == q.Data()) ) {
        return false; // valor diferente en la raíz
    }

    // A comparar a todos los hijos
    unsigned rp = p.Rightmost_N(), lp = p.Leftmost_N();
    unsigned rq = q.Rightmost_N(), lq = q.Leftmost_N();
    if ((lp != lq) || (rp != rq)) {
        return false;
    }
    for (unsigned i=lp; i<=rp ; ++i) {
        if (! Comp(p.Child(i), q.Child(i)) ) {
            return false;
        }
    }

    return true; // pues nunca encontró nodos diferentes
}

/** Graba en \c "cout" el contenido del árbol \c "T"

    - Indenta a los hijos \c "indent" espacios dobles
    - Numera a los hijos a partir de \c "num" usando 2 dígitos
    - Usualmente se invoca así: \c Print(T);
*/
void Print( Tree& T, unsigned indent, unsigned num ) {

    if ( T.Empty() ) {
        return;
    }

    cout << endl; // indenta doble espacio
    for (unsigned i = 0; i < indent; ++i) {
        cout << ' ' << ' ';
    }

    cout << '[' << setfill('0') << setw(2) << num << "]==> " << *T;

    Tree Child = T.Leftmost();
    while ( ! Child.Empty() ) {
        Print( Child, indent+1, Child.Child_Number() );
        Child = Child.Right_Sibling();
    }
}

/// Cambia las letras de cajita para que el árbol de \c Ztree_Print() se vea bonito en DOS
/// \post No funciona porque Win <==> \c cout convierten a su antojo las letras
string DOS_string(string& s) {

    if      (s == "¦  ") { return "À  "; }
    else if (s == "+--") { return "ÃÄÄ"; }
    else if (s == "+--") { return "ÀÄÄ"; }
    else return s;  // me dio pereza obligarlo a funcionar
}

/** Graba en \c "cout" el contenido de "T" de la forma en que Ztree.com despliega un árbol

    - "level" indica que el nivel de anidamiento desde la raíz hasta el nodo
    - "last_child" indica se éste es el último hijo de su padre

    \remarks Forma usual de invocación: \c Ztree_Print( T );
*/
void Ztree_Print( Tree & T, string s, unsigned level, bool last_child) {
    if ( T.Empty() ) {
        return; // se sale si el árbol está vacío
    }

    cout << s << T.Data() << endl;

    Tree L_Child = T.Leftmost();
    if ( L_Child.Empty() ) { // Si no hay hijo más izquierdo
        return; // ==> no hay hijos ==> se terminó el trabajo
    }
    if (level > 0) {
        if (last_child) {
            s.resize ( s.size () - 3 );
            s += "   ";
        } else {
            s.resize ( s.size () - 3 );
            s += "|  ";
        }
    }

    s += "|  ";
    Tree R_Child = T.Rightmost();
    Tree&  Child = L_Child;
    for (;;) {
        if (Child == R_Child) { // Al último le hace un quiebre cuadradito
            s.resize ( s.size () - 3 );
            s += "+--";
            Ztree_Print(Child, s, level+1, true);
            s.resize ( s.size () - 3 );
            s += "   ";
            break;
        } else {
            s.resize ( s.size () - 3 );
            s += "|--";
            Ztree_Print(Child, s, level+1, false);
            s.resize ( s.size () - 3 );
            s += "   ";
        }
        Child = Child.Right_Sibling();
    }
}

/** Convierte a \c "T" en su sub-árbol espejo, en el que recursivamente los hijos
    quedan en orden inverso del orden en el que aparecían originalmente en \c "T"

    \code
           a                a
          /|\              /|\
        / / \ \          / / \ \
       b  c d  e        e  d c  b
      /|\     /|\      /|\     /|\
     f g h   i j k    k j i   h g f
              / \      / \
              l m      m l
               / \    / \
               n o    o n
    \endcode
*/
void Mirror( Tree& T ) {
    if ( T.Empty() ) {
        return; // se sale si el árbol está vacío
    }

    Tree Child = T.Leftmost();
    while ( ! Child.Empty() ) { // recursión para cambiar a todos los hijos
        Mirror( Child );
        Child = Child.Right_Sibling();
    }

    unsigned N = T.Rightmost_N();
    Tree     Ti, Tn_i;           // [0] [1] [2] [3] [4]    N == 4
    unsigned i, Mid = (N+1) / 2; //  i   i < 2 ==  Mid ==> 2 == 4/2 == 5/2
    for (i=0; i<Mid; ++i) { // Intercambia los hijos i <==> N - i
        #if (0)
        { // dice qué hizo
            cout << endl; Print(T);
            Tree Ti   = T.Child( i );
            Tree Tn_i = T.Child( N - i );
            cout << endl;
            string sTi ="[]"; string sTn_i = "[]";
            if (!Ti.Empty()) sTi=*Ti;
            if (!Tn_i.Empty()) sTn_i=*Tn_i; unsigned DT = 2+Depth(T);
            for (unsigned j=0; j<DT; ++j) { cout << "  "; }
                cout << "[\"" << *T << "\"].Graft(" << i   << ",\"" << sTn_i << "\")" << endl;
            for (unsigned j=0; j<DT; ++j) { cout << "  "; }
                cout << "[\"" << *T << "\"].Graft(" << N-i << ",\"" << sTi   << "\")" << endl;
        }
        #endif
        Ti   = T.Child( i );
        Tn_i = T.Child( N - i );
        T.Graft( i,     Tn_i );     // assert(( Ti.Empty() ? true : Ti.Father().Empty() ));
        T.Graft( N - i, Ti   );
    }
    // cout << "# == " << T.Count() << endl; Print(T);
}

/** Retorna true si \c "Father" es un ancestro de \c "Child"

    - La raíz no tiene ancestros.
    - Un árbol vacío no tiene ancestros.
*/
bool Ancestor( Tree & Child, Tree & Father ) {
    if ( Child.Empty() ) {
        return false;
    }
    Tree T = Child.Father();
    while ( ! T.Empty() ) {
        if ( T.Same( Father ) ) { // No es válido usar la comparación profunda por valor
            return true;
        }
        T = T.Father();
    }
    return false;
}

/** Retorna true cuando el sub-árbol \c "T" es una hoja,
    o sea, cuando "T" no tiene hijos.

    - Un sub-árbol vacío no es una hoja porque no tiene raíz.
*/
inline bool Is_Leaf( Tree & T ) {
    return ( ! T.Empty() && T.Leftmost().Empty() );
} // Is_Leaf()

/** Retorna true cuando el sub-árbol \c "T" es una raíz,
    o sea, cuando "T" no tiene padre.

    - Un sub-árbol vacío no es una raíz porque no tiene raíz.
*/
inline bool Is_Root( Tree & T ) {
    return ( !T.Empty() && !T.Father().Empty() );
} // Is_Root()

/** Calcula la altura de sub-árbol.

  - Esta función es el paso recursivo necesario para implementar \c Height()
  - Recorre recursivamente el árbol y recuerda la máxima profundidad encontrada en \c "max".
  - \c "actual" es la profundidad del nodo actual.
*/
void Height0( Tree & T, unsigned &max, unsigned actual) {
    if ( T.Empty() ) {
        if (max < actual) {
            max = actual; // se deja el más grande de los 2
        }
        return;
    } else {
        for (unsigned i=T.Leftmost_N(); i <= T.Rightmost_N(); ++i) {
            Height0(T.Child(i), max, actual+1);
        }
        return;
    }
} // Height0()

/** Retorna la altura de \c "T"

  - La altura es la distanca desde \c "T" hasta la hoja más profunda en el
    sub-árbol formado por todos los descendientes de \c "T".
  - La altura de un nodo hoja siempre es cero.
  - <code> [ Is_Leaf(T) == true ] ==> [ Height(T) == 0 ] </code>

    \code
                                     [ Depth() Height() ]
    a [0 4]                a               [0 4]
    |--b [1 1]             |--b            [1 1]
    |  |--f [2 0]          |  |--f         [2 0]
    |  |--g [2 0]          |  |--g         [2 0]
    |  +--h [2 0]          |  +--h         [2 0]
    |--c [1 0]             |--c            [1 0]
    |--d [1 0]             |--d            [1 0]
    +--e [1 3]             +--e            [1 3]
       |--i [2 0]             |--i         [2 0]
       |--j [2 2]             |--j         [2 2]
       |  |--l [3 0]          |  |--l      [3 0]
       |  +--m [3 1]          |  +--m      [3 1]
       |     |--n [4 0]       |     |--n   [4 0]
       |     +--o [4 0]       |     +--o   [4 0]
       +--k [2 0]             +--k         [2 0]
    \endcode
*/
inline unsigned Height( Tree & T ) {
    unsigned actual,  max;
    max    = 0;
    actual = 0;
    Height0( T, max, actual );
    max = ( max > 0 ? max-1 : 0 );
    return max;
} // Height()

/** Retorna la longitud del camino desde \c "T" hasta la raíz del árbol.

    - Retorna la profundidad del sub-árbol respecto de su raíz
    - La profundidad de la raíz del árbol es cero.
    - <code> T.Empty() ==> [ Depth(T) == 0 ] </code>
*/
unsigned Depth(  Tree & T ) {
    if ( T.Empty() ) {
        return 0;
    }
    unsigned n = 0;
    Tree F = T;
    do {
        F = F.Father();
        ++n;
    } while ( ! F.Empty() );
    return n-1;
} // Depth()

/// Retorna la máxima cantidad de hijos que tienen \c "T" y todos sus sub-árboles
unsigned Arity( Tree & T ) {
    if ( T.Empty() ) {
        return 0;
    }
    unsigned max = 0, n_children = 0;
    Tree Child = T.Leftmost();
    while ( ! Child.Empty() ) {
        unsigned n = Arity( Child );
        max = max > n ? max : n;
        n_children++;
        Child = Child.Right_Sibling();
    }
    return max > n_children ? max : n_children;
} // Arity()

/// Retorna \c "true" cuando el árbol es binario
bool Is_Binary( Tree & T ) {
    return Arity(T) <= 2;
}

#include <climits> // para UINT_MAX
/** Esta función retorna el número de aristas que hay en
    el único camino que une la raíz de \c "n1" con la de \c "n2".
    - Si \c "n1" y \c "n2" pertenecen a árboles diferente,
      retorna \c UINT_MAX == \e infinito
*/
unsigned Length( Tree &n1, Tree &n2 ) {
/*
    1) Calcula L1 = Depth(n1)
    2) Calcula L2 = Depth(n2)
    3) Sincroniza profundidades, caminando hacia arriba en L2-L1 pasos (si L2>L1)
       para tratar de encontrar un ancestro comun "c" a "n1" y "n2":
                     r
                    /
                   /
            /     c         \
            |    / \        |
         L1 |   /   \    L2 |
            \  n1    \      |    \
                      \     |    | L2 - L1
                      n2    /    /

    4) En  un ciclo, pasa al padre de "n1" junto con el de "n2", buscando encontrar
       "c" un ancestro común. Cuenta [m == # iteraciones del ciclo]
    5) Si se llega a "r", lo que ocurre cuando el padre resulta ser el árbol vacío,
       quiere decir que "n1" y "n2" están en árboles diferentes, por lo que la distancia
       entre ellos no existe, o es infinita.
    6) Si existe el padre común "c", la distancia entre "n1" y "n2" es:
       2 * ( m ) + ( L2 - L1 )
*/
    bool Funcion_NO_implementada = false;
    assert( Funcion_NO_implementada );
    return UINT_MAX;
} // Length()

/** Transforma el árbol \c "T" que contiene como sub-árbol a\c "sT"
    para que la raíz de \c "T" sea \c "sT".

    - No hace nada si \c <code> T.Father().Emtpy() </code> [\c "T" ya es la raíz del árbol]
    - Traslada a \c Father() para que sea el hijo más izquierdo de manera que ocupe
      la posición "n-1" donde <code> n == Leftmost().Child_Number()" </code>
    - Traslada a los hermanos izquierdos para que estén antes de la antigua raíz
    - Traslada a los hermanos derechos para que estén después de la antigua raíz

    \code
           a                      e
          /|\                    /|\
        / / \ \                / / \ \
       b  c d  e              a  i j  k
      /|\     /|\            /|\
     f g h   i j k          b c d
                           /|\
                          f g h
    \endcode
     
    \pre
        - <code> Leftmost().Child_Number() > 0 </code>
        - <code> Ancestor(sT, T) == true </code>
*/
void New_Root( Tree& T, Tree &sT ) {
    bool Funcion_NO_implementada = false;
    assert( Funcion_NO_implementada );
    return;

    Tree F = T.Father();
    if ( F.Empty() ) {
        return;
    }
    unsigned n = sT.Child_Number();
    if (n == 0) {
        return;
    }
    Tree saveS = sT;
    Tree newT = T;
    F.Graft(n, Tree( ) ); // elimina "sT" del árbol "T"
    sT.Graft(n-1, newT);
    T.Move( sT );
    sT = saveS;
} // New_Root()

#endif  // Tree_Ex_h

// EOF: Tree_Ex.h

---