Los métodos para trabajar con árboles binarios regresan "referencias" que son sub-árboles. More...

#include <Bin_Tree.h>

Public Types
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 `size()`
Public Member Functions
Operaciones de borrado
void	erase ()
	Deja el árbol vacío.
void	clear ()
	Sinónimo de `erase()`.
Operaciones de copiado
Bin_Tree &	operator= (const Bin_Tree &other)
	Sinónimo de `this->copy(o)` (pero retorna `*this`).
void	copy (const Bin_Tree &other)
	Copia superficial desde `"o"`.
Bin_Tree &	operator= (const value_type &d)
	Usa `changeRoot()` para sustituir por `"d"` el valor almacenado en la raíz del árbol.
void	move (Bin_Tree &other)
	Traslada a `"*this"` el valor de `"other"`.
void	swap (Bin_Tree &other)
	Intercambia los valores de `"*this"` y `"o"`.
Métodos para cambiar los valores almacenados en el árbol
void	changeRoot (const value_type &d)
	Sustituye por `"d"` el valor almacenado en la raíz del árbol.
void	changeLeftChild (const value_type &d)
	Sustituye por `"d"` el valor almacenado en el hijo izquierdo del árbol.
void	changeRightChild (const value_type &d)
	Sustituye por `"d"` el valor almacenado en el hijo derecho del árbol.
void	makeLeftChild (Bin_Tree T)
	Pone al árbol `"T"` como sub-árbol izquierdo de `"*this"`.
void	makeRightChild (Bin_Tree T)
	Pone al árbol `"T"` como sub-árbol derecho de `"*this"`.
void	releaseLeftChild ()
	Elimina el hijo izquierdo del árbol.
void	releaseRightChild ()
	Elimina el hijo derecho del árbol.
void	makeOrphan ()
	Desconecta al hijo del padre.
Operaciones para usar los valores almacenados
value_type &	data () const
	Valor almacenado en la raíz del sub-árbol.
value_type &	operator* () const
	Valor almacenado en la raíz del sub-árbol.
value_type *	operator-> () const
	Puntero al valor almacenado en la raíz del sub-árbol.
Métodos para recorrer el árbol
const Bin_Tree	root () const
	Raíz del sub-árbol.
Bin_Tree	father () const
	Acceso al padre.
Bin_Tree	left () const
	Acceso al hijo izquierdo.
Bin_Tree	right () const
	Acceso al hijo derecho.
Bin_Tree	child (int i) const
	Acceso al i-ésimo hijo del árbol.
Propiedades del árbol
bool	isRoot () const
	Retorna `"true"` si el árbol no tiene padre.
bool	isLeaf () const
	Retorna `"true"` si el árbol es una hoja.
bool	isLeftChild () const
	Retorna `"true"` si el árbol es el hijo izquierdo de su padre.
bool	isRightChild () const
	Retorna `"true"` si el árbol es el hijo derecho de su padre.
unsigned	use_count () const
	Cantidad de referencias de la raíz del árbol.
Private Attributes
lkptr< Bin_Tree_Node< E > >	m_root
	Un árbol "es" el puntero al nodo raíz.
Constructores y destructor
	Bin_Tree ()
	Constructor de vector: el árbol queda vacío.
	Bin_Tree (const Bin_Tree &other)
	Constructor de copia: los dos árboles comparten la misma raíz.
	Bin_Tree (const value_type &d)
	Constructor a partir de un valor.
	~Bin_Tree ()
	Destructor.
	Bin_Tree (lkptr< Bin_Tree_Node< E > > &other)
	Constructor a partir de un puntero a un nodo.
	Bin_Tree (const lkptr< Bin_Tree_Node< E > > &other)
	Constructor a partir de un puntero a un nodo (puntero `const`).
Operaciones básicas
bool	isEmpty () const
	Retorna `"true"` si el sub-árbol está vacío.
unsigned	count () const
	Retorna la cantidad de valores almacenados en el sub-árbol.
unsigned	countChildren () const
	Retorna la cantidad de hijos del árbol.
unsigned	size () const
	Usa `count()` para retornar la cantidad de valores almacenados en el sub-árbol.
bool	ok () const
	Verifica la invariante de `Bin_Tree<E>`.
template<class T >
bool	check_ok (const Bin_Tree< T > &aT)
	Usa `ok()` para verificar la invariante de la clase.
Operaciones de comparación
bool	equals (const Bin_Tree &o) const
	¿¿¿ (*this==o) ???
bool	same (const Bin_Tree &o) const
	Retorna `true` si `"o"` comparte la raíz con `"*this"`.
template<class T >
bool	operator== (const Bin_Tree< T > &p, const Bin_Tree< T > &q)
	¿¿¿ (p == q) ???
template<class T >
bool	operator!= (const Bin_Tree< T > &p, const Bin_Tree< T > &q)
	¿¿¿ (p != q) ???

Detailed Description

