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

#include <Tree_L.h>

Public Types
typedef E	value_type
	Nombre estándar del tipo de elemento contenido. More...

Public Member Functions
Operaciones de copiado
Tree &	operator= (const Tree &o)
	Sinónimo de `this->Copy(o)` More...

Tree &	Copy (const Tree &o)
	Copia superficial desde `"o"`. More...

Tree &	Move (Tree &o)
	Traslada el valor de `"o"` a `"*this"`. More...

Tree &	Swap (Tree &o)
	Intercambia los valores de `"*this"` y `"o"`. More...

Tree &	Copy_Deep (const Tree &o)
	Copia profunda de `"o"`. More...

Tree &	operator= (const value_type &d)
	Usa `Change_Root()` para sustituir por "d" el valor almacenado en la raíz del árbol. More...

Métodos para cambiar los valores almacenados en el árbol
Tree	Change_Root (const value_type &d)
	Sustituye por `"d"` el valor almacenado en la raíz del árbol. More...

Tree	Change_Child (unsigned n, const value_type &d)
	Sustituye por `"d"` el valor almacenado en el hijo número `"n"` del árbol. More...

Tree	Change_Left_Sibling_Inmediate (const value_type &d)
	Sustituye por `"d"` el valor almacenado en el hermano inmediatamente anterior del sub-árbol. More...

Tree	Change_Right_Sibling_Inmediate (const value_type &d)
	Sustituye por `"d"` el valor almacenado en el hermano inmediatamente posterior del sub-árbol. More...

Tree	Graft (unsigned n, Tree &o)
	Injerta `"o"` para que sea el `"n"-ésimo` hijo de `"*this"`. More...

Operaciones para usar los valores almacenados
value_type &	Data ()
	Valor almacenado en la raíz del sub-árbol. More...

value_type &	operator* ()
	Valor almacenado en la raíz del sub-árbol. More...

value_type *	operator-> ()
	Puntero al valor almacenado en la raíz del sub-árbol. More...

const value_type &	Data () const
	Valor almacenado en la raíz del sub-árbol. More...

const value_type &	operator* () const
	Valor almacenado en la raíz del sub-árbol. More...

const value_type *	operator-> () const
	Puntero al valor almacenado en la raíz del sub-árbol. More...

Métodos para recorrer el árbol
Tree	Root () const
	Raíz del sub-árbol. More...

Tree	Father () const
	Acceso al padre. More...

Tree	Child (unsigned n) const
	Acceso al `"n"-ésimo` hijo. More...

Tree	Left () const
	Sub-árbol izquierdo [en un árbol binario]. More...

Tree	Right () const
	Sub-árbol derecho [en un árbol binario]. More...

Tree	Leftmost () const
	Obtiene el hijo más izquierdo del árbol. More...

Tree	Rightmost () const
	Obtiene el hijo más derecho del árbol. More...

Tree	Sibling (int n) const
	`"n"-ésimo` hermano a partir de `"*this"`. More...

Tree	Left_Sibling () const
	Obtiene el hermano no vacío anterior, que está hacia la izquierda. More...

Tree	Right_Sibling () const
	Obtiene el hermano no vacío siguiente, que está hacia la derecha. More...

Tree	Previous_Sibling () const
	Sinónimo de `Left_Sibling()` More...

Tree	Prev_Sibling () const
	Sinónimo de `Left_Sibling()` More...

Tree	Next_Sibling () const
	Sinónimo de `Right_Sibling()` More...

Tree	Right_Sibling_Inmediate () const
	Obtiene el hermano que está inmediatamente hacia la derecha. More...

Tree	Left_Sibling_Inmediate () const
	Obtiene el hermano que está inmediatamente hacia la izquierda. More...

Propiedades del árbol
unsigned	Child_Number () const
	Retorna `"n"` si `"*this"` es el n-ésimo hijo de su padre, si no retorna `0` (cero) More...

