// Bin_Tree.h (c) 2007 adolfo@di-mare.com

/** \file  Bin_Tree.h
    \brief Arbol binario implementado con referencias \c lkptr<X>

    \author Adolfo Di Mare <adolfo@di-mare.com>
    \date   2007

    - Why English names??? ==> http://www.di-mare.com/adolfo/binder/c01.htm#sc04
*/

#ifndef Bin_Tree_h
#define Bin_Tree_h  ///< Evita inclusión múltiple de \c "Bin_Tree.h"

#include "lkptr.h"
#include <iostream>

template <class E> class Bin_Tree;  // declaración hacia adelante para Bin_Tree_Node <>

/// Nodos almacenados en el árbol
template <class E>
class Bin_Tree_Node {
public:
    template <class X> friend class Bin_Tree; // Sólo el árbol se le mete a este Rep
    typedef E value_type; ///< Nombre estándar del tipo de elemento contenido
private:
    value_type                 m_data;   ///< Valor almacenado en el nodo.
    lkptr< Bin_Tree_Node <E> > m_father; ///< Nodo padre (puede ser \c NULL si es raíz).
    lkptr< Bin_Tree_Node <E> > m_left;   ///< Hijo izquierdo del árbol (\c NULL si es hoja).
    lkptr< Bin_Tree_Node <E> > m_right;  ///< Hijo derecho del árbol (\c NULL si es hoja).
private:
    /// Constructor a partir de un valor específico.
    Bin_Tree_Node( const value_type& d ) : m_data( d ), m_father(0), m_left(0), m_right(0) {}
public: // debe ser público para que otros módulos puedan destruir árboles ya construidos.
    ~Bin_Tree_Node();
}; // Bin_Tree_Node