template<class E>
class Bin_Tree< E >

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 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".

    {{  // test::multi_child()
        // Muestra que un mismo árbol "Bebe" puede ser sub-árbol
        // de varios árboles
        Bin_Tree<E> Paco = E();     // Paco    Lola //
        Bin_Tree<E> Lola = E();     //              //
        Bin_Tree<E> Bebe;           //   E()   E()  //
        Lola.makeLeftChild( E() );  //     \\ /     //
        Bebe = Lola.left();         //     Bebe     //
        Bebe.makeLeftChild(  E() ); //     // \\    //
        Bebe.makeRightChild( E() ); //   E()   E()  //
        Paco.makeRightChild( Bebe );

        // Como se muestra en el diagrama X, debido a este último cambio
        // el padre registrado de Bebe ahora es Paco

        assertTrue( 3 == Bebe.size() );
        assertTrue( 4 == Paco.size() ); // 3 de Bebe + Paco
        assertTrue( 4 == Lola.size() ); // 3 de Bebe + Lola

        assertTrue( Paco.right().same( Bebe ) ); // Bebe es hijo de Paco
        assertTrue( Lola.left() .same( Bebe ) ); // Bebe es hijo de Lola

        assertTrue(   Bebe.father().same( Paco ) ); // El papá de Bebe es Paco
        assertTrue( ! Bebe.father().same( Lola ) ); // Lola no es ancestro de Bebe
        // corrección: "Lola" no aparece registrada como padre para "Bebe"

        Bebe.erase();
        assertTrue( Bebe.isEmpty() ); // La referencia Bebe está vacía

        Bebe = Lola.left();           // Se llega al hijo compartido desde Lola
        assertTrue( ! Bebe.isEmpty() );
        assertTrue(   Bebe.father().same( Paco ) ); // Repito: el papá de Bebe es Paco
        assertTrue( ! Bebe.father().same( Lola ) ); // Repito: Lola no es ancestro de Bebe

        if ( false ) { // Tortón !!!
            Bebe.left().makeRightChild( Paco );  // ciclo infinito en el árbol
            Bebe.right().makeLeftChild( Lola );
        }
    }}

See also:: test_Bin_Tree<E>::test_multi_child()

Definition at line 54 of file Bin_Tree.h.

Member Typedef Documentation

template<class E>

typedef E Bin_Tree< E >::value_type

Nombre estándar del tipo de elemento contenido.

Definition at line 58 of file Bin_Tree.h.

template<class E>

typedef const value_type& Bin_Tree< E >::const_reference

Referencia constante al objeto contenido.

Definition at line 59 of file Bin_Tree.h.

template<class E>

typedef unsigned Bin_Tree< E >::size_type

Nombre estándar del tipo retornado por size()

Definition at line 60 of file Bin_Tree.h.

Constructor & Destructor Documentation

template<class E>

Bin_Tree< E >::Bin_Tree ( ) [inline]

Constructor de vector: el árbol queda vacío.

Definition at line 65 of file Bin_Tree.h.

template<class E>

template< class E > inline Bin_Tree< E >::Bin_Tree ( const Bin_Tree< E > & o ) [inline]

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.

Complejidad:: O( 1 ).

Definition at line 68 of file Bin_Tree.h.

template<class E >

Bin_Tree< E >::Bin_Tree ( const value_type & d ) [inline]

Constructor a partir de un valor.

Definition at line 352 of file Bin_Tree.h.

template<class E >

Bin_Tree< E >::~Bin_Tree ( )

Destructor.

Complejidad:: O( count() ) ==> tiempo
O( height() ) ==> espacio.

See also:: http://www.di-mare.com/adolfo/binder/c04.htm#sc04

Definition at line 318 of file Bin_Tree.h.

template<class E>

Bin_Tree< E >::Bin_Tree ( lkptr< Bin_Tree_Node< E > > & other ) [inline, private]

Constructor a partir de un puntero a un nodo.

Definition at line 73 of file Bin_Tree.h.

template<class E>

Bin_Tree< E >::Bin_Tree ( const lkptr< Bin_Tree_Node< E > > & other ) [inline, private]

Constructor a partir de un puntero a un nodo (puntero const).

Definition at line 75 of file Bin_Tree.h.

Member Function Documentation

template<class E>

bool Bin_Tree< E >::isEmpty ( ) const [inline]

Retorna "true" si el sub-árbol está vacío.

Definition at line 82 of file Bin_Tree.h.

template<class E >

unsigned Bin_Tree< E >::count ( ) const

Retorna la cantidad de valores almacenados en el sub-árbol.

Calcula el número de sub-árboles no vacíos del árbol.
Complejidad:
O( count() ) ==> tiempo
O( height() ) ==> espacio.

See also:
http://www.di-mare.com/adolfo/binder/c05.htm#sc03

Definition at line 449 of file Bin_Tree.h.

template<class E >

unsigned Bin_Tree< E >::countChildren ( ) const

Retorna la cantidad de hijos del árbol.

Complejidad:: O( 1 )