unsigned	Leftmost_N () const
	Retorna `"n"` si el hijo más izquierdo de `"*this"` es el n-ésimo hijo, si no retorna `0` (cero) More...

unsigned	Rightmost_N () const
	Retorna `"n"` si el hijo más derecho de `"*this"` es el n-ésimo hijo, si no retorna `0` (cero) More...

bool	Is_Leaf () const
	Retorna `"true"` si el árbol es una hoja. More...

bool	Is_Root () const
	Retorna `"true"` si el árbol no tiene padre. More...

unsigned	use_count () const
	Cantidad de referencias de la raíz del árbol. More...

Static Private Member Functions
Funciones para manipular valores a bajo nivel
static Tree &	CastTo_Sub_Tree_Ref (Tree_Node< E > *&p)
	Convierte el puntero al nodo en un referencia a `Tree`. More...

Funciones recursivas que realizan el trabajo sobre nodos
static void	Erase0 (Tree_Node< E > *p)
	Elimina recursivamente a `"*p"` y a todos sus descendientes. More...

static bool	Comp0 (const Tree_Node< E > p, const Tree_Node< E > q)
	Compara recursivamente los árboles cuyos nodo raíz son `"p"` y `"q"`. More...

static void	Count0 (const Tree_Node< E > *p, unsigned &n)
	Implementación recursiva para `Count()`. More...

static Tree_Node< E > *	Copy_Deep0 (const Tree_Node< E > *p)
	Hace una copia profunda nodo por nodo del árbol cuyo nodo raíz es `"*p"`. More...

Private Attributes
Tree_Node< E > *	m_root
	Un árbol "es" el puntero al nodo raíz. More...

Constructores y destructor
typedef void	NOT_null_pointer
	Truco para usar el constructor que no verifica `(p != 0)` More...

	Tree ()
	Constructor de vector. More...

	Tree (const Tree &o)
	Constructor de copia desde otro árbol (copia superficial). More...

	Tree (const value_type &d)
	Constructor a partir de un valor. More...

	~Tree ()
	Destructor. More...

	Tree (Tree_Node< E > *p)
	Constructor a partir de un nodo. More...

	Tree (NOT_null_pointer *p)
	Constructor a partir de un nodo [ requiere `p != 0` ]. More...

Operaciones básicas
bool	Empty () const
	Retorna `"true"` si el sub-árbol está vacío. More...

unsigned	Count () const
	Retorna la cantidad de valores almacenados en el sub-árbol. More...

unsigned	Count_Children () const
	Retorna la cantidad de hijos del árbol. More...

unsigned	Size () const
	Usa `Count()` para retornar la cantidad de valores almacenados en el sub-árbol. More...

bool	Ok ()
	Usa `check_ok(Tree& T)` para verificar la invariante de `Tree`. More...

bool	check_ok (const Tree< E > &T)
	Verifica que se cumpla la invariante de la clase, o sea, que el objeto esté bien construido. More...

Operaciones de borrado
void	Erase ()
	Elimina el árbol y sus descendientes. More...

void	Erase_Son (unsigned n)
	Elimina el sub-árbol número `"n"`. More...

void	Erase_Son_Prev (unsigned n, Tree_Node< E > *&)
	Elimina el sub-árbol número `"n-1"` y retorna un puntero al nodo anterior al borrado. More...

Operaciones de comparación
bool	Equals (const Tree &o) const
	¿¿¿ (*this==o) ??? More...

bool	Same (const Tree &o) const
	Retorna `true` si `"o"` comparte la raíz con `"*this"`. More...

template<class X >
bool	operator== (const Tree< X > &p, const Tree< X > &q)
	¿¿¿ (p == q) ??? More...

template<class X >
bool	operator!= (const Tree< X > &p, const Tree< X > &q)
	¿¿¿ (p != q) ??? More...

Detailed Description

template<class E>
class TL::Tree< E >

