Referencia de la Clase Bin_Tree< E >

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

#include <Bin_Tree.h>

Lista de todos los miembros.

Constructores y destructor
	Bin_Tree ()
	Constructor de vector: el árbol queda vacío.
	Bin_Tree (const Bin_Tree &other)
	Constructor de copia desde otro árbol (copia superficial).
	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 nodo.
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 E>
bool	operator== (const Bin_Tree< E > &p, const Bin_Tree< E > &q)
	¿¿¿ (p == q) ???
template<class E>
bool	operator!= (const Bin_Tree< E > &p, const Bin_Tree< E > &q)
	¿¿¿ (p != q) ???
Tipos públicos
typedef E	value_type
	Nombre estándar del tipo de elemento contenido.
Métodos públicos
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
Operaciones de borrado
void	erase ()
	Elimina el árbol y sus descendientes.
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 &	copyDeep (const Bin_Tree &other)
	Copia profunda de "other".
Bin_Tree &	operator= (const value_type &d)
	Usa changeRoot() para sustituir por "d" el valor almacenado en la raíz del árbol.
void	swap (Bin_Tree &other)
	Intercambia los valores de "*this" y "o".
void	move (Bin_Tree &other)
	Traslada a "*this" el valor de "other".
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	changeChild (unsigned n, const value_type &d)
	Sustituye por "d" el valor almacenado en el hijo número "n" 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".
Operaciones para usar los valores almacenados
value_type &	dato () 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
Bin_Tree	root () const
	Raíz del sub-árbol.
Bin_Tree	padre () 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	isLeaf () const
	Retorna "true" si el árbol es una hoja.
bool	isRoot () const
	Retorna "true" si el árbol no tiene padre.
unsigned	refs () const
	Cantidad de referencias de la raíz del árbol.
Atributos privados
lkptr< Bin_Tree_Node< E > >	m_root
	Un árbol "es" el puntero al nodo raíz.

---

Descripción detallada

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

Definición en la línea 52 del archivo Bin_Tree.h.

---

Documentación de los 'Tipos Definidos' miembros de la clase

template<class E>

typedef E Bin_Tree< E >::value_type

Nombre estándar del tipo de elemento contenido.

Definición en la línea 57 del archivo Bin_Tree.h.

---

Documentación del constructor y destructor

template<class E>

Bin_Tree< E >::Bin_Tree

(

)

[inline]

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

Definición en la línea 62 del archivo Bin_Tree.h.

template<class E>

template< class E > inline Bin_Tree< E >::Bin_Tree

(

const Bin_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.

  Complejidad:

  O( 1 ).

Definición en la línea 63 del archivo Bin_Tree.h.

template<class E>

Bin_Tree< E >::Bin_Tree

(

const value_type &

d

)

[inline]

Constructor a partir de un valor.

Definición en la línea 217 del archivo Bin_Tree.h.

template<class E>

Bin_Tree< E >::~Bin_Tree

(

)

Destructor.

Complejidad:

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

Ver también:

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

Definición en la línea 211 del archivo Bin_Tree.h.

template<class E>

Bin_Tree< E >::Bin_Tree

(

lkptr< Bin_Tree_Node< E > > &

other

)

[inline, private]

Constructor a partir de un nodo.

Definición en la línea 68 del archivo Bin_Tree.h.

---

Documentación de las funciones miembro

template<class E>

bool Bin_Tree< E >::isEmpty

(

)

const [inline]

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

Definición en la línea 74 del archivo 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.

  Ver también:

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

Definición en la línea 303 del archivo Bin_Tree.h.

template<class E>

unsigned Bin_Tree< E >::countChildren

(

)

const

Retorna la cantidad de hijos del árbol.

Complejidad:

O( 1 )

Definición en la línea 315 del archivo 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.

Definición en la línea 78 del archivo Bin_Tree.h.

template<class E>

bool Bin_Tree< E >::ok

(

)

const [inline]

Definición en la línea 81 del archivo Bin_Tree.h.

template<class E>

void Bin_Tree< E >::erase

(

)

[inline]

Elimina el árbol y sus descendientes.

• T.left().erase(); // No cambia "T" porque el que cambia es "T.left()"
• T.makeLeftChild( Bin_Tree<E>() ); // borra el hijo izquierdo
• T.makeRightChild( Bin_Tree<E>() ); // borra el hijo derecho

  Complejidad:

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

  Ver también:

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

Definición en la línea 96 del archivo 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).