Definition at line 461 of file Bin_Tree.h.

template<class E>

unsigned Bin_Tree< E >::size ( ) const [inline]

Usa count() para retornar la cantidad de valores almacenados en el sub-árbol.

Definition at line 86 of file Bin_Tree.h.

template<class E>

bool Bin_Tree< E >::ok ( ) const [inline]

Verifica la invariante de Bin_Tree<E>.

Definition at line 87 of file Bin_Tree.h.

template<class E>

void Bin_Tree< E >::erase ( ) [inline]

Deja el árbol vacío.

Si es necesario, también elimina sus descendientes.
T.left().erase(); // No cambia "T" porque el que cambia es "T.left()"
T.makeLeftChild( Bin_Tree<E>() ); // así sí se borra el hijo izquierdo
T.makeRightChild( Bin_Tree<E>() ); // borra el hijo derecho

Complejidad:: O( count() ) ==> tiempo
O( height() ) ==> espacio.

See also:: http://www.di-mare.com/adolfo/binder/c04.htm#sc03

Definition at line 106 of file Bin_Tree.h.

template<class E>

void Bin_Tree< E >::clear ( ) [inline]

Sinónimo de erase().

Definition at line 107 of file Bin_Tree.h.

template<class E>

Bin_Tree& Bin_Tree< E >::operator= ( const Bin_Tree< E > & other ) [inline]

Sinónimo de this->copy(o) (pero retorna *this).

Definition at line 114 of file Bin_Tree.h.

template<class E >

void Bin_Tree< E >::copy ( const Bin_Tree< E > & other ) [inline]

Copia superficial desde "o".

El valor anterior de "*this" se pierde.

Complejidad:: O( 1 ).

Returns:: *this.

See also:: http://www.di-mare.com/adolfo/binder/c04.htm#sc05

Definition at line 365 of file Bin_Tree.h.

template<class E>

Bin_Tree& Bin_Tree< E >::operator= ( const value_type & d ) [inline]

Usa changeRoot() para sustituir por "d" el valor almacenado en la raíz del árbol.

Definition at line 117 of file Bin_Tree.h.

template<class E >

void Bin_Tree< E >::move ( Bin_Tree< E > & other ) [inline]

Traslada a "*this" el valor de "other".

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

Complejidad:: O( count() )

Returns:: *this.

See also:: http://www.di-mare.com/adolfo/binder/c04.htm#sc07

    {{  // test::move_swap()
        Bin_Tree<E> Paco = E(), Lola = E();  //     E()     //
        Paco.makeLeftChild(  E() );          //    /  \     //
        Paco.makeRightChild( E() );          //  E()   E()  //

        assertTrue( Paco.size() == 3 );
        assertTrue( Lola.size() == 1 );
        Paco.swap( Lola );
        assertTrue( Paco.size() == 1 );
        assertTrue( Lola.size() == 3 );

        Lola.move( Paco );
        assertTrue( Paco.size() == 0 );
        assertTrue( Lola.size() == 1 );
    }}

See also:: test_Bin_Tree<E>::test_move_swap()

Definition at line 433 of file Bin_Tree.h.

template<class E >

void Bin_Tree< E >::swap ( Bin_Tree< E > & other )

Intercambia los valores de "*this" y "o".

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

Complejidad:: O( 1 ).

Returns:: *this.

See also:: http://www.di-mare.com/adolfo/binder/c04.htm#sc08

    {{  // test::move_swap()
        Bin_Tree<E> Paco = E(), Lola = E();  //     E()     //
        Paco.makeLeftChild(  E() );          //    /  \     //
        Paco.makeRightChild( E() );          //  E()   E()  //

        assertTrue( Paco.size() == 3 );
        assertTrue( Lola.size() == 1 );
        Paco.swap( Lola );
        assertTrue( Paco.size() == 1 );
        assertTrue( Lola.size() == 3 );

        Lola.move( Paco );
        assertTrue( Paco.size() == 0 );
        assertTrue( Lola.size() == 1 );
    }}

See also:: test_Bin_Tree<E>::test_move_swap()

    {{  // test::no_swap()
        Bin_Tree<E> T = E();      //  E()     //
        Bin_Tree<E> Right;        //    \     //
        T.makeRightChild( E() );  //     E()  //

        assertTrue( T.size() == 2 );
        assertTrue( T.right().isRightChild() ); // Ahí está el hijo derecho
        Right = T.right();  // no compila >==> T.left().swap( T.right() );
        T.left().swap( Right );
        assertTrue( T.right().isRightChild() ); // El hijo derecho no ha cambiado
        assertTrue( T.size() == 2 );

        T.makeLeftChild( T.right() );            //    E()   //
        assertTrue( T.size() == 3 );             //   /   \  //
        assertTrue( T.left().same( T.right()) ); //   \   /  //
        assertTrue( T.right().isRightChild() );  //    E()   //
        assertTrue( T.left().isLeftChild() );    // hijo compartido

        T.makeLeftChild( T.right() );            // ahora sí cambió el árbol
        T.makeRightChild( Bin_Tree<E>() );       // borra al hijo derecho
        assertTrue( T.size() == 2 );
        assertTrue( ! T.left().same( T.right()) );
        assertTrue( ! T.right().isRightChild() ); // si hay hijo derecho
        assertTrue( T.left().isLeftChild() );     // Ahí está el antiguo hijo derecho
    }}