Los métodos para trabajar con árboles 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 Tree::Copy_Deep().
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 "cuentas de referencia" que impiden que métodos como Father() o Root() sean métodos const.
Muchos métodos retornan referencias Tree& porque es más eficiente, pues cada vez que un Tree es copiado hay que actualizar la "cuenta de referencia" de la raíz del sub-árbol.

Definition at line 25 of file Tree_L.h.

Member Typedef Documentation

template<class E>

typedef E TL::Tree< E >::value_type

Nombre estándar del tipo de elemento contenido.

Definition at line 70 of file Tree_L.h.

template<class E>

TL::Tree< E >::NOT_null_pointer

private

Truco para usar el constructor que no verifica (p != 0)

Truco para evitar comparar con 0 ( nil ) al usar Tree::Tree_Node<E>* para construir Tree().

Al implementar cada uno de los métodos de Tree con frecuencia ocurre que es posible saber que el sub-árbol retornado no está vacío. En estos casos, conviene usar un contructor que no verifique si la raíz del árbol es nula.

Esta clase se usa como una marca para que se ejecute el contructor Tree::Tree(NOT_null_pointer* p) que no verifica la nulidad de "m_root"; esta es una micro-eficiencia, pero aquí sirve para mostrar un truco que es muy usado en C++ para aumentar la eficiencia de los programas, pues le permite al programado usar la sobrecarga de operadores para evitar repetir verificaciones innecesarias.

See Also: http://www.di-mare.com/adolfo/binder/c01.htm#k1-micro-eficiencia

Definition at line 82 of file Tree_L.h.

Constructor & Destructor Documentation

template<class E>

TL::Tree< E >::Tree ( )

inline

Constructor de vector.

Definition at line 74 of file Tree_L.h.

template<class E >

TL::Tree< E >::Tree ( const Tree< E > & o )

inline

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.

Definition at line 237 of file Tree_L.h.

template<class E >

TL::Tree< E >::Tree ( const value_type & d )

inline

Constructor a partir de un valor.

Definition at line 262 of file Tree_L.h.

template<class E >

TL::Tree< E >::~Tree ( )

Destructor.

Complejidad:: O( Count() )

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

Definition at line 250 of file Tree_L.h.

template<class E>

TL::Tree< E >::Tree ( Tree_Node< E > * p )

inlineprivate

Constructor a partir de un nodo.

Definition at line 80 of file Tree_L.h.

template<class E>

TL::Tree< E >::Tree ( NOT_null_pointer * p )

inlineprivate

Constructor a partir de un nodo [ requiere p != 0 ].

Definition at line 84 of file Tree_L.h.

Member Function Documentation

template<class E>

bool TL::Tree< E >::Empty ( ) const

inline

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

Definition at line 91 of file Tree_L.h.

template<class E >

unsigned TL::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 770 of file Tree_L.h.

template<class E >

unsigned TL::Tree< E >::Count_Children ( ) const

Retorna la cantidad de hijos del árbol.

Complejidad:: O( Count_Children() )

Definition at line 784 of file Tree_L.h.

template<class E>

unsigned TL::Tree< E >::Size ( ) const

inline

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

Definition at line 94 of file Tree_L.h.

template<class E>

bool TL::Tree< E >::Ok ( )

inline

Usa check_ok(Tree& T) para verificar la invariante de Tree.

Definition at line 96 of file Tree_L.h.

template<class E >

void TL::Tree< E >::Erase ( )

Elimina el árbol y sus descendientes.

Complejidad:: O( Count() ) + O( Father().Count() ) ==> tiempo
O( Height() ) ==> espacio

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

Definition at line 1183 of file Tree_L.h.

template<class E>

void TL::Tree< E >::Erase_Son ( unsigned n )

inline

Elimina el sub-árbol número "n".

Complejidad:: O( Child(n).Count() ) ==> tiempo
O( Height( Child(n) ) ) ==> espacio

Definition at line 103 of file Tree_L.h.

template<class E >

void TL::Tree< E >::Erase_Son_Prev	(	unsigned	n,
		Tree_Node< E > *&	prev
	)

private