/** Los métodos para trabajar con árboles binarios regresan "referencias" que son sub-árboles.
    - Un sub-árbol es parte del árbol, por lo que al modificar los valores del
      sub-árbol también el árbol original queda cambiado.
    - Para evitar este tipo de modificación indirecta, es necesario trabajar
      con una "copia profunda" del árbol orignal, la que se puede obtener con
      \c copyDeep().
    - Aún si el árbol original es eliminado, el sub-árbol continúa existiendo.
    - Debido a que los árboles y sub-árboles son referencias, en C++ es necesario mantener
      internamente "enlaces de referencia".

    \dontinclude test_Bin_Tree.cpp
    \skipline    test::multi_child()
    \until       }}
    \see         test_Bin_Tree<E>::test_multi_child()
*/
template <class E>
class Bin_Tree {
private:
    lkptr< Bin_Tree_Node<E> > m_root; ///< Un árbol "es" el puntero al nodo raíz.
public:
    typedef E value_type; ///< Nombre estándar del tipo de elemento contenido
    typedef const value_type& const_reference; ///< Referencia constante al objeto contenido
    typedef unsigned size_type;  ///< Nombre estándar del tipo retornado por \c size()

/// \name Constructores y destructor
//@{
public:
    Bin_Tree() : m_root(0) {} ///< Constructor de vector: el árbol queda vacío.
    // Constructor de copia (no \c const).
    // Bin_Tree( Bin_Tree& other ) : m_root(0) { m_root.get() = const_cast< Bin_Tree_Node<E>* >(other.m_root); }
    Bin_Tree(const Bin_Tree& other) : m_root( other.m_root ) { }
    Bin_Tree(const value_type & d);
    ~Bin_Tree();
private:
    /// Constructor a partir de un puntero a un nodo.
    Bin_Tree( lkptr< Bin_Tree_Node<E> >& other ) : m_root(other) { }
    /// Constructor a partir de un puntero a un nodo (puntero \c const).
    Bin_Tree( const lkptr< Bin_Tree_Node<E> >& other ) : m_root(other) { }

//@}

/// \name Operaciones básicas
//@{
public:
    bool     isEmpty() const { return (m_root.get() == 0); } ///< Retorna \c "true" si el sub-árbol está vacío
    unsigned count() const ;
    unsigned countChildren() const ;
    /// Usa \c count() para retornar la cantidad de valores almacenados en el sub-árbol.
    unsigned size () const { return count(); }
    bool     ok() const { return true; } ///< Verifica la invariante de \c Bin_Tree<E>.
    /// Usa \c ok() para verificar la invariante de la clase.
    template <class T> friend inline bool check_ok(const Bin_Tree<T>& aT);
//@}

/// \name Operaciones de borrado
//@{
public:
    /** Deja el árbol vacío.
        - Si es necesario, también elimina sus descendientes.
        - <code> T.left().erase(); // No cambia "T" porque el que cambia es "T.left()" </code>
        - <code> T.makeLeftChild( Bin_Tree<E>() );  // así sí se borra el hijo izquierdo </code>
        - <code> T.makeRightChild( Bin_Tree<E>() ); // borra el hijo derecho </code>

        \par Complejidad:
             O( \c count()  ) ==> tiempo <br>
             O( \c height() ) ==> espacio.
        \see http://www.di-mare.com/adolfo/binder/c04.htm#sc03
    */
    void erase() { m_root.release(); }
    void clear() { erase(); } ///< Sinónimo de \c erase().
//@}

/// \name Operaciones de copiado
//@{
public:
    /// Sinónimo de \c this->copy(o) (pero retorna \c *this).
    Bin_Tree& operator= ( const Bin_Tree & other ) { m_root = other.m_root; return *this; }
    void copy( const Bin_Tree & other );
    /// Usa \c changeRoot() para sustituir por \c "d" el valor almacenado en la raíz del árbol.
    Bin_Tree& operator=( const value_type & d) { changeRoot(d); return *this; }
    void move( Bin_Tree & other );
    void swap( Bin_Tree & other );
//@}

/// \name Métodos para cambiar los valores almacenados en el árbol
//@{
public:
    void changeRoot(  const value_type &d );
    void changeLeftChild( const value_type &d );
    void changeRightChild( const value_type &d );
    void makeLeftChild(  Bin_Tree T );
    void makeRightChild( Bin_Tree T );
    void releaseLeftChild( );
    void releaseRightChild( );
    void makeOrphan( );
//@}

/// \name Operaciones para usar los valores almacenados
//@{
public:
    /// Valor almacenado en la raíz del sub-árbol
    /// \pre \c !isEmpty()
    value_type& data        () const { return  m_root->m_data;   }
    /// Valor almacenado en la raíz del sub-árbol
    /// \pre \c !isEmpty()
    value_type& operator *  () const { return  m_root->m_data;   }
    /// Puntero al valor almacenado en la raíz del sub-árbol
    /// \pre \c !isEmpty()
    value_type* operator -> () const { return &(m_root->m_data); }
//@}

/// \name Operaciones de comparación
//@{
public:
    /// ¿¿¿ (p == q) ???
    template <class T> friend bool operator == (const Bin_Tree<T> &p, const Bin_Tree<T> &q);
    /// ¿¿¿ (p != q) ???
    template <class T> friend bool operator != (const Bin_Tree<T> &p, const Bin_Tree<T> &q);
    bool equals( const Bin_Tree & o ) const { return (*this)==o; } ///< ¿¿¿ (*this==o) ???
    /// Retorna \c true si \c "o" comparte la raíz con \c "*this"
    bool same( const Bin_Tree & o ) const { return m_root == o.m_root; }
//@}

/// \name Métodos para recorrer el árbol
//@{
public:
    const Bin_Tree root() const { return Bin_Tree( m_root ); } ///< Raíz del sub-árbol
    /** Acceso al padre.
        - Si el sub-árbol no tiene padre retorna el árbol vacío.
        - Como los árboles son referencias, este método no sirve para modificar
          la estructura del árbol.
    */
    Bin_Tree father() const {
        if ( m_root.get() == 0 ) { return Bin_Tree(); }
        else { return Bin_Tree( m_root->m_father ); }
    }
    /** Acceso al hijo izquierdo.
        - Si el sub-árbol no tiene hijo izquierdo retorna el árbol vacío.
        - Permite cambiar el valor del hijo izquierdo si ese sub-árbol existe.
        - No sirve para agregarle un hijo a un árbol que no tiene hijo izquierdo.
        - Para agregar un sub-árbol como hijo izquierdo es necesario usar
          \c makeLeftChild().
        - Como los árboles son referencias, este método no sirve para modificar
          la estructura del árbol.

        \dontinclude test_Bin_Tree.cpp
        \skipline    test::left_right()
        \until       }}
        \see         test_Bin_Tree<E>::test_left_right()
    */
    Bin_Tree left() const {
        if ( m_root.get() == 0 ) { return Bin_Tree(); }
    //  else if ( m_root->m_left == 0) { return Bin_Tree(); }
        else { return Bin_Tree( m_root->m_left ); }
    }