See also:: test_Bin_Tree<E>::test_no_swap()

Definition at line 396 of file Bin_Tree.h.

template<class E >

void Bin_Tree< E >::changeRoot ( const value_type & d )

Sustituye por "d" el valor almacenado en la raíz del árbol.

Si el árbol está vacío, le agrega su raíz.

Definition at line 478 of file Bin_Tree.h.

template<class E >

void Bin_Tree< E >::changeLeftChild ( const value_type & d )

Sustituye por "d" el valor almacenado en el hijo izquierdo del árbol.

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

    {{  // test::changeChild()
        Bin_Tree<char> T, Tcopy;
        T = 'A'; // agrega la raiz 'A'    A
        T.changeLeftChild(  '0' );  //  ./ \.
        T.changeRightChild( '1' );  //  0   1
        copyDeep( Tcopy , T );
        assertTrue( TestCase::toString(T) == "(A (0) (1))" );
        mirror( T );
        assertTrue( TestCase::toString(T) == "(A (1) (0))" );
        mirror( T ); {
            std::basic_ostringstream<char> ost;
            ost << T;
            assertTrue( ost.str() == "(A (0) (1))" );
        }

        assertTrue( comp(T, Tcopy) );
    }}

See also:: test_Bin_Tree<E>::test_changeChild()

Definition at line 497 of file Bin_Tree.h.

template<class E >

void Bin_Tree< E >::changeRightChild ( const value_type & d )

Sustituye por "d" el valor almacenado en el hijo derecho del árbol.

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

    {{  // test::changeChild()
        Bin_Tree<char> T, Tcopy;
        T = 'A'; // agrega la raiz 'A'    A
        T.changeLeftChild(  '0' );  //  ./ \.
        T.changeRightChild( '1' );  //  0   1
        copyDeep( Tcopy , T );
        assertTrue( TestCase::toString(T) == "(A (0) (1))" );
        mirror( T );
        assertTrue( TestCase::toString(T) == "(A (1) (0))" );
        mirror( T ); {
            std::basic_ostringstream<char> ost;
            ost << T;
            assertTrue( ost.str() == "(A (0) (1))" );
        }

        assertTrue( comp(T, Tcopy) );
    }}

See also:: test_Bin_Tree<E>::test_changeChild()

Definition at line 522 of file Bin_Tree.h.

template<class E >

void Bin_Tree< E >::makeLeftChild ( Bin_Tree< E > T )

Pone al árbol "T" como sub-árbol izquierdo de "*this".

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

Precondition:: ! isEmpty()

    {{  // test::no_swap()
        Bin_Tree<E> T = E();      //  E()     //
        Bin_Tree<E> Right;        //    \     //
        T.makeRightChild( E() );  //     E()  //

        assertTrue( T.size() == 2 );
        assertTrue( T.right().isRightChild() ); // Ahí está el hijo derecho
        Right = T.right();  // no compila >==> T.left().swap( T.right() );
        T.left().swap( Right );
        assertTrue( T.right().isRightChild() ); // El hijo derecho no ha cambiado
        assertTrue( T.size() == 2 );

        T.makeLeftChild( T.right() );            //    E()   //
        assertTrue( T.size() == 3 );             //   /   \  //
        assertTrue( T.left().same( T.right()) ); //   \   /  //
        assertTrue( T.right().isRightChild() );  //    E()   //
        assertTrue( T.left().isLeftChild() );    // hijo compartido

        T.makeLeftChild( T.right() );            // ahora sí cambió el árbol
        T.makeRightChild( Bin_Tree<E>() );       // borra al hijo derecho
        assertTrue( T.size() == 2 );
        assertTrue( ! T.left().same( T.right()) );
        assertTrue( ! T.right().isRightChild() ); // si hay hijo derecho
        assertTrue( T.left().isLeftChild() );     // Ahí está el antiguo hijo derecho
    }}

See also:: test_Bin_Tree<E>::test_no_swap()

Definition at line 552 of file Bin_Tree.h.

template<class E >

void Bin_Tree< E >::makeRightChild ( Bin_Tree< E > T )

Pone al árbol "T" como sub-árbol derecho de "*this".

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