Elimina el sub-árbol número "n-1" y retorna un puntero al nodo anterior al borrado.

Esta es la rutina que en realidad hace el trabajo de Erase_Son().
Elimina el sub-árbol número "n-1", como también lo hace Erase_Son().
La única diferencia con Erase_Son() es que este método retorna un puntero al nodo anterior al nodo eliminado.
"prev" apunta al nodo que está antes de "prev" en el árbol.
Trabaja con "n-1" porque no incrementa el valor de "n", pues se supone que la rutina invocadora ya hizo ese ajuste en el valor originar de "n".
Esta rutina existe para compartir el código que se necesita para implementar Erase_Son() y Graft().
Si retorna 0 == NULL es porque Nodo[n-1] debe ser el primero en la lista de hijos del padre.

Remarks

[Eliminado porque ya no hace falta]

"prev_prev" apunta al nodo que está antes de "prev" en el árbol.
Si "prev" y "prev_prev" son la misma variable, el valor correcto para "prev" es calculado.

Definition at line 1257 of file Tree_L.h.

template<class E>

Tree& TL::Tree< E >::operator= ( const Tree< E > & o )

inline

Sinónimo de this->Copy(o)

Definition at line 111 of file Tree_L.h.

template<class E >

Tree< E > & TL::Tree< E >::Copy ( const Tree< E > & o )

Copia superficial desde "o".

El valor anterior de "*this" se pierde

Complejidad:: O( Count() )

Returns: *this

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

Definition at line 279 of file Tree_L.h.

template<class E >

Tree< E > & TL::Tree< E >::Move ( Tree< E > & o )

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

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

Complejidad:
O( Count() )

Returns
*this

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

Definition at line 311 of file Tree_L.h.

template<class E >

Tree< E > & TL::Tree< E >::Swap ( Tree< E > & o )

inline

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 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 Graft().

Complejidad:
O( 1 )

Returns
*this

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

Definition at line 342 of file Tree_L.h.

template<class E >

Tree< E > & TL::Tree< E >::Copy_Deep ( const Tree< E > & o )

Copia profunda de "o".

Copia todo el valor de "o" sobre "*this", de forma que el nuevo valor de "*this" sea un duplicado exacto del valor de "o"
El valor anterior de "*this" se pierde
El objeto "o" mantiene su valor anterior
Luego de la copia, cuando el valor de "o" cambia, el de "*this" no cambiará, y viceversa, pues la copia es una copia profunda; no es superficial
Si "*this" es "o" entonces su valor no cambia
Después de esta operación siempre ocurre que *this == o

Complejidad:: O( Count() ) + O( o.Count() )

Returns: *this

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

Definition at line 1405 of file Tree_L.h.

template<class E>

Tree& TL::Tree< E >::operator= ( const value_type & d )

inline

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

Definition at line 117 of file Tree_L.h.

template<class E >

Tree< E > TL::Tree< E >::Change_Root ( const value_type & d )

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

Si el árbol está vacío, le agrega el nodo raíz.
Returns
*this

Definition at line 926 of file Tree_L.h.

template<class E >

Tree< E > TL::Tree< E >::Change_Child	(	unsigned	n,
		const value_type &	d
	)

Sustituye por "d" el valor almacenado en el hijo número "n" del árbol.

Si no existe el hijo número "n", lo agrega como una hoja con valor "d"
Si ya existe el hijo número "n", le sustituye su valor por "d"

Precondition: !Empty() && (0 <= n) && (n < infinito)

Complejidad:: O( Count_Children() )

Returns: Child(n)

Definition at line 949 of file Tree_L.h.

template<class E >

Tree< E > TL::Tree< E >::Change_Left_Sibling_Inmediate ( const value_type & d )

Sustituye por "d" el valor almacenado en el hermano inmediatamente anterior del sub-árbol.

Si n == Child_Number() cambia el valor del hijo número "n-1" de Father()
Si no existe el hijo número "n-1" de Father() lo agrega como una hoja con valor "d"
Si ya existe ese hijo número "n-1", le sustituye su valor por "d"
Retorna un árbol vacío si no es posible que exista el hijo número "n-1" de Father()