    /** Acceso al hijo derecho.
        - Si el sub-árbol no tiene hijo derecho retorna el árbol vacío.
        - Permite cambiar el valor del hijo derecho si ese sub-árbol existe.
        - No sirve para agregarle un hijo a un árbol que no tiene hijo derecho.
        - Para agregar un sub-árbol como hijo derecho es necesario usar
          \c makeRightChild().
        - Como los árboles son referencias, este método no sirve para modificar
          la estructura del árbol.

        \dontinclude test_Bin_Tree.cpp
        \skipline    test::left_right()
        \until       }}
        \see         test_Bin_Tree<E>::test_left_right()
    */
    Bin_Tree right() const {
        if ( m_root.get() == 0 ) { return Bin_Tree(); }
    //  else if ( m_root->m_right == 0) { return Bin_Tree(); }
        else { return Bin_Tree(m_root->m_right); }
    }
    /** Acceso al i-ésimo hijo del árbol.
        - Si el sub-árbol no tiene es hijo retorna el árbol vacío.
        - <code>( i == 0 )</code> ==> Hijo izquierdo.
        - <code>( i == 1 )</code> ==> Hijo derecho.
        - Como los árboles son referencias, este método no sirve para modificar
          la estructura del árbol.
    */
    Bin_Tree child(int i) const {
        if ( m_root.get() == 0 ) { return Bin_Tree(); }
        else if (i==0)           { return Bin_Tree(m_root->m_left); }
        else if (i==1)           { return Bin_Tree(m_root->m_right); }
        else                     { return Bin_Tree(); }
    }
//@}

/// \name Propiedades del árbol
//@{
public:
    /** Retorna \c "true" si el árbol no tiene padre.
        - Retorna \c "false" para un árbol vacío.

        \dontinclude test_Bin_Tree.cpp
        \skipline    test::isRoot_isLeaf()
        \until       }}
        \see         test_Bin_Tree<E>::test_isRoot_isLeaf()
    */
    bool isRoot() const { return ( m_root.get() == 0 ? false : m_root->m_father.get() == 0 ); }
    /** Retorna \c "true" si el árbol es una hoja.
        - Retorna \c "false" para un árbol vacío.

        \dontinclude test_Bin_Tree.cpp
        \skipline    test::isRoot_isLeaf()
        \until       }}
        \see         test_Bin_Tree<E>::test_isRoot_isLeaf()
    */
    bool isLeaf() const {
        return ( m_root.get() == 0 ? false : (m_root->m_left.get() == 0) && (m_root->m_right.get() == 0) );
    }
    /** Retorna \c "true" si el árbol es el hijo izquierdo de su padre.
        - Retorna \c "false" si el árbol está vacío.
        - Retorna \c "false" si el árbol no tiene padre.
        - Retorna \c "false" si el árbol es el hijo derecho de su padre.

        \dontinclude test_Bin_Tree.cpp
        \skipline    test::isLeft_isRight()
        \until       }}
        \see         test_Bin_Tree<E>::test_isLeft_isRight()
    */
    bool isLeftChild() const {
        if ( m_root.isNull() ) {
            return false; // árbol vacío
        }
        else if ( m_root->m_father.get() != 0 ) {
            Bin_Tree_Node<E> * father = m_root->m_father.get();
            return (m_root == father->m_left);
        }
        else {
            return false; // no es el hijo izquierdo
        }
    }
    /** Retorna \c "true" si el árbol es el hijo derecho de su padre.
        - Retorna \c "false" si el árbol está vacío.
        - Retorna \c "false" si el árbol no tiene padre.
        - Retorna \c "false" si el árbol es el hijo izquierdo de su padre.

        \dontinclude test_Bin_Tree.cpp
        \skipline    test::isLeft_isRight()
        \until       }}
        \see         test_Bin_Tree<E>::test_isLeft_isRight()
    */
    bool isRightChild() const {
        if ( m_root.isNull() ) {
            return false; // árbol vacío
        }
        else if ( m_root->m_father.get() != 0 ) {
            Bin_Tree_Node<E> * father = m_root->m_father.get();
            return (m_root == father->m_right);
        }
        else {
            return false; // no es el hijo derecho
        }
    }

    /// Cantidad de referencias de la raíz del árbol
    unsigned use_count() const { return (m_root.get() == 0 ? 0 : m_root.use_count()); }
//@}
}; // Bin_Tree

