Página principal | Lista de namespace | Lista de componentes | Lista de archivos | Miembros del Namespace  | Miembros de las clases | Archivos de los miembros | Páginas relacionadas

Referencia de la Clase TL::Tree

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

#include <Tree_L.h>

Lista de todos los miembros.

Constructores y destructor

 Tree ()
 Constructor de vector.
 Tree (Tree &o)
 Constructor de copia desde otro árbol (copia superficial).
 Tree (const value_type &d)
 Constructor a partir de un valor.
 ~Tree ()
 Destructor.
typedef void NOT_null_pointer
 Truco para evitar comparar con 0 ( nil ) al usar Tree::Node* para construir Tree().
 Tree (Node *p)
 Constructor a partir de un nodo.
 Tree (NOT_null_pointer *p)
 Constructor a partir de un nodo [ requiere p != 0 ].

Operaciones básicas

bool Empty () const
 Retorna "true" si el sub-árbol está vacío.
unsigned Count () const
 Retorna la cantidad de valores almacenados en el sub-árbol.
unsigned Count_Children () 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 ()
 Usa Check_Ok(Tree& T) para verificar la invariante de Tree.
bool Check_Ok (Tree &T)
 Verifica que se cumpla la invariante de la clase, o sea, que el objeto esté bien construido.

Operaciones de borrado

void Erase ()
 Elimina el árbol y sus descendientes.
void Erase_Son (unsigned n)
 Elimina el sub-árbol número "n".
void Erase_Son_Prev (unsigned n, Node *&)
 Elimina el sub-árbol número "n-1" y retorna un puntero al nodo anterior al borrado.

Operaciones de comparación

bool Equals (const Tree &o) const
 ¿¿¿ (*this==o) ???
bool Same (const Tree &o) const
 Retorna true si "o" comparte la raíz con "*this".
bool operator== (const Tree &p, const Tree &q)
 ¿¿¿ (p == q) ???
bool operator!= (const Tree &p, const Tree &q)
 ¿¿¿ (p != q) ???

Tipos públicos

typedef Elem_Tree value_type
 Nombre estándar del tipo de elemento contenido.

Métodos públicos

Operaciones de copiado
Tree & operator= (Tree &o)
 Sinónimo de this->Copy(o).
Tree & Copy (Tree &o)
 Copia superficial desde "o".
Tree & Move (Tree &o)
 Traslada el valor de "o" a "*this".
Tree & Swap (Tree &o)
 Intercambia los valores de "*this" y "o".
Tree & Copy_Deep (const Tree &o)
 Copia profunda de "o".
Tree & operator= (const value_type &d)
 Usa Change_Root() para sustituir por "d" el valor almacenado en la raíz del árbol.
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.
Tree Change_Child (unsigned n, const value_type &d)
 Sustituye por "d" el valor almacenado en el hijo número "n" del árbol.
Tree Change_Left_Sibling_Inmediate (const value_type &d)
 Sustituye por "d" el valor almacenado en el hermano inmediatamente anterior del sub-árbol.
Tree Change_Right_Sibling_Inmediate (const value_type &d)
 Sustituye por "d" el valor almacenado en el hermano inmediatamente posterior del sub-árbol.
Tree Graft (unsigned n, Tree &o)
 Injerta "o" para que sea el "n"-ésimo hijo de "*this".
Operaciones para usar los valores almacenados
value_type & Data ()
 Valor almacenado en la raíz del sub-árbol.
value_type & operator * ()
 Valor almacenado en la raíz del sub-árbol.
value_type * operator-> ()
 Puntero al valor almacenado en la raíz del sub-árbol.
Métodos para recorrer el árbol
Tree Root ()
 Raíz del sub-árbol.
Tree Father ()
 Acceso al padre.
Tree Child (unsigned n)
 Acceso al "n"-ésimo hijo.
Tree Left ()
 Sub-árbol izquierdo [en un árbol binario].
Tree Right ()
 Sub-árbol derecho [en un árbol binario].
Tree Leftmost ()
 Obtiene el hijo más izquierdo del árbol.
Tree Rightmost ()
 Obtiene el hijo más derecho del árbol.
Tree Sibling (int n)
 "n"-ésimo hermano a partir de "*this".
Tree Left_Sibling ()
 Obtiene el hermano no vacío anterior, que está hacia la izquierda.
Tree Right_Sibling ()
 Obtiene el hermano no vacío siguiente, que está hacia la derecha.
Tree Previous_Sibling ()
 Sinónimo de Left_Sibling().
Tree Prev_Sibling ()
 Sinónimo de Left_Sibling().
Tree Next_Sibling ()
 Sinónimo de Right_Sibling().
Tree Right_Sibling_Inmediate ()
 Obtiene el hermano que está inmediatamente hacia la derecha.