Precondition: !Empty() && (1 <= Child_Number())

Complejidad:: O( Father().Count_Children() )

Returns: El hermano izquierdo, Sibling(-1)

Definition at line 1042 of file Tree_L.h.

template<class E >

Tree< E > TL::Tree< E >::Change_Right_Sibling_Inmediate ( const value_type & d )

Sustituye por "d" el valor almacenado en el hermano inmediatamente posterior del sub-árbol.

Si n == Child_Number() cambia el valor del hijo número "n+1" de Father()
Si no existe el hijo número "n+1" de Father() lo agrega como una hoja con valor "d"
Si ya existe ese hijo número "n+1", le sustituye su valor por "d"
Retorna un árbol vacío si no es posible que exista el hijo número "n+1" de Father()

Precondition: !Empty() && ( Child_Number() < infinito )

Complejidad:: O( 1 )

Returns: El hermano derecho, Sibling(+1)

Definition at line 1066 of file Tree_L.h.

template<class E >

Tree< E > TL::Tree< E >::Graft	(	unsigned	n,
		Tree< E > &	o
	)

Injerta "o" para que sea el "n"-ésimo hijo de "*this".

Si "o" es sub-árbol de otro árbol, dejara de serlo para pasar ser hijo de "*this"
Si "*this" tiene un "n"-ésimo hijo, ese hijo desaparece
Si "o" está vacío, elimina el "n"-ésimo hijo del árbol [ Erase_Son(n) ]

Precondition

! Root().Empty()
- Si el árbol está vacío no tiene raíz, y por lo tanto tampoco puede tener hijos
! Ancestor(o, *this)
- "o" no puede ser ancestro de *this"
(0 <= n) && (n < infinito)
! Root(). Same( o.Root() )

Postcondition

"o" deja de ser sub-árbol del árbol en que estaba
o.Father() .Same( Root() )

Remarks

Un sub-árbol puede ser hijo (o sub-árbol) de otro árbol
Un sub-árbol puede ser hijo únicamente de un árbol
Este método no hace nada cuando [ ! Root() .Same( o.Root() ) ]
Injertar un sub-árbol vacío es una forma de eliminar a un hijo junto con toda su descendencia

Returns: "o" ==> El árbol recién injertado

Complejidad::: O( Count_Children() ) + O( o.Father().Count_Children() )

Definition at line 1456 of file Tree_L.h.

template<class E>

value_type& TL::Tree< E >::Data ( )

inline

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

Definition at line 133 of file Tree_L.h.

template<class E>

value_type& TL::Tree< E >::operator* ( )

inline

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

Definition at line 134 of file Tree_L.h.

template<class E>

value_type* TL::Tree< E >::operator-> ( )

inline

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

Definition at line 135 of file Tree_L.h.

template<class E>

const value_type& TL::Tree< E >::Data ( ) const

inline

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

Definition at line 136 of file Tree_L.h.

template<class E>

const value_type& TL::Tree< E >::operator* ( ) const

inline

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

Definition at line 137 of file Tree_L.h.

template<class E>

const value_type* TL::Tree< E >::operator-> ( ) const

inline

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

Definition at line 138 of file Tree_L.h.

template<class E>

bool TL::Tree< E >::Equals ( const Tree< E > & o ) const

inline

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

Definition at line 146 of file Tree_L.h.

template<class E>

bool TL::Tree< E >::Same ( const Tree< E > & o ) const

inline

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

Definition at line 148 of file Tree_L.h.

template<class E>

Tree TL::Tree< E >::Root ( ) const

inline

Raíz del sub-árbol.

Definition at line 154 of file Tree_L.h.

template<class E >

Tree< E > TL::Tree< E >::Father ( ) const

Acceso al padre.

Si el sub-árbol no tiene padre retorna el árbol vacío.

Complejidad:: O( Father().Count_Children() )