Precondition:: ! isEmpty()

    {{  // test::no_swap()
        Bin_Tree<E> T = E();      //  E()     //
        Bin_Tree<E> Right;        //    \     //
        T.makeRightChild( E() );  //     E()  //

        assertTrue( T.size() == 2 );
        assertTrue( T.right().isRightChild() ); // Ahí está el hijo derecho
        Right = T.right();  // no compila >==> T.left().swap( T.right() );
        T.left().swap( Right );
        assertTrue( T.right().isRightChild() ); // El hijo derecho no ha cambiado
        assertTrue( T.size() == 2 );

        T.makeLeftChild( T.right() );            //    E()   //
        assertTrue( T.size() == 3 );             //   /   \  //
        assertTrue( T.left().same( T.right()) ); //   \   /  //
        assertTrue( T.right().isRightChild() );  //    E()   //
        assertTrue( T.left().isLeftChild() );    // hijo compartido

        T.makeLeftChild( T.right() );            // ahora sí cambió el árbol
        T.makeRightChild( Bin_Tree<E>() );       // borra al hijo derecho
        assertTrue( T.size() == 2 );
        assertTrue( ! T.left().same( T.right()) );
        assertTrue( ! T.right().isRightChild() ); // si hay hijo derecho
        assertTrue( T.left().isLeftChild() );     // Ahí está el antiguo hijo derecho
    }}

See also:: test_Bin_Tree<E>::test_no_swap()

Definition at line 577 of file Bin_Tree.h.

template<class E >

void Bin_Tree< E >::releaseLeftChild ( ) [inline]

Elimina el hijo izquierdo del árbol.

Es sinónimo de makeLeftChild( Bin_Tree<E>() );

    {{  // test::releaseChild()
        Bin_Tree<E> Paco = E();     // Paco    Lola //
        Bin_Tree<E> Lola = E();     //              //
        Bin_Tree<E> Bebe;           //   E()   E()  //
        Lola.makeLeftChild( E() );  //     \\ /     //
        Bebe = Lola.left();         //     Bebe     //
        Bebe.makeLeftChild(  E() ); //     // \\    //
        Bebe.makeRightChild( E() ); //   E()   E()  //
        Paco.makeRightChild( Bebe );

        Paco.releaseLeftChild();
        assertTrue( 4 == Paco.size() ); // Paco no tiene hijo izquierdo
        Paco.releaseRightChild();
        assertTrue( 1 == Paco.size() ); // Ya Paco no tiene hijo derecho
        assertTrue( Paco.right() == Bin_Tree<E>() ); // El hijo derecho es un árbol vacío
        assertTrue( Bebe != Bin_Tree<E>() );         // Bebe todavía existe
        assertTrue( Bebe.father() == Paco );  // Paco sigue registrado como padre de Bebe

        assertTrue( 4 == Lola.size() ); // Lola todavía tiene a su hijo izquierdo
        assertTrue( Bebe.same( Lola.left() ) ); // Bebe si es hijo izquierdo de Lola
        assertTrue( Lola.left().same( Bebe ) ); // Lola si tiene hijo izquierdo
        assertTrue( Bebe.father() != Bin_Tree<E>() ); // Bebe no está registrado como hijo de Lola

        Lola.releaseLeftChild(); // Ahora ya Bebe no es hijo de Lola
        assertTrue( ! Bebe.same( Lola.left() ) );
        assertTrue( 1 == Lola.size() ); // Ya Lola no tiene hijos
    }}

See also:: test_Bin_Tree<E>::test_releaseChild()

Definition at line 611 of file Bin_Tree.h.

template<class E >

void Bin_Tree< E >::releaseRightChild ( ) [inline]

Elimina el hijo derecho del árbol.

Es sinónimo de makeLeftChild( Bin_Tree<E>() );

    {{  // test::releaseChild()
        Bin_Tree<E> Paco = E();     // Paco    Lola //
        Bin_Tree<E> Lola = E();     //              //
        Bin_Tree<E> Bebe;           //   E()   E()  //
        Lola.makeLeftChild( E() );  //     \\ /     //
        Bebe = Lola.left();         //     Bebe     //
        Bebe.makeLeftChild(  E() ); //     // \\    //
        Bebe.makeRightChild( E() ); //   E()   E()  //
        Paco.makeRightChild( Bebe );

        Paco.releaseLeftChild();
        assertTrue( 4 == Paco.size() ); // Paco no tiene hijo izquierdo
        Paco.releaseRightChild();
        assertTrue( 1 == Paco.size() ); // Ya Paco no tiene hijo derecho
        assertTrue( Paco.right() == Bin_Tree<E>() ); // El hijo derecho es un árbol vacío
        assertTrue( Bebe != Bin_Tree<E>() );         // Bebe todavía existe
        assertTrue( Bebe.father() == Paco );  // Paco sigue registrado como padre de Bebe

        assertTrue( 4 == Lola.size() ); // Lola todavía tiene a su hijo izquierdo
        assertTrue( Bebe.same( Lola.left() ) ); // Bebe si es hijo izquierdo de Lola
        assertTrue( Lola.left().same( Bebe ) ); // Lola si tiene hijo izquierdo
        assertTrue( Bebe.father() != Bin_Tree<E>() ); // Bebe no está registrado como hijo de Lola

        Lola.releaseLeftChild(); // Ahora ya Bebe no es hijo de Lola
        assertTrue( ! Bebe.same( Lola.left() ) );
        assertTrue( 1 == Lola.size() ); // Ya Lola no tiene hijos
    }}