Tree Left_Sibling_Inmediate ()
 Obtiene el hermano que está inmediatamente hacia la izquierda.
Propiedades del árbol
unsigned Child_Number ()
 Retorna "n" si "*this" es el n-ésimo hijo de su padre, si no retorna 0 (cero).
unsigned Leftmost_N ()
 Retorna "n" si el hijo más izquierdo de "*this" es el n-ésimo hijo, si no retorna 0 (cero).
unsigned Rightmost_N ()
 Retorna "n" si el hijo más derecho de "*this" es el n-ésimo hijo, si no retorna 0 (cero).
bool Is_Leaf ()
 Retorna "true" si el árbol es una hoja.
bool Is_Root ()
 Retorna "true" si el árbol no tiene padre.
unsigned Nref ()
 Cantidad de referencias de la raíz del árbol.

Métodos privados estáticos

Funciones para manipular valores a bajo nivel
Tree & CastTo_Sub_Tree_Ref (Node *&p)
 Convierte el puntero al nodo en un referencia a Tree.
Funciones recursivas que realizan el trabajo sobre nodos
void Erase0 (Node *p)
 Elimina recursivamente a "*p" y a todos sus descendientes.
bool Comp0 (const Node *p, const Node *q)
 Compara recursivamente los árboles cuyos nodo raíz son "*p" y "*q".
void Count0 (const Node *p, unsigned &n)
 Implementación recursiva para Count().
Node * Copy_Deep0 (const Node *p)
 Hace una copia profunda nodo por nodo del árbol cuyo nodo raíz es "*p".

Atributos privados

Tree::Node * _root
 Un árbol "es" el puntero al nodo raíz.

Descripción detallada

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

Definición en la línea 44 del archivo Tree_L.h.

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

typedef Elem_Tree TL::Tree::value_type
 

Nombre estándar del tipo de elemento contenido.

Definición en la línea 46 del archivo Tree_L.h.

TL::Tree::NOT_null_pointer [private]
 

Truco para evitar comparar con 0 ( nil ) al usar Tree::Node* 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 "_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.

Ver también:
http://www.di-mare.com/adolfo/binder/c01.htm#k1-micro-eficiencia

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

Documentación del constructor y destructor

TL::Tree::Tree (   )  [inline]
 

Constructor de vector.

Definición en la línea 73 del archivo Tree_L.h.