Definition at line 355 of file Tree_L.h.

template<class E >

Tree< E > TL::Tree< E >::Child ( unsigned n ) const

Acceso al "n"-ésimo hijo.

Si el sub-árbol no tiene un hijo número "n" retorna el sub-árbol vacío.

Complejidad:: O( Father().Count_Children() )

Definition at line 375 of file Tree_L.h.

template<class E >

Tree< E > TL::Tree< E >::Left ( ) const

inline

Sub-árbol izquierdo [en un árbol binario].

Sinónimo de Child(0).
Complejidad:
O( 1 )

Definition at line 429 of file Tree_L.h.

template<class E >

Tree< E > TL::Tree< E >::Right ( ) const

Sub-árbol derecho [en un árbol binario].

Sinónimo de Child(1).

Complejidad:: O( 1 )

Definition at line 445 of file Tree_L.h.

template<class E >

Tree< E > TL::Tree< E >::Leftmost ( ) const

inline

Obtiene el hijo más izquierdo del árbol.

Este método usualmente se usa junto con Right_Sibling()

Complejidad:: O( 1 )

Remarks: Esta es una forma de procesar los hijos no vacíos de un sub-árbol de izquierda a derecha:

Tree<E> Child = T.Leftmost();
while ( ! Child.Empty() ) {
    Process( Child );
    Child = Child.Right_Sibling();
}

Definition at line 698 of file Tree_L.h.

template<class E >

Tree< E > TL::Tree< E >::Rightmost ( ) const

Obtiene el hijo más derecho del árbol.

Este método usualmente se usa junto con Left_Sibling()

Complejidad:: O( Count_Children() )

Remarks: Esta es una forma de procesar los hijos no vacíos de un sub-árbol de derecha a izquierda:

Tree<E> Child = T.Rightmost();
while ( ! Child.Empty() ) {
    Process( Child );
    Child = Child.Left_Sibling();
}

Definition at line 721 of file Tree_L.h.

template<class E >

Tree< E > TL::Tree< E >::Sibling ( int n ) const

"n"-ésimo hermano a partir de "*this".

El hermano puede ser vacío aunque haya otros hermanos que no son vacíos.
Se "corre" hacia el n-ésimo hermano "n" "posiciones".
El hermano se determina contando sub-árboles hacia la derecha o izquierda de acuerdo al signo de "n":
- Si n=0, regresa "*this".
- Si n>0, regresa el hermano número "+n" contando hacia la derecha de "*this".
- Si n<0, regresa el hermano número "-n" contando hacia la izquierda de "*this".
Si no existe un hermano número "n" retorna un sub-árbol vacío.
El árbol "T" tiene 3 hijos no vacíos "B", "C" y "E" y tiene 4 sub-árboles:
- C.Sibling( +0 ) == C
- B.Sibling( +1 ) == C
- E.Sibling( -2 ) == C
- E.Sibling( -1 ) –> Vacío
- A.Sibling( +1 ) –> Vacío
- B.Sibling( -1 ) –> Vacío
- E.Sibling( +1 ) –> Vacío
  A <-- T
  
  /|\
  
  / / \ \ [] --> es representa un sub-árbol vacío
  
  B C [] E

Complejidad:: O( Father().Count_Children() )

Definition at line 625 of file Tree_L.h.

template<class E >

Tree< E > TL::Tree< E >::Left_Sibling ( ) const

Obtiene el hermano no vacío anterior, que está hacia la izquierda.

Si no existe un hermano no vacío hacia la izquierda, retorna un sub-árbol vacío.
Si n == Child_Number() no necesariamente ocurrirá que (n-1)== Left_Sibling().Child_Number() pues los anteriores hijos de Father() pueden ser sub-árboles vacíos, como ocurre si un árbol binario tiene hijo derecho pero no tiene hijo izquierdo.
Este método usualmente se usa junto con Rightmost()

Complejidad:: O( Father().Count_Children() )

Definition at line 474 of file Tree_L.h.

template<class E >