/** \fn    template <class E> inline Bin_Tree<E>::Bin_Tree(const Bin_Tree& o)
    \brief Constructor de copia: los dos árboles comparten la misma raíz.
    - Constructor de copia desde otro árbol (copia superficial).
    - Como un sub-árbol en realidad es una referencia, este método
      no hace la copia completa [profunda] del árbol.

    \par Complejidad:
          O( \c 1 ).
*/

/**  Destructor.
    \par Complejidad:
         O( \c count()  ) ==> tiempo <br>
         O( \c height() ) ==> espacio.
    \see http://www.di-mare.com/adolfo/binder/c04.htm#sc04
*/
template <class E>
Bin_Tree<E>::~Bin_Tree() { // lkptr<> destruye el valor si hace falta
    m_root.release( );     // se auto-mata
}

/// Destructor.
template <class E>
inline Bin_Tree_Node<E>::~Bin_Tree_Node() {
    m_father.release();
/*  NOTA
    Cuando la estructura tiene ciclos puede ocurrir que al destruir
    uno de los elementos de la estructura se desencadene la destrucción
    de los demás, con lo que los valores terminan siendo destruidos más
    de una vez:
     A -> B -> C -> D ->   // A mata a B que mata a C que mata a D
    /|\                |   // y entonces D re-mata A etc...
     +---------<-------+

    En el caso de Bin_Tree<E> nunca hay ciclos, pues aunque cada nodo
    tiene punteros hacia arriba (m_father) y hacia abajo, a los hijos
    (m_left && m_right), nunca puede ocurrir que un nodo descendiente
    también sea padre de alguno de sus ancestros.

                    0      <== puntero nulo
                   /|\
                    A
                  /   \        Nunca hay ciclos en el árbol
                 B     C
                / \   / \
                0 0   0 0  <== punteros nulos
*/
}

/// Constructor a partir de un valor.
template <class E>
inline Bin_Tree<E>::Bin_Tree(const E & d) : m_root(0) {
    m_root.reset( new Bin_Tree_Node<E>(d) );
}

/** Copia superficial desde \c "o".
    - El valor anterior de \c "*this" se pierde.

    \par Complejidad:
         O( \c 1 ).
    \returns *this.
    \see http://www.di-mare.com/adolfo/binder/c04.htm#sc05
*/
template <class E>
inline void Bin_Tree<E>::copy( const Bin_Tree & other ) {
    m_root = other.m_root;
}

/** Intercambia los valores de \c "*this" y \c "o".
    - Debido a que algunos métodos retornan copias del valor de \c "*this" en
      lugar de una referencia, como ocurre con \c Bin_Tree::child(), a veces
      \c swap() no tiene el resultado esperado por el programador.
    - Por ejemplo, si se invoca <code> T.child(i). swap( T.child(j) ) </code>
      el resultado no es intercambiar los hijos, sino más bien intercambiar
      los valores de los sub-árboles temporales \c T.child(i) y \c T.child(j).
      La forma correcta de intercambiar hijos es usar \c makeLeftChild() y/o
      \c makeRightChild().

    \par Complejidad:
         O( \c 1 ).
    \returns *this.

    \see http://www.di-mare.com/adolfo/binder/c04.htm#sc08

    \dontinclude test_Bin_Tree.cpp
    \skipline    test::move_swap()
    \until       }}
    \see         test_Bin_Tree<E>::test_move_swap()

    \dontinclude test_Bin_Tree.cpp
    \skipline    test::no_swap()
    \until       }}
    \see         test_Bin_Tree<E>::test_no_swap()
*/
template <class E>
void Bin_Tree<E>::swap( Bin_Tree & other ) {
    if (this == &other) {
        return;          // evita auto-copia
    }
    #if 1
        // Esta sí funciona porque no hace falta cambiar "m_father" en los hijos
        lkptr< Bin_Tree_Node<E> > tmp ( m_root );
        m_root = other.m_root;
        other.m_root = tmp;
    #else
        Bin_Tree<E> TMP;     // tmp está vacío
        TMP.move( *this );   // *this queda vacío
        this->move( other ); // ahora other está vacío
        other.move( TMP );   // ahora TMP vuelve a quedar vacío
    #endif
    return;
}