TL::Tree::Tree (  Tree &  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.

Definición en la línea 232 del archivo Tree_L.h.

TL::Tree::Tree (  const value_type &  d  )  [inline]
 

Constructor a partir de un valor.

Definición en la línea 257 del archivo Tree_L.h.

TL::Tree::~Tree (   ) 
 

Destructor.

Complejidad:
O( Count() )
Ver también:
http://www.di-mare.com/adolfo/binder/c04.htm#sc04

Definición en la línea 246 del archivo Tree_L.h.

TL::Tree::Tree (  Node *  p  )  [inline, private]
 

Constructor a partir de un nodo.

Definición en la línea 79 del archivo Tree_L.h.

TL::Tree::Tree (  NOT_null_pointer *  p  )  [inline, private]
 

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

Definición en la línea 83 del archivo Tree_L.h.

Documentación de las funciones miembro

bool TL::Tree::Empty (   )  const [inline]
 

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

Definición en la línea 90 del archivo Tree_L.h.

unsigned TL::Tree::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 783 del archivo Tree_L.h.

unsigned TL::Tree::Count_Children (   )  const
 

Retorna la cantidad de hijos del árbol.

Complejidad:
O( Count_Children() )

Definición en la línea 798 del archivo Tree_L.h.

unsigned TL::Tree::Size (   )  const [inline]
 

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

Definición en la línea 93 del archivo Tree_L.h.

bool TL::Tree::Ok (   )  [inline]
 

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

Definición en la línea 95 del archivo Tree_L.h.

void TL::Tree::Erase (   ) 
 

Elimina el árbol y sus descendientes.

Complejidad:
O( Count() ) + O( Father().Count() ) ==> tiempo
O( Height() ) ==> espacio
Ver también:
http://www.di-mare.com/adolfo/binder/c04.htm#sc03

Definición en la línea 1205 del archivo Tree_L.h.

void TL::Tree::Erase_Son (  unsigned  n  )  [inline]
 

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

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

Definición en la línea 102 del archivo Tree_L.h.

void TL::Tree::Erase_Son_Prev (  unsigned  n,
Node *&  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.

Comentarios:
[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.

Definición en la línea 1280 del archivo Tree_L.h.

Tree& TL::Tree::operator= (  Tree &  o  )  [inline]
 

Sinónimo de this->Copy(o).

Definición en la línea 110 del archivo Tree_L.h.

Tree & TL::Tree::Copy (  Tree &  o  ) 
 

Copia superficial desde "o".

  • El valor anterior de "*this" se pierde

Complejidad:
O( Count() )
Devuelve:
*this
Ver también:
http://www.di-mare.com/adolfo/binder/c04.htm#sc05

Definición en la línea 275 del archivo Tree_L.h.

Tree & TL::Tree::Move (  Tree &  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() )
Devuelve:
*this
Ver también:
http://www.di-mare.com/adolfo/binder/c04.htm#sc07

Definición en la línea 308 del archivo Tree_L.h.

Tree & TL::Tree::Swap (  Tree &  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 )
Devuelve:
*this
Ver también:
http://www.di-mare.com/adolfo/binder/c04.htm#sc08

Definición en la línea 340 del archivo Tree_L.h.

Tree & TL::Tree::Copy_Deep (  const Tree &  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() )
Devuelve:
*this
Ver también:
http://www.di-mare.com/adolfo/binder/c04.htm#sc05

Definición en la línea 1431 del archivo Tree_L.h.

Tree& TL::Tree::operator= (  const value_type &  d  )  [inline]
 

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

Definición en la línea 116 del archivo Tree_L.h.

Tree TL::Tree::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.

Devuelve:
*this

Definición en la línea 943 del archivo Tree_L.h.

Tree TL::Tree::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"

Precondición:
!Empty() && (0 <= n) && (n < infinito)
Complejidad:
O( Count_Children() )
Devuelve:
Child(n)

Definición en la línea 967 del archivo Tree_L.h.

Tree TL::Tree::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()

Precondición:
!Empty() && (1 <= Child_Number())
Complejidad:
O( Father().Count_Children() )
Devuelve:
El hermano izquierdo, Sibling(-1)

Definición en la línea 1061 del archivo Tree_L.h.

Tree TL::Tree::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()

Precondición:
!Empty() && ( Child_Number() < infinito )
Complejidad:
O( 1 )
Devuelve:
El hermano derecho, Sibling(+1)

Definición en la línea 1086 del archivo Tree_L.h.

Tree TL::Tree::Graft (  unsigned  n,
Tree &  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) ]

Precondición:
  • ! 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() )
Postcondición:
  • "o" deja de ser sub-árbol del árbol en que estaba
  • o.Father() .Same( Root() )
Comentarios:
  • 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
Devuelve:
"o" ==> El árbol recién injertado
Complejidad::
O( Count_Children() ) + O( o.Father().Count_Children() )

Definición en la línea 1484 del archivo Tree_L.h.

value_type& TL::Tree::Data (   )  [inline]
 

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

Definición en la línea 132 del archivo Tree_L.h.

value_type& TL::Tree::operator * (   )  [inline]
 

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

Definición en la línea 133 del archivo Tree_L.h.

value_type* TL::Tree::operator-> (   )  [inline]
 

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

Definición en la línea 134 del archivo Tree_L.h.

bool TL::Tree::Equals (  const Tree &  o  )  const [inline]
 

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

Definición en la línea 142 del archivo Tree_L.h.

bool TL::Tree::Same (  const Tree &  o  )  const [inline]
 

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

Definición en la línea 144 del archivo Tree_L.h.

Tree TL::Tree::Root (   )  [inline]
 

Raíz del sub-árbol.

Definición en la línea 150 del archivo Tree_L.h.

Tree TL::Tree::Father (   ) 
 

Acceso al padre.

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

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

Definición en la línea 355 del archivo Tree_L.h.

Tree TL::Tree::Child (  unsigned  n  ) 
 

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

Definición en la línea 376 del archivo Tree_L.h.

Tree TL::Tree::Left (   )  [inline]
 

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

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

Definición en la línea 431 del archivo Tree_L.h.

Tree TL::Tree::Right (   ) 
 

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

  • Sinónimo de Child(1).

Complejidad:
O( 1 )

Definición en la línea 448 del archivo Tree_L.h.

Tree TL::Tree::Leftmost (   )  [inline]
 

Obtiene el hijo más izquierdo del árbol.

Complejidad:
O( 1 )
Comentarios:
Esta es una forma de procesar los hijos no vacíos de un sub-árbol de izquierda a derecha:
    Tree Child = T.Leftmost();
    while ( ! Child.Empty() ) {
        Process( Child );
        Child = Child.Right_Sibling();
    }

Definición en la línea 708 del archivo Tree_L.h.

Tree TL::Tree::Rightmost (   ) 
 

Obtiene el hijo más derecho del árbol.

Complejidad:
O( Count_Children() )
Comentarios:
Esta es una forma de procesar los hijos no vacíos de un sub-árbol de derecha a izquierda:
    Tree Child = T.Rightmost();
    while ( ! Child.Empty() ) {
        Process( Child );
        Child = Child.Left_Sibling();
    }

Definición en la línea 732 del archivo Tree_L.h.

Tree TL::Tree::Sibling (  int  n  ) 
 

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

Definición en la línea 634 del archivo Tree_L.h.

Tree TL::Tree::Left_Sibling (   ) 
 

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

Definición en la línea 478 del archivo Tree_L.h.

Tree TL::Tree::Right_Sibling (   ) 
 

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 )