Tree< E > TL::Tree< E >::Right_Sibling ( ) const

Obtiene el hermano no vacío siguiente, que está hacia la derecha.

Si no existe un hermano hacia la derecha, retorna un sub-árbol vacío.
Si n == Child_Number() no necesariamente ocurrirá que (n+1) == Right_Sibling().Child_Number() pues los siguientes hijos de Father() pueden ser sub-árboles vacíos, como ocurre si un árbol binario tiene hijo izquierdo pero no tiene hijo derecho.
Este método usualmente se usa junto con Leftmost()

Complejidad:: O( 1 )

Definition at line 521 of file Tree_L.h.

template<class E>

Tree TL::Tree< E >::Previous_Sibling ( ) const

inline

Sinónimo de Left_Sibling()

Definition at line 164 of file Tree_L.h.

template<class E>

Tree TL::Tree< E >::Prev_Sibling ( ) const

inline

Sinónimo de Left_Sibling()

Definition at line 165 of file Tree_L.h.

template<class E>

Tree TL::Tree< E >::Next_Sibling ( ) const

inline

Sinónimo de Right_Sibling()

Definition at line 166 of file Tree_L.h.

template<class E >

Tree< E > TL::Tree< E >::Right_Sibling_Inmediate ( ) const

Obtiene el hermano que está inmediatamente hacia la derecha.

Este método es equivalente a invocar Sibling( +1 )
Si no existe ese hermano hacia la derecha, retorna un sub-árbol vacío.

Complejidad:: O( 1 )

Definition at line 551 of file Tree_L.h.

template<class E >

Tree< E > TL::Tree< E >::Left_Sibling_Inmediate ( ) const

inline

Obtiene el hermano que está inmediatamente hacia la izquierda.

Este método es equivalente a invocar Sibling( -1 )
Si no existe un hermano hacia la derecha, retorna un sub-árbol vacío.

Complejidad:: O( Father().Count_Children() )

Definition at line 540 of file Tree_L.h.

template<class E>

unsigned TL::Tree< E >::Child_Number ( ) const

inline

Retorna "n" si "*this" es el n-ésimo hijo de su padre, si no retorna 0 (cero)

Definition at line 175 of file Tree_L.h.

template<class E>

unsigned TL::Tree< E >::Leftmost_N ( ) const

inline

Retorna "n" si el hijo más izquierdo de "*this" es el n-ésimo hijo, si no retorna 0 (cero)

Definition at line 177 of file Tree_L.h.

template<class E>

unsigned TL::Tree< E >::Rightmost_N ( ) const

inline

Retorna "n" si el hijo más derecho de "*this" es el n-ésimo hijo, si no retorna 0 (cero)

Definition at line 179 of file Tree_L.h.

template<class E>

bool TL::Tree< E >::Is_Leaf ( ) const

inline

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

Definition at line 181 of file Tree_L.h.

template<class E>

bool TL::Tree< E >::Is_Root ( ) const

inline

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

Definition at line 183 of file Tree_L.h.

template<class E>

unsigned TL::Tree< E >::use_count ( ) const

inline

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

Definition at line 185 of file Tree_L.h.

template<class E>

static Tree& TL::Tree< E >::CastTo_Sub_Tree_Ref ( Tree_Node< E > *& p )

inlinestaticprivate

Convierte el puntero al nodo en un referencia a Tree.

Definition at line 192 of file Tree_L.h.

template<class E >

void TL::Tree< E >::Erase0 ( Tree_Node< E > * p )

staticprivate

Elimina recursivamente a "*p" y a todos sus descendientes.

Implementación recursiva para Erase()
Borra el nodo sólo después de que constata que ya no hay punteros que le apunten
No saca a "*p" de la lista de hijos del padre ==> ese es el trabajo de Graft() o Erase()
La rutina llamadora invoca Erase0() porque sabe que al decrementar "p->m_refCount" queda en cero
No decrementa "p->m_refCount" porque ya el invocador sabe que hay que destruir "*p"
Recursivamente, borra a los descendientes de "*p"