See also:: test_Bin_Tree<E>::test_releaseChild()

Definition at line 624 of file Bin_Tree.h.

template<class E >

void Bin_Tree< E >::makeOrphan ( )

Desconecta al hijo del padre.

Funciona con árboles vacíos.
El árbol "*this" continúa registrado como hijo de su padre.

    {{  // test::makeOrphan()
        Bin_Tree<E> Paco = E();     // Paco    Lola //
        Bin_Tree<E> Lola = E();     //              //
        Bin_Tree<E> Bebe;           //   E()   E()  //
        Lola.makeLeftChild( E() );  //     \\ /     //
        Bebe = Lola.left();         //     Bebe     //
        Bebe.makeLeftChild(  E() ); //     // \\    //
        Bebe.makeRightChild( E() ); //   E()   E()  //
        Paco.makeRightChild( Bebe );

        assertTrue( Bebe.same( Lola.left()  ) ); // Bebe si es hijo izquierdo de Lola
        assertTrue( Bebe.same( Paco.right() ) ); // Bebe si es hijo derecho de Paco
        assertTrue( Bebe.father() == Paco );     // Bebe está registrado como hijo de Paco
        assertTrue( Bebe.father() != Lola );     // Bebe no está registrado como hijo de Lola

        Bebe.makeOrphan();
        assertTrue( Bebe.father() != Paco );          // Ya Paco no está registrado como el padre de Bebe
        assertTrue( Bebe.father() == Bin_Tree<E>() ); // Bebe no tiene registrado a nadie como su padre

        assertTrue( Bebe.same( Lola.left() ) );  // Bebe sigue registrado como hijo izquierdo de Lola
        assertTrue( Bebe.same( Paco.right() ) ); // Bebe sigue registrado como hijo derecho de Paco
        assertTrue( Bebe.father() != Paco );     // Bebe ya no está registrado como hijo de Paco
        assertTrue( Bebe.father() != Lola );     // Bebe ya no está registrado como hijo de Lola
    }}

See also:: test_Bin_Tree<E>::test_makeOrphan()

Definition at line 638 of file Bin_Tree.h.

template<class E>

value_type& Bin_Tree< E >::data ( ) const [inline]

Valor almacenado en la raíz del sub-árbol.

Precondition:: !isEmpty()

Definition at line 140 of file Bin_Tree.h.

template<class E>

value_type& Bin_Tree< E >::operator* ( ) const [inline]

Valor almacenado en la raíz del sub-árbol.

Precondition:: !isEmpty()

Definition at line 143 of file Bin_Tree.h.

template<class E>

value_type* Bin_Tree< E >::operator-> ( ) const [inline]

Puntero al valor almacenado en la raíz del sub-árbol.

Precondition:: !isEmpty()

Definition at line 146 of file Bin_Tree.h.

template<class E>

bool Bin_Tree< E >::equals ( const Bin_Tree< E > & o ) const [inline]

¿¿¿ (*this==o) ???

Definition at line 156 of file Bin_Tree.h.

template<class E>

bool Bin_Tree< E >::same ( const Bin_Tree< E > & o ) const [inline]

Retorna true si "o" comparte la raíz con "*this".

Definition at line 158 of file Bin_Tree.h.

template<class E>

const Bin_Tree Bin_Tree< E >::root ( ) const [inline]

Raíz del sub-árbol.

Definition at line 164 of file Bin_Tree.h.

template<class E>

Bin_Tree Bin_Tree< E >::father ( ) const [inline]

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.

Definition at line 170 of file Bin_Tree.h.

template<class E>