Definición en la línea 103 del archivo Bin_Tree.h.

template<class E>

template< class E > void Bin_Tree< E >::copy

(

const Bin_Tree< E > &

o

)

[inline]

Copia superficial desde "o".

• El valor anterior de "*this" se pierde.

  Complejidad:

  O( 1 ).

  Devuelve:

  *this.

  Ver también:

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

Definición en la línea 104 del archivo Bin_Tree.h.

template<class E>

Bin_Tree< E > & Bin_Tree< E >::copyDeep

(

const Bin_Tree< E > &

other

)

Copia profunda de "other".

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

  Complejidad:

  O( count() ) + O( other.count() ).

  Devuelve:

  *this.

  Ver también:

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

Definición en la línea 487 del archivo 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.

Definición en la línea 107 del archivo 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 ).

Devuelve:

*this.

Ver también:

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

Definición en la línea 247 del archivo Bin_Tree.h.

template<class E>

void Bin_Tree< E >::move

(

Bin_Tree< E > &

other

)

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

  Devuelve:

  *this.

  Ver también:

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

Definición en la línea 277 del archivo 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.

Definición en la línea 339 del archivo Bin_Tree.h.

template<class E>

void Bin_Tree< E >::changeChild	(	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".
• Si "n" no es uno de {0,1} no hace nada.

Definición en la línea 353 del archivo 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.

  Precondición:

  ! isEmpty()

Definición en la línea 387 del archivo 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.

  Precondición:

  ! isEmpty()

Definición en la línea 399 del archivo Bin_Tree.h.

template<class E>

value_type& Bin_Tree< E >::dato

(

)

const [inline]

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

Definición en la línea 125 del archivo Bin_Tree.h.

template<class E>

value_type& Bin_Tree< E >::operator *

(

)

const [inline]

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

Definición en la línea 127 del archivo 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.

Definición en la línea 129 del archivo Bin_Tree.h.

template<class E>

bool Bin_Tree< E >::equals

(

const Bin_Tree< E > &

o

)

const [inline]

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

Definición en la línea 139 del archivo 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".

Definición en la línea 141 del archivo Bin_Tree.h.

template<class E>

Bin_Tree Bin_Tree< E >::root

(

)

const [inline]

Raíz del sub-árbol.

Definición en la línea 147 del archivo Bin_Tree.h.

template<class E>

Bin_Tree Bin_Tree< E >::padre

(

)

const [inline]

Acceso al padre.

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

Definición en la línea 150 del archivo 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.

Definición en la línea 156 del archivo 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.

Definición en la línea 163 del archivo 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.

Definición en la línea 172 del archivo 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.

Definición en la línea 185 del archivo 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.

Definición en la línea 190 del archivo Bin_Tree.h.

template<class E>

unsigned Bin_Tree< E >::refs

(

)

const [inline]

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

Definición en la línea 192 del archivo Bin_Tree.h.

---

Documentación de las funciones relacionadas y clases amigas

template<class E>

template<class E>

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

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

Definición en la línea 330 del archivo Bin_Tree.h.

template<class E>

template<class E>

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

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

Definición en la línea 333 del archivo Bin_Tree.h.

---

Documentación de los datos miembro

template<class E>

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

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

Definición en la línea 54 del archivo Bin_Tree.h.

---

La documentación para esta clase fué generada a partir del siguiente archivo:

• Bin_Tree.h

---