// Forma usual de invocación
if ( child->m_refCount <= 1 ) { // Ya no hay más referencias a "child"
    Erase0( child ); // lo elimina
} else {
    child->m_refCount--; // uno menos le apunta
    child->m_n_child = -1;
    child->m_right_brother = 0; // ya no es hijo de nadie
}

Precondition: (p != 0) && (p->m_refCount == 1)

Postcondition: No cambia "p" porque trabaja con una copia de su valor

Definition at line 1129 of file Tree_L.h.

template<class E >

bool TL::Tree< E >::Comp0	(	const Tree_Node< E > *	p,
		const Tree_Node< E > *	q
	)

staticprivate

Compara recursivamente los árboles cuyos nodo raíz son "*p" y "*q".

Implementación recursiva para operator==(Tree, Tree) .

Definition at line 811 of file Tree_L.h.

template<class E >

void TL::Tree< E >::Count0	(	const Tree_Node< E > *	p,
		unsigned &	n
	)

staticprivate

Implementación recursiva para Count().

Incrementa "n" en el número de hijos que tiene el sub-árbol cuya raíz es "p"
Cambia el valor de "n"
No cuenta el nodo raíz "p"
Esta función complementa a Count()

Precondition: p != 0

Definition at line 744 of file Tree_L.h.

template<class E >

Tree_Node< E > * TL::Tree< E >::Copy_Deep0 ( const Tree_Node< E > * p )

staticprivate

Hace una copia profunda nodo por nodo del árbol cuyo nodo raíz es "*p".

Implementación recursiva para Tree::Copy_Deep()
No altera p->m_refCount porque copia los nodos
El campo p->m_right_brother queda con basura porque no queda inicializado
Le corresponde a la rutina invocadora inicializar p->m_right_brother

Precondition: p != 0

Postcondition: No cambia "p" porque trabaja con una copia de su valor

Returns: Puntero al nodo raíz del árbol copiado

Definition at line 1367 of file Tree_L.h.

Friends And Related Function Documentation

template<class E>

bool check_ok ( const Tree< E > & T )

friend

Verifica que se cumpla la invariante de la clase, o sea, que el objeto esté bien construido.

La razón por la que esta función no es un método es continuar la costumbre de muchos programadores quienes no definen la invariante para sus clases, pues en muchos casos sobra hacerlo.
No invoca check_ok( value_type& ) para cada valor almacenado, aunque si el árbol cumple con su invariante necesariamentes es porque también sus elementos almacenados están bien construidos.
Esta función en general es difícil de implementar, y en algunos casos es imposible pues, cuando el objeto no está bien construido, puede ocurrir que la función no retorne (como ocurriria si un nodo interno del árbol apunta de vuelta a la raíz, lo que se resulta en un círculo).
En general, la implementáción de esta función no es completa pues hay casos en que es imposible verificar la invariante de una clase.

Complejidad:: O( Count() ) ==> tiempo
O( Height() ) ==> espacio

Postcondition: Retorna "true" si el árbol es un objeto bien construido

See Also: check_ok(Tree&); http://www.di-mare.com/adolfo/binder/c04.htm#sc11

template<class E>

template<class X >

bool operator==	(	const Tree< X > &	p,
		const Tree< X > &	q
	)

friend

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

template<class E>

template<class X >

bool operator!=	(	const Tree< X > &	p,
		const Tree< X > &	q
	)

friend

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

Member Data Documentation

template<class E>

Tree_Node<E>* TL::Tree< E >::m_root

private

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

Definition at line 205 of file Tree_L.h.

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

Tree_L.h

Public Types

Public Member Functions

Static Private Member Functions

Private Attributes

Constructores y destructor

Operaciones básicas

Operaciones de borrado

Operaciones de comparación

Detailed Description

template<class E> class TL::Tree< E >

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Friends And Related Function Documentation

Member Data Documentation

template<class E>
class TL::Tree< E >