Bin_Tree Bin_Tree< E >::left ( ) const [inline]

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 makeLeftChild().
Como los árboles son referencias, este método no sirve para modificar la estructura del árbol.

    {{  // test::left_right()
        Bin_Tree<E> T = E(); // no hay hijo izquierdo alguno
        {   T.left() = E();    // sí hace el cambio
            // pero el destructor elimina la referencia
        }   // sin modificar el hijo izquierdo que no existe
        assertTrue( T.size() == 1 );
        assertTrue( T.left().isEmpty() ); // "T.left()" es una nueva referencia al hijo de "T"

        T.makeRightChild( E() ); // esta es la forma de crear un nuevo sub-árbol derecho
        T.right().erase(); // no elimina al hijo derecho: borra la nueva referencia "right()"
        assertTrue( T.size() == 2 );
        assertTrue( ! T.right().isEmpty() ); // el hijo derecho está ahí todavía

        {   // Para eliminar a un hijo hay que poner el árbol nulo en su lugar
            T.right() = Bin_Tree<E>(); // cambia la referencia: el hijo derecho sigue ahí
            assertTrue( ! T.right().isEmpty() ); // el hijo derecho está ahí todavía

            assertTrue( Bin_Tree<E>().isEmpty() ); // referencia nula: árbol vacío

            // esta es la forma correcta de eliminar hijos
            T.makeRightChild( Bin_Tree<E>() ); // elimina al hijo derecho
            assertTrue( T.right().isEmpty() ); // ya no existe el hijo derecho
        }

        if ( T.right().isEmpty() ) {
            if (false) {
                *T.right() = E(); // ERROR: Trata de cambiar un árbol vacío
            }
            T.makeRightChild( E() ); // nuevo hijo derecho
        }
        else {
            T.right().changeRoot( E() ); // sí cambia el valor almacenado
            *( T.right() ) = E(); // efecto similar al renglón anterior
        }
        T = T.right(); // caminar hacia las hojas no cambia el valor almacenado
        assertTrue ( ! T.father().isEmpty() );
        assertTrue( T.size() == 1 );
        T = T.father();
        assertTrue( T.size() == 2 );
        T.right().erase(); // no cambia nada
        assertTrue( T.size() == 2 );

        Bin_Tree<E> Child = T.right();     // sostiene al hijo
        T.right().makeOrphan();            // elimna la conexión hijo->padre
        assertTrue( T.right() == Child );  // no eliminó la conexión hijo->padre
        assertTrue( Child.father() != T ); // ni el antiguo hijo encuentra a su padre
        assertTrue ( ! T.isEmpty() );
        assertTrue ( ! Child.isEmpty() );
        assertTrue ( Child.father().isEmpty() ); // ni el antiguo hijo tiene padre
    }}

See also:: test_Bin_Tree<E>::test_left_right()

Definition at line 188 of file Bin_Tree.h.

template<class E>

Bin_Tree Bin_Tree< E >::right ( ) const [inline]

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 makeRightChild().
Como los árboles son referencias, este método no sirve para modificar la estructura del árbol.

    {{  // test::left_right()
        Bin_Tree<E> T = E(); // no hay hijo izquierdo alguno
        {   T.left() = E();    // sí hace el cambio
            // pero el destructor elimina la referencia
        }   // sin modificar el hijo izquierdo que no existe
        assertTrue( T.size() == 1 );
        assertTrue( T.left().isEmpty() ); // "T.left()" es una nueva referencia al hijo de "T"

        T.makeRightChild( E() ); // esta es la forma de crear un nuevo sub-árbol derecho
        T.right().erase(); // no elimina al hijo derecho: borra la nueva referencia "right()"
        assertTrue( T.size() == 2 );
        assertTrue( ! T.right().isEmpty() ); // el hijo derecho está ahí todavía

        {   // Para eliminar a un hijo hay que poner el árbol nulo en su lugar
            T.right() = Bin_Tree<E>(); // cambia la referencia: el hijo derecho sigue ahí
            assertTrue( ! T.right().isEmpty() ); // el hijo derecho está ahí todavía

            assertTrue( Bin_Tree<E>().isEmpty() ); // referencia nula: árbol vacío

            // esta es la forma correcta de eliminar hijos
            T.makeRightChild( Bin_Tree<E>() ); // elimina al hijo derecho
            assertTrue( T.right().isEmpty() ); // ya no existe el hijo derecho
        }

        if ( T.right().isEmpty() ) {
            if (false) {
                *T.right() = E(); // ERROR: Trata de cambiar un árbol vacío
            }
            T.makeRightChild( E() ); // nuevo hijo derecho
        }
        else {
            T.right().changeRoot( E() ); // sí cambia el valor almacenado
            *( T.right() ) = E(); // efecto similar al renglón anterior
        }
        T = T.right(); // caminar hacia las hojas no cambia el valor almacenado
        assertTrue ( ! T.father().isEmpty() );
        assertTrue( T.size() == 1 );
        T = T.father();
        assertTrue( T.size() == 2 );
        T.right().erase(); // no cambia nada
        assertTrue( T.size() == 2 );

        Bin_Tree<E> Child = T.right();     // sostiene al hijo
        T.right().makeOrphan();            // elimna la conexión hijo->padre
        assertTrue( T.right() == Child );  // no eliminó la conexión hijo->padre
        assertTrue( Child.father() != T ); // ni el antiguo hijo encuentra a su padre
        assertTrue ( ! T.isEmpty() );
        assertTrue ( ! Child.isEmpty() );
        assertTrue ( Child.father().isEmpty() ); // ni el antiguo hijo tiene padre
    }}

See also:: test_Bin_Tree<E>::test_left_right()

Definition at line 208 of file Bin_Tree.h.

template<class E>

Bin_Tree Bin_Tree< E >::child ( int i ) const [inline]

Acceso al i-ésimo hijo del árbol.

Si el sub-árbol no tiene es hijo retorna el árbol vacío.
( i == 0 ) ==> Hijo izquierdo.
( i == 1 ) ==> Hijo derecho.
Como los árboles son referencias, este método no sirve para modificar la estructura del árbol.

Definition at line 220 of file Bin_Tree.h.

template<class E>