/** Traslada a \c "*this" el valor de \c "other".
    - El valor anterior de \c "*this" se pierde.
    - El nuevo valor de \c "*this" es el que \c "other" tuvo.
    - \c "other" queda en el estado en que lo dejaría \c other.erase().
    - Si \c "*this" es \c "other" entonces su valor no cambia.
    - En general, después de esta operación casi
      nunca ocurre que \c this->equal(other) es \c "true".

    \par Complejidad:
         O( \c count() )
    \returns *this.
    \see http://www.di-mare.com/adolfo/binder/c04.htm#sc07

    \dontinclude test_Bin_Tree.cpp
    \skipline    test::move_swap()
    \until       }}
    \see         test_Bin_Tree<E>::test_move_swap()
*/
template <class E>
inline void Bin_Tree<E>::move( Bin_Tree & other ) {
    if (this == &other) {
        return; // evita auto-copia
    }
    m_root = other.m_root;
    other.m_root.release();
    return;
    // Es O( count() ) porque a veces operator=() borra "*this" completo
}
/** Retorna la cantidad de valores almacenados en el sub-árbol.
    - Calcula el número de sub-árboles no vacíos del árbol.
    \par Complejidad:
         O( \c count() ) ==> tiempo <br>
         O( \c height() ) ==> espacio.
    \see http://www.di-mare.com/adolfo/binder/c05.htm#sc03 */
template <class E>
unsigned Bin_Tree<E>::count() const {
    if (m_root.get() == 0) {
        return 0;
    } else {
        return 1 + ( left().count() + right().count() );
    }
}

/// Retorna la cantidad de hijos del árbol.
/// \par Complejidad:
///      O( \c 1 )
template <class E>
unsigned Bin_Tree<E>::countChildren() const {
    if (m_root.get() == 0) {
        return 0;
    }
    int n = 0;
    if ( !left().isEmpty() ) {
        ++n;
    }
    if ( !right().isEmpty() ) {
        ++n;
    }
    return n;
}

/// Sustituye por \c "d" el valor almacenado en la raíz del árbol.
/// - Si el árbol está vacío, le agrega su raíz.
template <class E>
void Bin_Tree<E>::changeRoot( const value_type & d ) {
    if ( m_root.isNull() ) { // como el árbol está vacío hay que agregarle la raíz
        m_root.reset ( new Bin_Tree_Node<E>(d) ); // crea el nodo raíz
    } else { // como no hay más referencias....
        m_root->m_data = d; // ... cambia el valor directamente
    }
}

/** Sustituye por \c "d" el valor almacenado en el hijo izquierdo del árbol.
    - Si no existe el hijo izquierdo lo agrega como una hoja con valor \c "d".
    - Si ya existe el hijo izquierdo le sustituye su valor por \c "d".
    - No hace nada si el árbol \c "*this" está vacío.

    \dontinclude test_Bin_Tree.cpp
    \skipline    test::changeChild()
    \until       }}
    \see         test_Bin_Tree<E>::test_changeChild()
*/
template <class E>
void Bin_Tree<E>::changeLeftChild( const value_type &d ) {
    if (m_root.get() == 0) { // ignora árboles vacíos
        return;
    }
    else if ( m_root->m_left.isNull() ) {
        m_root->m_left.reset( new Bin_Tree_Node<E>(d) ); // crea el nodo raíz
        m_root->m_left->m_father = m_root; // conecta el hijo hacia su padre
    }
    else {
        m_root->m_left->m_data =  d; // cambia el valor almacenado
    }
    return;
}

/** Sustituye por \c "d" el valor almacenado en el hijo derecho del árbol.
    - Si no existe el hijo derecho lo agrega como una hoja con valor \c "d".
    - Si ya existe el hijo derecho le sustituye su valor por \c "d".
    - No hace nada si el árbol \c "*this" está vacío.

    \dontinclude test_Bin_Tree.cpp
    \skipline    test::changeChild()
    \until       }}
    \see         test_Bin_Tree<E>::test_changeChild()
*/
template <class E>
void Bin_Tree<E>::changeRightChild( const value_type &d ) {
    if (m_root.get() == 0) { // ignora árboles vacíos
        return;
    }
    else if ( m_root->m_right.isNull() ) {
        m_root->m_right.reset( new Bin_Tree_Node<E>(d) ); // crea el nodo raíz
        m_root->m_right->m_father = m_root; // conecta el hijo hacia su padre
    }
    else {
        m_root->m_right->m_data =  d; // cambia el valor almacenado
    }
    return;
}