Definición en la línea 526 del archivo Tree_L.h.

Tree TL::Tree::Previous_Sibling (   )  [inline]
 

Sinónimo de Left_Sibling().

Definición en la línea 160 del archivo Tree_L.h.

Tree TL::Tree::Prev_Sibling (   )  [inline]
 

Sinónimo de Left_Sibling().

Definición en la línea 161 del archivo Tree_L.h.

Tree TL::Tree::Next_Sibling (   )  [inline]
 

Sinónimo de Right_Sibling().

Definición en la línea 162 del archivo Tree_L.h.

Tree TL::Tree::Right_Sibling_Inmediate (   ) 
 

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 )

Definición en la línea 558 del archivo Tree_L.h.

Tree TL::Tree::Left_Sibling_Inmediate (   )  [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() )

Definición en la línea 546 del archivo Tree_L.h.

unsigned TL::Tree::Child_Number (   )  [inline]
 

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

Definición en la línea 171 del archivo Tree_L.h.

unsigned TL::Tree::Leftmost_N (   )  [inline]
 

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

Definición en la línea 173 del archivo Tree_L.h.

unsigned TL::Tree::Rightmost_N (   )  [inline]
 

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

Definición en la línea 175 del archivo Tree_L.h.

bool TL::Tree::Is_Leaf (   )  [inline]
 

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

Definición en la línea 177 del archivo Tree_L.h.

bool TL::Tree::Is_Root (   )  [inline]
 

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

Definición en la línea 179 del archivo Tree_L.h.

unsigned TL::Tree::Nref (   )  [inline]
 

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

Definición en la línea 181 del archivo Tree_L.h.

Tree& TL::Tree::CastTo_Sub_Tree_Ref (  Node *&  p  )  [inline, static, private]
 

Convierte el puntero al nodo en un referencia a Tree.

Definición en la línea 187 del archivo Tree_L.h.

void TL::Tree::Erase0 (  Tree::Node *  p  )  [static, private]
 

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->_refCount" queda en cero
  • No decrementa "p->_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->_refCount <= 1 ) { // Ya no hay más referencias a "child"
        Erase0( child ); // lo elimina
    } else {
        child->_refCount--; // uno menos le apunta
        child->_n_child = -1;
        child->_right_brother = 0; // ya no es hijo de nadie
    }

Precondición:
(p != 0) && (p->_refCount == 1)
Postcondición:
No cambia "p" porque trabaja con una copia de su valor

Definición en la línea 1150 del archivo Tree_L.h.

bool TL::Tree::Comp0 (  const Node *  p,
const Node *  q
)  [static, private]
 

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

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

Definición en la línea 825 del archivo Tree_L.h.

void TL::Tree::Count0 (  const Node *  p,
unsigned &  n
)  [static, private]
 

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

Precondición:
p != 0

Definición en la línea 756 del archivo Tree_L.h.

Tree::Node * TL::Tree::Copy_Deep0 (  const Node *  p  )  [static, private]
 

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->_refCount porque copia los nodos
  • El campo p->_right_brother queda con basura porque no queda inicializado
  • Le corresponde a la rutina invocadora inicializar p->_right_brother

Precondición:
p != 0
Postcondición:
No cambia "p" porque trabaja con una copia de su valor
Devuelve:
Puntero al nodo raíz del árbol copiado

Definición en la línea 1392 del archivo Tree_L.h.

Documentación de las funciones relacionadas y clases amigas

bool Check_Ok (  Tree &  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
Postcondición:
Retorna "true" si el árbol es un objeto bien construido
Ver también:
Check_Ok(Tree&)

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

Definición en la línea 740 del archivo Tree_V.h.

bool operator== (  const Tree &  p,
const Tree &  q
)  [friend]
 

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

Definición en la línea 688 del archivo Tree_V.h.

bool operator!= (  const Tree &  p,
const Tree &  q
)  [friend]
 

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

Definición en la línea 689 del archivo Tree_V.h.

Documentación de los datos miembro

Tree::Node* TL::Tree::_root [private]
 

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

Definición en la línea 200 del archivo Tree_L.h.

La documentación para esta clase fué generada a partir del siguiente archivo:
Generado el Sun Feb 19 09:37:35 2006 para Uso de TL::Tree y TV::Tree: por  doxygen 1.3.9.1