bool Bin_Tree< E >::isRoot ( ) const [inline]

Retorna "true" si el árbol no tiene padre.

Retorna "false" para un árbol vacío.

    {{  // test::isRoot_isLeaf()
        Bin_Tree<E> T = E();      //     E()     //
        T.makeLeftChild( E() );   //    /  \     //
        T.makeRightChild( E() );  //  E()   E()  //

        assertTrue( T.isRoot() && ! T.isLeaf()  );
        assertTrue( T.left().isLeaf() );
        assertTrue( T.right().isLeaf() );
        assertTrue( !T.left().left().isLeaf() );   // árbol vacío
        assertTrue( !T.right().right().isRoot() ); // árbol vacío
    }}

See also:: test_Bin_Tree<E>::test_isRoot_isLeaf()

Definition at line 239 of file Bin_Tree.h.

template<class E>

bool Bin_Tree< E >::isLeaf ( ) const [inline]

Retorna "true" si el árbol es una hoja.

Retorna "false" para un árbol vacío.

    {{  // test::isRoot_isLeaf()
        Bin_Tree<E> T = E();      //     E()     //
        T.makeLeftChild( E() );   //    /  \     //
        T.makeRightChild( E() );  //  E()   E()  //

        assertTrue( T.isRoot() && ! T.isLeaf()  );
        assertTrue( T.left().isLeaf() );
        assertTrue( T.right().isLeaf() );
        assertTrue( !T.left().left().isLeaf() );   // árbol vacío
        assertTrue( !T.right().right().isRoot() ); // árbol vacío
    }}

See also:: test_Bin_Tree<E>::test_isRoot_isLeaf()

Definition at line 248 of file Bin_Tree.h.

template<class E>

bool Bin_Tree< E >::isLeftChild ( ) const [inline]

Retorna "true" si el árbol es el hijo izquierdo de su padre.

Retorna "false" si el árbol está vacío.
Retorna "false" si el árbol no tiene padre.
Retorna "false" si el árbol es el hijo derecho de su padre.

    {{  // test::isLeft_isRight()
        Bin_Tree<E> T = E();      //     E()     //
        T.makeLeftChild( E() );   //    /  \     //
        T.makeRightChild( E() );  //  E()   E()  //

        assertTrue( ! T.isLeftChild()  );
        assertTrue( T.left().isLeftChild() );
        assertTrue( T.right().isRightChild() );
        assertTrue( !T.left().left().isLeftChild() );    // árbol vacío
        assertTrue( !T.right().right().isRightChild() ); // árbol vacío
    }}

See also:: test_Bin_Tree<E>::test_isLeft_isRight()

Definition at line 261 of file Bin_Tree.h.

template<class E>

bool Bin_Tree< E >::isRightChild ( ) const [inline]

Retorna "true" si el árbol es el hijo derecho de su padre.

Retorna "false" si el árbol está vacío.
Retorna "false" si el árbol no tiene padre.
Retorna "false" si el árbol es el hijo izquierdo de su padre.

    {{  // test::isLeft_isRight()
        Bin_Tree<E> T = E();      //     E()     //
        T.makeLeftChild( E() );   //    /  \     //
        T.makeRightChild( E() );  //  E()   E()  //

        assertTrue( ! T.isLeftChild()  );
        assertTrue( T.left().isLeftChild() );
        assertTrue( T.right().isRightChild() );
        assertTrue( !T.left().left().isLeftChild() );    // árbol vacío
        assertTrue( !T.right().right().isRightChild() ); // árbol vacío
    }}

See also:: test_Bin_Tree<E>::test_isLeft_isRight()

Definition at line 283 of file Bin_Tree.h.

template<class E>

unsigned Bin_Tree< E >::use_count ( ) const [inline]

Cantidad de referencias de la raíz del árbol.

Definition at line 297 of file Bin_Tree.h.

Friends And Related Function Documentation

template<class E>

template<class T >

bool check_ok ( const Bin_Tree< T > & aT ) [friend]

Usa ok() para verificar la invariante de la clase.

template<class E>

template<class T >

bool operator==	(	const Bin_Tree< T > &	p,
		const Bin_Tree< T > &	q
	)		`[friend]`

¿¿¿ (p == q) ???

template<class E>

template<class T >

bool operator!=	(	const Bin_Tree< T > &	p,
		const Bin_Tree< T > &	q
	)		`[friend]`

¿¿¿ (p != q) ???

Member Data Documentation

template<class E>

lkptr< Bin_Tree_Node<E> > Bin_Tree< E >::m_root [private]

Un árbol "es" el puntero al nodo raíz.

Definition at line 56 of file Bin_Tree.h.

The documentation for this class was generated from the following file:

Bin_Tree.h

Public Types

Public Member Functions

Private Attributes

Constructores y destructor

Operaciones básicas

Operaciones de comparación

Detailed Description

template<class E> class Bin_Tree< E >

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Friends And Related Function Documentation

Member Data Documentation

template<class E>
class Bin_Tree< E >