/** Pone al árbol \c "T" como sub-árbol izquierdo de \c "*this".
    - Elimina el sub-árbol izquierdo de \c "*this" si \c "T" está vacío.
    - El sub-árbol \c "T" puede ser hijo de muchos árboles, pero el que
      es reportado como su padre es el último para el que se usó
      \c makeLeftChild(T) o \c makeRightChild(T).
    - El programador cliente debe ser cuidadoso para no introducir
      ciclos en sus árboles.

    \pre <code> ! isEmpty() </code>

    \dontinclude test_Bin_Tree.cpp
    \skipline    test::no_swap()
    \until       }}
    \see         test_Bin_Tree<E>::test_no_swap()
*/
template <class E>
void Bin_Tree<E>::makeLeftChild( Bin_Tree T ) {
    if ( ! m_root.isNull() /* && this->m_root != T.m_root */ ) {
        if ( ! T.m_root.isNull() ) {
            T.m_root->m_father = this->m_root;
        }
        m_root->m_left = T.m_root; // ahora sí es el hijo izquierdo
    }
}

/** Pone al árbol \c "T" como sub-árbol derecho de \c "*this".
    - Elimina el sub-árbol derecho de \c "*this" si \c "T" está vacío.
    - El sub-árbol \c "T" puede ser hijo de muchos árboles, pero el que
      es reportado como su padre es el último para el que se usó
      \c makeLeftChild(T) o \c makeRightChild(T).
    - El programador cliente debe ser cuidadoso para no introducir
      ciclos en sus árboles.

    \pre <code> ! isEmpty() </code>

    \dontinclude test_Bin_Tree.cpp
    \skipline    test::no_swap()
    \until       }}
    \see         test_Bin_Tree<E>::test_no_swap()
*/
template <class E>
void Bin_Tree<E>::makeRightChild( Bin_Tree T ) {
    if ( ! m_root.isNull() /* && this->m_root != T.m_root */ ) {
        if ( ! T.m_root.isNull() ) {
            T.m_root->m_father = this->m_root;
            #if 0
            if ( ! T.m_root->m_father.isNull() ) {
                if ( T.m_root->m_father->m_left == T.m_root ) {
                    T.m_root->m_father->m_left.release();
                }
                else {
                    T.m_root->m_father->m_right.release();
                }
            }  // "T" queda desconectado como hijo de su antiguo padre
            #endif
        }
        m_root->m_right = T.m_root; // ahora sí es el hijo derecho
    }
    #if 0 // implementación que no verifica que *this sea nulo
        m_root->m_right = T.m_root;
        if ( ! T.m_root.isNull() ) {
            T.m_root->m_father = this->m_root;
        }
    #endif
}

/** Elimina el hijo izquierdo del árbol.
    - Es sinónimo de \c makeLeftChild( Bin_Tree<E>() );

    \dontinclude test_Bin_Tree.cpp
    \skipline    test::releaseChild()
    \until       }}
    \see         test_Bin_Tree<E>::test_releaseChild()
*/
template <class E>
inline void Bin_Tree<E>::releaseLeftChild( ) {
    makeLeftChild( Bin_Tree<E>() );
}

/** Elimina el hijo derecho del árbol.
    - Es sinónimo de \c makeLeftChild( Bin_Tree<E>() );

    \dontinclude test_Bin_Tree.cpp
    \skipline    test::releaseChild()
    \until       }}
    \see         test_Bin_Tree<E>::test_releaseChild()
*/
template <class E>
inline void Bin_Tree<E>::releaseRightChild( ) {
    makeRightChild( Bin_Tree<E>() );
}

/** Desconecta al hijo del padre.
    - Funciona con árboles vacíos.
    - El árbol \c "*this" continúa registrado como hijo de su padre.

    \dontinclude test_Bin_Tree.cpp
    \skipline    test::makeOrphan()
    \until       }}
    \see         test_Bin_Tree<E>::test_makeOrphan()
*/
template <class E>
void Bin_Tree<E>::makeOrphan( ) {
    if ( ! m_root.isNull() ) {
        if ( m_root->m_father.isNull() ) {
            return; // ya está huérfano
        }
        #if 0
        else if ( m_root->m_father->m_left == m_root ) {
            // es el hijo izquierdo de su padre
            m_root->m_father->m_left.release();
        }
        else { // assert( m_root->m_father->m_right == m_root );
            // es el hijo derecho de su padre
            m_root->m_father->m_right.release();
        }
        #endif
        m_root->m_father.release();
    }
}

#endif  // Bin_Tree_h

// EOF: Bin_Tree.h