Java iterators for C++:
 All Classes Namespaces Files Functions Variables Typedefs Friends Macros Pages
Tree_L.h
Go to the documentation of this file.
1 // Tree_L.h (c) 2006 adolfo@di-mare.com
2 
3 /** \file Tree_L.h
4  \brief Declaraciones y definiciones para la clase \c Tree
5 
6  \author Adolfo Di Mare <adolfo@di-mare.com>
7  \date 2006
8 
9  - Why English names??? ==> http://www.di-mare.com/adolfo/binder/c01.htm#sc04
10 */
11 
12 #ifndef Tree_L_h
13 #define Tree_L_h
14 
15 #ifndef NDEBUG // ==> Overview of File Translation ==> C++
16  #define USE_v_Alive
17  #undef USE_v_Alive
18 #endif
19 
20 #include <cassert> // para usar assert()
21 
22 /// Arboles de adolfo@di-mare.com cuyos nodos contienen un puntero izquierdo al hijo y uno derecho al hermano o padre
23 namespace TL {
24 
25 template <class E> class Tree;
26 template <class E> bool check_ok( const E & );
27 template <class E> bool check_ok( const Tree<E>& T); // declaration hacia adelante
28 
29 /// Nodos almacenados en el árbol.
30 template <class E>
31 class Tree_Node {
32 public:
33  friend class Tree<E>;
34  typedef E value_type; ///< Nombre estándar del tipo de elemento contenido
35 private:
36  Tree_Node( const value_type& d ) : m_data( d ), m_refCount(1) {} ///< Constructor de vector
37  static Tree_Node<E>* Get_New(const value_type& d);
38  unsigned Abs_n_child() const;
39 private:
40  value_type m_data; ///< Valor almacenado en el nodo
41  unsigned m_refCount; ///< Cantidad de punteros hacia mi
42  int m_n_child; ///< Soy el el hijo número <code> "(m_n_child - 1)" </code> de mi padre
43  Tree_Node<E> * m_left_child; ///< Puntero al nodo hijo más izquierdo
44  Tree_Node<E> * m_right_brother; ///< Puntero al nodo hermano o al padre
45 private:
46  #ifdef USE_v_Alive // ==> NDEBUG ==> Overview of File Translation ==> C++
47  static const unsigned N_Alive = 333; ///< Cantidad máxima posible de punteros en uso
48  static Tree_Node<E> * m_v_Alive[N_Alive]; ///< Punteros en uso
49  static unsigned m_n_Alive; ///< Cantidad de punteros en uso
50  #endif
51 }; // Tree_Node
52 
53 /** Los métodos para trabajar con árboles regresan "referencias" que son sub-árboles.
54  - Un sub-árbol es parte del árbol, por lo que al modificar los valores del
55  sub-árbol también el árbol original queda cambiado.
56  - Para evitar este tipo de modificación indirecta, es necesario trabajar
57  con una "copia profunda" del árbol orignal, la que se puede obtener con
58  \c Tree::Copy_Deep().
59  - Aún si el árbol original es eliminado, el sub-árbol continúa existiendo
60  - Debido a que los árboles y sub-árboles son referencias, en C++ es necesario mantener
61  internamente "cuentas de referencia" que impiden que métodos como \c Father() o \c Root()
62  sean métodos <code>const</code>.
63  - Muchos métodos retornan referencias \c Tree& porque es más eficiente, pues cada
64  vez que un \c Tree es copiado hay que actualizar la "cuenta de referencia" de
65  la raíz del sub-árbol.
66 */
67 template <class E>
68 class Tree {
69 public:
70  typedef E value_type; ///< Nombre estándar del tipo de elemento contenido
71 /// \name Constructores y destructor
72 //@{
73 public:
74  Tree() : m_root(0) {} ///< Constructor de vector
75  Tree(const Tree& o);
76  Tree(const value_type & d);
77  ~Tree();
78 private:
79  /// Constructor a partir de un nodo
80  Tree(Tree_Node<E>* p) : m_root(p) { if (p!=0) { p->m_refCount++; } }
81  /// Truco para usar el constructor que no verifica <code> (p != 0) </code>
82  typedef void NOT_null_pointer;
83  /// Constructor a partir de un nodo [ requiere <code> p != 0 </code> ]
84  Tree(NOT_null_pointer* p) : m_root( (Tree_Node<E>*)p) { // assert( p != 0 );
85  ((Tree_Node<E>*)p)->m_refCount++; }
86 //@}
87 
88 /// \name Operaciones básicas
89 //@{
90 public:
91  bool Empty() const { return (m_root == 0); } ///< Retorna \c "true" si el sub-árbol está vacío
92  unsigned Count() const ;
93  unsigned Count_Children() const ;
94  unsigned Size () const { return Count(); } ///< Usa \c Count() para retornar la cantidad de valores almacenados en el sub-árbol
95  friend bool check_ok<E>(const Tree<E>& T);
96  bool Ok() { return check_ok(*this); } ///< Usa \c check_ok(Tree& T) para verificar la invariante de \c Tree
97 //@}
98 
99 /// \name Operaciones de borrado
100 //@{
101 public:
102  void Erase();
103  void Erase_Son(unsigned n) { Tree_Node<E>*p; Erase_Son_Prev(n+1,p /*,p*/); }
104 private:
105  void Erase_Son_Prev(unsigned n, Tree_Node<E>*& /*, Tree_Node<E>*& */);
106 //@}
107 
108 /// \name Operaciones de copiado
109 //@{
110 public:
111  Tree& operator= (const Tree &o) { return Copy(o); } ///< Sinónimo de \c this->Copy(o)
112  Tree& Copy (const Tree &o);
113  Tree& Move (Tree &o);
114  Tree& Swap (Tree &o);
115  Tree& Copy_Deep( const Tree &o );
116  /// Usa \c Change_Root() para sustituir por "d" el valor almacenado en la raíz del árbol
117  Tree& operator=( const value_type & d) { Change_Root(d); return *this; }
118 //@}
119 
120 /// \name Métodos para cambiar los valores almacenados en el árbol
121 //@{
122 public:
123  Tree Change_Root(const value_type &d);
124  Tree Change_Child( unsigned n, const value_type &d );
127  Tree Graft( unsigned n, Tree &o );
128 //@}
129 
130 /// \name Operaciones para usar los valores almacenados
131 //@{
132 public:
133  value_type& Data () { return m_root->m_data; } ///< Valor almacenado en la raíz del sub-árbol
134  value_type& operator * () { return Data(); } ///< Valor almacenado en la raíz del sub-árbol
135  value_type* operator -> () { return &(m_root->m_data); } ///< Puntero al valor almacenado en la raíz del sub-árbol
136  const value_type& Data () const { return m_root->m_data; } ///< Valor almacenado en la raíz del sub-árbol
137  const value_type& operator * () const { return Data(); } ///< Valor almacenado en la raíz del sub-árbol
138  const value_type* operator -> () const { return &(m_root->m_data); } ///< Puntero al valor almacenado en la raíz del sub-árbol
139 //@}
140 
141 /// \name Operaciones de comparación
142 //@{
143 public:
144  template <class X> friend bool operator == (const Tree<X> &p, const Tree<X> &q); ///< ¿¿¿ (p == q) ???
145  template <class X> friend bool operator != (const Tree<X> &p, const Tree<X> &q); ///< ¿¿¿ (p != q) ???
146  bool Equals( const Tree & o ) const { return (*this)==o; } ///< ¿¿¿ (*this==o) ???
147  /// Retorna \c true si \c "o" comparte la raíz con \c "*this"
148  bool Same( const Tree & o ) const { return m_root == o.m_root; }
149 //@}
150 
151 /// \name Métodos para recorrer el árbol
152 //@{
153 public:
154  Tree Root() const { return Tree( m_root ); } ///< Raíz del sub-árbol
155  Tree Father() const ;
156  Tree Child(unsigned n) const;
157  Tree Left() const;
158  Tree Right() const;
159  Tree Leftmost() const;
160  Tree Rightmost() const;
161  Tree Sibling(int n) const;
162  Tree Left_Sibling() const;
163  Tree Right_Sibling() const;
164  Tree Previous_Sibling() const { return Left_Sibling(); } ///< Sinónimo de \c Left_Sibling()
165  Tree Prev_Sibling() const { return Left_Sibling(); } ///< Sinónimo de \c Left_Sibling()
166  Tree Next_Sibling() const { return Right_Sibling(); } ///< Sinónimo de \c Right_Sibling()
169 //@}
170 
171 /// \name Propiedades del árbol
172 //@{
173 public:
174  /// Retorna \c "n" si \c "*this" es el n-ésimo hijo de su padre, si no retorna \c 0 (cero)
175  unsigned Child_Number() const { return ( m_root==0 ? 0 : m_root->Abs_n_child() - 1); }
176  /// Retorna \c "n" si el hijo más izquierdo de \c "*this" es el n-ésimo hijo, si no retorna \c 0 (cero)
177  unsigned Leftmost_N() const { return Leftmost().Child_Number(); }
178  /// Retorna \c "n" si el hijo más derecho de \c "*this" es el n-ésimo hijo, si no retorna \c 0 (cero)
179  unsigned Rightmost_N() const { return Rightmost().Child_Number(); }
180  /// Retorna \c "true" si el árbol es una hoja
181  bool Is_Leaf() const { return (m_root != 0) && (m_root->m_left_child != 0); }
182  /// Retorna \c "true" si el árbol no tiene padre
183  bool Is_Root() const { return (m_root != 0) && (m_root->m_right_brother == 0); }
184  /// Cantidad de referencias de la raíz del árbol
185  unsigned use_count() const { return (m_root==0 ? 0 : m_root->m_refCount); }
186 //@}
187 
188 /// \name Funciones para manipular valores a bajo nivel
189 //@{
190 private:
191  /// Convierte el puntero al nodo en un referencia a \c Tree
193  { return (Tree&) *( reinterpret_cast<Tree*> (&p)); }
194 //@}
195 
196 /// \name Funciones recursivas que realizan el trabajo sobre nodos
197 //@{
198 private:
199  static void Erase0(Tree_Node<E> * p);
200  static bool Comp0(const Tree_Node<E> *p, const Tree_Node<E> *q);
201  static void Count0(const Tree_Node<E> * p, unsigned & n);
202  static Tree_Node<E>* Copy_Deep0(const Tree_Node<E> * p);
203 //@}
204 private:
205  Tree_Node<E> * m_root; ///< Un árbol "es" el puntero al nodo raíz
206 }; // Tree
207 
208 #ifdef USE_v_Alive
209  unsigned Tree::Tree_Node<E>::m_n_Alive = 0; // Hay que "repetir" estos nombres acá para que el ...
210  Tree::Tree_Node<E>* Tree::Tree_Node<E>::m_v_Alive[Tree::Tree_Node<E>::N_Alive]; // ... compilador les asigne memoria
211 #endif
212 
213 /** Crea un nuevo nodo y lo inicializa con \c "d"
214 
215  - Para mejorar la eficiencia, no incializa los punteros del nodo.
216  - Si la macro \c USE_v_Alive de compilación existe, también agrega el nuevo
217  nodo al contenedor global \c Tree::m_v_Alive[], de manera que es posible
218  saber si un puntero a un nodo está o no en uso.
219  - En realidad sobra usar este método, pero la utilidad de usarlo es
220  que es posible examinar \c Tree::m_v_Alive[] para saber si los métodos
221  de árbol están correctamente implementados.
222 */
223 template <class E>
224 inline Tree_Node<E> * Tree_Node<E>::Get_New( const E& d) {
225  Tree_Node<E>* p = new Tree_Node(d);
226  #ifdef USE_v_Alive
227  m_v_Alive[m_n_Alive] = p;
228  m_n_Alive++;
229  #endif
230  return p;
231 }
232 
233 /// Constructor de copia desde otro árbol (copia superficial).
234 /// - Como un sub-árbol en realidad es una referencia, este método
235 /// no hace la copia completa [profunda] del árbol.
236 template <class E>
237 inline Tree<E>::Tree(const Tree& o) {
238  if (o.m_root != 0) {
239  o.m_root->m_refCount++; // una referencia más porque "o" y "*this" ...
240  }
241  m_root = o.m_root; // ... ahora comparten la raíz
242 }
243 
244 /** Destructor.
245  \par Complejidad:
246  O( \c Count() )
247 
248  \see http://www.di-mare.com/adolfo/binder/c04.htm#sc04 */
249 template <class E>
251  if (m_root != 0) {
252  if (m_root->m_refCount == 1) {
253  Erase0(m_root);
254  } else {
255  m_root->m_refCount--;
256  }
257  }
258 }
259 
260 /// Constructor a partir de un valor
261 template <class E>
262 inline Tree<E>::Tree(const E & d) {
263  m_root = Tree_Node<E>::Get_New(d);
264  m_root->m_n_child = -1;
265  m_root->m_left_child = 0;
266  m_root->m_right_brother = 0;
267 }
268 
269 /** Copia superficial desde \c "o".
270  - El valor anterior de \c "*this" se pierde
271 
272  \par Complejidad:
273  O( \c Count() )
274 
275  \returns *this
276 
277  \see http://www.di-mare.com/adolfo/binder/c04.htm#sc05 */
278 template <class E>
279 Tree<E>& Tree<E>::Copy( const Tree &o ) {
280  if (m_root != o.m_root) { // evita auto-borrado
281  if (m_root != 0) {
282  if ( m_root->m_refCount == 1 ) { // como es el último...
283  Erase0(m_root); // ...lo mata
284  } else {
285  m_root->m_refCount--;
286  }
287  }
288  m_root = o.m_root; // comparte la raíz
289  if (o.m_root != 0) {
290  o.m_root->m_refCount++; // una referencia más
291  }
292  }
293  return *this;
294 }
295 
296 /** Traslada el valor de \c "o" a \c "*this".
297  - El valor anterior de \c "*this" se pierde
298  - El nuevo valor de \c "*this" es el que \c "o" tuvo
299  - \c "o" queda en el estado en que lo dejaría \c Erase()
300  - Si \c "*this" es \c "o" entonces su valor no cambia
301  - En general, después de esta operación casi
302  nunca ocurre que <code> (*this == o) </code>
303 
304  \par Complejidad:
305  O( \c Count() )
306 
307  \returns \c *this
308 
309  \see http://www.di-mare.com/adolfo/binder/c04.htm#sc07 */
310 template <class E>
312  if (m_root == o.m_root) { // evita auto-borrado
313  if (m_root != 0) {
314  if ( m_root->m_refCount == 1 ) { // como es el último...
315  Erase0(m_root); // ...lo mata
316  } else {
317  m_root->m_refCount--;
318  }
319  }
320  m_root = o.m_root; // se roba los hijos
321  o.m_root = 0; // anula al dador
322  }
323  return *this;
324 }
325 
326 /** Intercambia los valores de \c "*this" y \c "o".
327  - Debido a que algunos métodos retornan copias del valor de \c "*this" en
328  lugar de una referencia, como ocurre con \c Tree::Child(), a veces
329  \c Swap() no tiene el resultado esperado por el programador.
330  - Por ejemplo, si se invoca <code> T.Child(i). Swap( T.Child(j) ) </code>
331  el resultado no es intercambiar los hijos, sino más bien intercambiar
332  los valores de los sub-árboles temporales \c T.Child(i) y \c T.Child(j).
333  La forma correcta de intercambiar hijos es usar \c Graft().
334 
335  \par Complejidad:
336  O( \c 1 )
337 
338  \returns *this
339 
340  \see http://www.di-mare.com/adolfo/binder/c04.htm#sc08 */
341 template <class E>
342 inline Tree<E>& Tree<E>::Swap( Tree &o ) {
343  Tree_Node<E> * tmp = m_root;
344  m_root = o.m_root;
345  o.m_root = tmp;
346  return *this;
347 }
348 
349 /** Acceso al padre.
350  - Si el sub-árbol no tiene padre retorna el árbol vacío.
351 
352  \par Complejidad:
353  O( <code> Father().Count_Children() </code> ) */
354 template <class E>
356  if (m_root == 0) {
357  return Tree( );
358  }
359 
360  Tree_Node<E>* p = m_root; // soy el primer hijo de mi padre
361  while (p->m_n_child > 0) {
362  p = p->m_right_brother; // se brinca los que no tienen el puntero al padre
363  }
364  return Tree( p->m_right_brother );
365  // para la raíz siempre ocurre que [m_root->m_right_brother == 0] por lo que
366  // Tree( p->m_right_brother ) produce un árbol vacío
367 }
368 
369 /** Acceso al \c "n"-ésimo hijo.
370  - Si el sub-árbol no tiene un hijo número \c "n" retorna el sub-árbol vacío.
371 
372  \par Complejidad:
373  O( <code> Father().Count_Children() </code> ) */
374 template <class E>
375 Tree<E> Tree<E>::Child( unsigned n ) const {
376  if (m_root == 0) {
377  return Tree( );
378  }
379 
380  Tree_Node<E>* child = m_root->m_left_child; // soy el primer hijo de mi padre
381  if (child == 0) {
382  return Tree( );
383  }
384 
385  n++; // lo incrementa para evitar incrementar "m_n_child" para cada hijo de "m_root"
386 
387  for (;;) {
388  if (child->m_n_child <= 0) { // es el último hijo
389  if ( unsigned(- child->m_n_child) == n ) {
390  return Tree( (NOT_null_pointer*) child );
391  } else {
392  return Tree( );
393  }
394  } else { // assert( child->m_n_child > 0 );
395  if ( static_cast<unsigned>(child->m_n_child) == n ) {
396  return Tree( (NOT_null_pointer*) child );
397  } else if ( unsigned(child->m_n_child) < n) {
398  child = child->m_right_brother;
399  } else { // assert( unsigned(child->m_n_child) > n );
400  return Tree( );
401  }
402  }
403  }
404 }
405 
406 /** \typedef Tree::NOT_null_pointer
407  \brief Truco para evitar comparar con \c 0 ( \c nil )
408  al usar \c Tree::Tree_Node<E>* para construir \c Tree().
409 
410  Al implementar cada uno de los métodos de \c Tree con frecuencia ocurre
411  que es posible saber que el sub-árbol retornado no está vacío. En estos casos, conviene
412  usar un contructor que no verifique si la raíz del árbol es nula.
413 
414  Esta clase se usa como una marca para que se ejecute el contructor
415  <code> Tree::Tree(NOT_null_pointer* p) </code>
416  que no verifica la nulidad de \c "m_root"; esta es una micro-eficiencia, pero aquí sirve
417  para mostrar un truco que es muy usado en C++ para aumentar la eficiencia de los
418  programas, pues le permite al programado usar la sobrecarga de operadores para evitar
419  repetir verificaciones innecesarias.
420 
421  \see http://www.di-mare.com/adolfo/binder/c01.htm#k1-micro-eficiencia
422 */
423 
424 /** Sub-árbol izquierdo [en un árbol binario].
425  - Sinónimo de \c Child(0).
426  \par Complejidad:
427  O( \c 1 ) */
428 template <class E>
429 inline Tree<E> Tree<E>::Left() const {
430  if (m_root == 0) {
431  return Tree( );
432  } else if ( -1 ==m_root->m_left_child->m_n_child ||
433  1 ==m_root->m_left_child->m_n_child ) {
434  return Tree( (NOT_null_pointer*) m_root->m_left_child );
435  }
436  return Tree( );
437 }
438 
439 /** Sub-árbol derecho [en un árbol binario].
440  - Sinónimo de \c Child(1).
441 
442  \par Complejidad:
443  O( \c 1 ) */
444 template <class E>
446  if (m_root == 0) {
447  return Tree( );
448  } else if ( 0 == m_root->m_left_child ) { // no hay hijos
449  return Tree( );
450  } else if ( -1 ==m_root->m_left_child->m_n_child ) {
451  return Tree( ); // sólo está el hijo izquierdo
452  } else if ( 1 ==m_root->m_left_child->m_n_child ) {
453  if ( -2 == m_root->m_left_child->m_right_brother->m_n_child ||
454  2 == m_root->m_left_child->m_right_brother->m_n_child ) {
455  return Tree( (NOT_null_pointer*) m_root->m_left_child->m_right_brother );
456  }
457  } else if ( 2 == m_root->m_left_child->m_n_child || -2 == m_root->m_left_child->m_n_child ) {
458  return Tree( (NOT_null_pointer*) m_root->m_left_child );
459  }
460  return Tree( ); // uso 1-2 en lugar de 0-1 porque "m_n_child" contiene "uno más"
461 }
462 
463 /** Obtiene el hermano no vacío anterior, que está hacia la izquierda.
464  - Si no existe un hermano no vacío hacia la izquierda, retorna un sub-árbol vacío.
465  - Si <code>n == Child_Number()</code> no necesariamente ocurrirá que
466  <code> (n-1)== Left_Sibling().Child_Number()</code>
467  pues los anteriores hijos de \c Father() pueden ser sub-árboles vacíos, como ocurre si
468  un árbol binario tiene hijo derecho pero no tiene hijo izquierdo.
469  - Este método usualmente se usa junto con \c Rightmost()
470 
471  \par Complejidad:
472  O( <code> Father().Count_Children() </code> ) */
473 template <class E>
475  if (m_root == 0) {
476  return Tree( );
477  }
478 
479  unsigned n_child = m_root->Abs_n_child()-1; // assert( n_child >= 0 );
480  if ( n_child <= 0 ) { // no puede haber un hijo anterior...
481  return Tree( ); // huye porque no existen hijos antes del primero
482  }
483  #ifdef ESTO_SOBRA_en_Left_Sibling
484  if (m_root->m_right_brother == 0) { // sólo la raíz tiene en blanco "m_right_brother"
485  return Tree( ); // la raíz no tiene hermanos
486  }
487  // Para el nodo raíz de un árbol [T] el campo [T.m_root->m_right_brother == 0] es nulo
488  // - Afortunadamente, como [T.m_root->m_n_child == -1], el if(){} anterior retorna
489  // el sub-árbol vacío para el nodo raíz del árbol [T].
490  #endif
491 
492  Tree_Node<E>* brother = m_root; // camina sobre los hermanos hasta llegar al padre
493  while (brother->m_n_child > 0) {
494  brother = brother->m_right_brother; // se brinca los que no tienen el puntero al padre
495  }
496  Tree_Node<E>* father = brother->m_right_brother;
497  // assert( ! Father().Empty() && Father().Same( Tree( brother ) ) );
498 
499  brother = father->m_left_child; // hijo más izquierdo de Father()
500  if ( m_root == brother ) {
501  return Tree( ); // ya "m_root" era el hijo más izquierdo
502  }
503  while ( m_root != brother->m_right_brother ) {
504  brother = brother->m_right_brother;
505  }
506  // assert( m_root == brother->m_right_brother );
507  return Tree( brother );
508 }
509 
510 /** Obtiene el hermano no vacío siguiente, que está hacia la derecha.
511  - Si no existe un hermano hacia la derecha, retorna un sub-árbol vacío.
512  - Si <code>n == Child_Number()</code> no necesariamente ocurrirá que
513  <code>(n+1) == Right_Sibling().Child_Number()</code>
514  pues los siguientes hijos de \c Father() pueden ser sub-árboles vacíos, como ocurre si
515  un árbol binario tiene hijo izquierdo pero no tiene hijo derecho.
516  - Este método usualmente se usa junto con \c Leftmost()
517 
518  \par Complejidad:
519  O( \c 1 ) */
520 template <class E>
522  if (m_root == 0) {
523  return Tree( );
524  } if (m_root->m_n_child < 0) { // es el último hijo
525  return Tree( ); // ==> ya no hay dónde más buscar
526  } else {
527  return Tree( m_root->m_right_brother );
528  // sólo la raíz tiene "m_right_brother" en blanco (puntero nulo);
529  // en ese caso se retorna el árbol vacío.
530  }
531 }
532 
533 /** Obtiene el hermano que está inmediatamente hacia la izquierda.
534  - Este método es equivalente a invocar \c Sibling( -1 )
535  - Si no existe un hermano hacia la derecha, retorna un sub-árbol vacío.
536 
537  \par Complejidad:
538  O( <code> Father().Count_Children() </code> ) */
539 template <class E>
541  return Sibling( -1 );
542 }
543 
544 /** Obtiene el hermano que está inmediatamente hacia la derecha.
545  - Este método es equivalente a invocar \c Sibling( +1 )
546  - Si no existe ese hermano hacia la derecha, retorna un sub-árbol vacío.
547 
548  \par Complejidad:
549  O( \c 1 ) */
550 template <class E>
552 // return Sibling( +1 );
553  if (m_root == 0) {
554  return Tree( );
555  }
556  if (m_root->m_n_child <= 0) { // es el último hijo
557  return Tree( ); // ya no hay hermanos a la derecha
558  }
559  // assert( m_root->m_right_brother != 0 ); // pues "(m_root->m_n_child > 0)"
560  Tree_Node<E>* brother = m_root->m_right_brother;
561  // assert( brother->Abs_n_child() > 0 ); // pues "brother" está "a la derecha" de "m_root"
562  int n_brother = brother->Abs_n_child() - 1;
563  if ( m_root->m_n_child == n_brother ) {
564  return Tree( (NOT_null_pointer*) brother );
565  } else {
566  return Tree( );
567  }
568 #if 0
569  if (brother->m_n_child > 0) {
570  if ( m_root->m_n_child + 1 == brother->m_n_child ) {
571  return Tree( (NOT_null_pointer*) brother );
572  } else {
573  return Tree( );
574  }
575  } else {
576  if ( m_root->m_n_child + 1 == - brother->m_n_child ) {
577  return Tree( (NOT_null_pointer*) brother );
578  } else {
579  return Tree( );
580  }
581  }
582 #endif
583 }
584 
585 /** Retorna el valor absoluto del campo \c "m_n_child".
586  - Hay que tomar en cuenta que que \c m_n_child está incrementado en \c +int(1)
587  porque la marca de "puntero al padre" es un valor negativo, y como hay un hijo número cero
588  \c int(0), no sería posible marcar como "puntero al padre" a ese nodo
589  - Esta rutina también existe para documentar el truco del "puntero al padre", pues más directo
590  habría sido usar la función \c abs() definida en <code> \#include <cstdlib> </code>
591  - En otras palabras, parte de la invariante de un nodo siempre será que
592  <code> (m_n_child != 0) </code> porque siempre <code> int(0) == int(-0) </code> */
593 template <class E>
594 inline unsigned Tree_Node<E>::Abs_n_child() const {
595  return ( m_n_child >= 0 ? unsigned(m_n_child) : unsigned( - m_n_child ) );
596 }
597 
598 /** \c "n"-ésimo hermano a partir de \c "*this".
599  - El hermano puede ser vacío aunque haya otros hermanos que no son vacíos.
600  - Se "corre" hacia el n-ésimo hermano \c "n" "posiciones".
601  - El hermano se determina contando sub-árboles hacia la derecha o izquierda de acuerdo
602  al signo de \c "n":
603  - Si \c n=0, regresa \c "*this".
604  - Si \c n>0, regresa el hermano número \c "+n" contando hacia la derecha de \c "*this".
605  - Si \c n<0, regresa el hermano número \c "-n" contando hacia la izquierda de \c "*this".
606  - Si no existe un hermano número \c "n" retorna un sub-árbol vacío.
607  - El árbol \c "T" tiene 3 hijos no vacíos \c "B", \c "C" y \c "E" y tiene 4 sub-árboles:
608  - <code> C.Sibling( +0 ) == C</code>
609  - <code> B.Sibling( +1 ) == C</code>
610  - <code> E.Sibling( -2 ) == C</code>
611  - <code> E.Sibling( -1 ) --> Vacío</code>
612  - <code> A.Sibling( +1 ) --> Vacío </code>
613  - <code> B.Sibling( -1 ) --> Vacío </code>
614  - <code> E.Sibling( +1 ) --> Vacío </code>
615  \code
616  A <-- T
617  /|\
618  / / \ \ [] --> es representa un sub-árbol vacío
619  B C [] E
620  \endcode
621 
622  \par Complejidad:
623  O( <code> Father().Count_Children() </code> ) */
624 template <class E>
625 Tree<E> Tree<E>::Sibling( int n ) const {
626  if (m_root == 0) {
627  return Tree( );
628  } else if ( m_root->m_right_brother == 0 ) {
629  return Tree( );
630  } else if ( n==0 ) {
631  return Tree( (NOT_null_pointer*) m_root );
632  }
633 
634  Tree_Node<E>* brother; // desde dónde comenzar a buscar en la lista de hermanos
635  unsigned n_target; // número de hijo que hay que encontrar: "(m_n_child + n)"
636 
637  // averigua "n_target" (hay que manejar el "+1" del "puntero al padre")
638  if ( n < 0 ) { // a la izquierda ==> busque al padre para comenzar en m_left_child
639  unsigned n_child = m_root->Abs_n_child()-1; // assert( n_child >= 0 );
640  unsigned abs_n = unsigned(-n); // assert( abs_n > 0 );
641  if ( n_child < abs_n ) { // no se puede hacer la resta porque da un número de hijo negativo
642  return Tree( ); // se sale pues no existen hijos antes del hijo más izquierdo
643  } else {
644  n_target = n_child - abs_n; // como el hermano está hacia la izquierda...
645  // return Father().Child( n_target ); // ...hay que buscarlo desde el padre
646  brother = m_root;
647  while (brother->m_n_child > 0) { // se brinca los que no tienen el puntero al padre
648  brother = brother->m_right_brother;
649  }
650  brother = brother->m_right_brother->m_left_child; // buscará desde el primer nodo
651  }
652  } else { // assert( n > 0 ); // a la derecha ==> busque desde aquí en adelante
653  brother = m_root;
654  n_target = unsigned(n) + m_root->Abs_n_child()-1; // assert( (n > 0) && (n_target > m_n_child) );
655  }
656 
657  // hay que manejar el "+1" del "puntero al padre" en "n_target"
658  ++n_target; // para no tener que restarle int(1) a "child->m_n_child"
659 
660  // avance hacia la derecha en busca del hermano "n_target"
661  // assert( brother != 0 );
662  for (;;) {
663  if (brother->m_n_child < 0) { // es el último hijo
664  if ( unsigned(- brother->m_n_child) == n_target ) {
665  return Tree( (NOT_null_pointer*) brother );
666  } else {
667  return Tree( ); // esa era el último ==> ya no hay dónde más buscar
668  }
669  } else {
670  unsigned n_child = brother->m_n_child;
671  if (n_child == n_target) { // lo encontró
672  return Tree( (NOT_null_pointer*) brother );
673  } else if (n_child < n_target) { // siga buscando...
674  brother = brother->m_right_brother;
675  } else { // if (n_child > n_target) // ya se lo brincó; no está
676  return Tree( );
677  }
678  }
679  }
680 }
681 
682 /** Obtiene el hijo más izquierdo del árbol.
683  - Este método usualmente se usa junto con \c Right_Sibling()
684 
685  \par Complejidad:
686  O( \c 1 )
687 
688  \remark Esta es una forma de procesar los hijos no vacíos de un sub-árbol de izquierda a derecha:
689 
690  \code
691  Tree<E> Child = T.Leftmost();
692  while ( ! Child.Empty() ) {
693  Process( Child );
694  Child = Child.Right_Sibling();
695  }
696  \endcode */
697 template <class E>
698 inline Tree<E> Tree<E>::Leftmost() const {
699  if (m_root == 0) {
700  return Tree( );
701  }
702  return Tree( m_root->m_left_child ); // puede ser el puntero nulo
703 }
704 
705 /** Obtiene el hijo más derecho del árbol.
706  - Este método usualmente se usa junto con \c Left_Sibling()
707 
708  \par Complejidad:
709  O( <code> Count_Children() </code> )
710 
711  \remark Esta es una forma de procesar los hijos no vacíos de un sub-árbol de derecha a izquierda:
712 
713  \code
714  Tree<E> Child = T.Rightmost();
715  while ( ! Child.Empty() ) {
716  Process( Child );
717  Child = Child.Left_Sibling();
718  }
719  \endcode */
720 template <class E>
722  if (m_root == 0) {
723  return Tree( );
724  }
725  Tree_Node<E>* child = m_root->m_left_child; // soy el primer hijo de mi padre
726  if (child == 0) {
727  return Tree( );
728  }
729 
730  while (child->m_n_child > 0) { // todavía no se ha llegado al último hijo
731  child = child->m_right_brother;
732  }
733  return Tree( (NOT_null_pointer*) child );
734 }
735 
736 /** Implementación recursiva para \c Count().
737  - Incrementa \c "n" en el número de hijos que tiene el sub-árbol cuya raíz es \c "p"
738  - Cambia el valor de \c "n"
739  - No cuenta el nodo raíz \c "p"
740  - Esta función complementa a \c Count()
741 
742  \pre p != 0 */
743 template <class E>
744 void Tree<E>::Count0(const Tree_Node<E> * p, unsigned & n) {
745  Tree_Node<E>* child = p->m_left_child; // soy el primer hijo de mi padre
746  if (child == 0) {
747  return;
748  }
749 
750  for (;;) {
751  ++n; // cuenta a este hijo
752  Count0( child, n );
753  if (child->m_n_child > 0) { // todavía no se ha llegado al último hijo
754  child = child->m_right_brother;
755  } else {
756  break;
757  }
758  }
759 }
760 
761 /** Retorna la cantidad de valores almacenados en el sub-árbol.
762  - Calcula el número de sub-árboles no vacíos del árbol
763 
764  \par Complejidad:
765  O( \c Count() ) ==> tiempo <br>
766  O( \c Height() ) ==> espacio
767 
768  \see http://www.di-mare.com/adolfo/binder/c05.htm#sc03 */
769 template <class E>
770 unsigned Tree<E>::Count() const {
771  if (m_root == 0) {
772  return 0;
773  } else {
774  unsigned n = 1; // comienza contando en uno...
775  Count0(m_root, n); // ... porque Count0() no cuenta la raíz
776  return n;
777  }
778 }
779 
780 /** Retorna la cantidad de hijos del árbol.
781  \par Complejidad:
782  O( \c Count_Children() ) */
783 template <class E>
784 unsigned Tree<E>::Count_Children() const {
785  if (m_root == 0) {
786  return 0;
787  }
788  Tree_Node<E>* child = m_root->m_left_child;
789  if ( 0 == child ) { // no hay hijos
790  return 0;
791  }
792  unsigned tot = 0;
793  for (;;) {
794  ++tot; // cuenta a este hijo
795  if (child->m_n_child > 0) { // todavía no se ha llegado al último hijo
796  child = child->m_right_brother;
797  } else {
798  break;
799  }
800  }
801  return tot;
802 }
803 template <class E>
804 inline bool operator == (const Tree<E> &p, const Tree<E> &q) { return Tree<E>::Comp0(p.m_root, q.m_root); }
805 template <class E>
806 inline bool operator != (const Tree<E> &p, const Tree<E> &q) { return !(p == q); }
807 
808 /// Compara recursivamente los árboles cuyos nodo raíz son \c "*p" y \c "*q".
809 /// - Implementación recursiva para <code> operator==(Tree, Tree) </code>.
810 template <class E>
811 bool Tree<E>::Comp0(const Tree_Node<E> *p, const Tree_Node<E> *q) {
812  if (p == q) {
813  return true;
814  }
815  if ( (p==0) || (q==0)) { // son diferentes...
816  return false; // ...pues sólo 1 está vácio
817  }
818  if ( p->m_n_child != q->m_n_child ) {
819  return false; // números de hijo diferentes
820  }
821  if ( ! (p->m_data == q->m_data) ) {
822  return false; // valor diferente en la raíz
823  }
824 
825  // A comparar a todos los hijos
826  p = p->m_left_child;
827  q = q->m_left_child;
828  for (;;) {
829  if (p == q) { // como se terminaron juntos...
830  return true; // ...son iguales
831  }
832  if ( (p==0) || (q==0) ) { // son diferentes...
833  return false; // ...pues sólo 1 está vácio
834  }
835  if ( p->m_n_child != q->m_n_child ) {
836  return false; // números de hijo diferentes
837  }
838  if (! Comp0(p, q) ) {
839  return false; // recorrido recursivo
840  }
841  if ( p->m_n_child < 0 ) { // assert( q->m_n_child < 0 );
842  return true; // ya no hay más hermanos
843  }
844  p = p->m_right_brother;
845  q = q->m_right_brother;
846  }
847 }
848 
849 /** Verifica que se cumpla la invariante de la clase, o sea, que el objeto esté bien construido.
850  - La razón por la que esta función no es un método es continuar la costumbre de muchos
851  programadores quienes no definen la invariante para sus clases, pues en muchos
852  casos sobra hacerlo.
853  - No invoca \c check_ok( value_type& ) para cada valor almacenado, aunque si el árbol
854  cumple con su invariante necesariamentes es porque también sus elementos almacenados
855  están bien construidos.
856  - Esta función en general es difícil de implementar, y en algunos casos es imposible
857  pues, cuando el objeto no está bien construido, puede ocurrir que la función no
858  retorne (como ocurriria si un nodo interno del árbol apunta de vuelta a la raíz, lo
859  que se resulta en un círculo).
860  - En general, la implementáción de esta función no es completa pues hay casos en que
861  es imposible verificar la invariante de una clase.
862 
863  \par Complejidad:
864  O( \c Count() ) ==> tiempo <br>
865  O( \c Height() ) ==> espacio
866 
867  \post Retorna \c "true" si el árbol es un objeto bien construido
868  \see \c check_ok(Tree&)
869 
870  \see http://www.di-mare.com/adolfo/binder/c04.htm#sc11 */
871 template <class E>
872 bool check_ok(const Tree<E>& T) {
873 
874  if ( T.Empty() ) {
875  return true;
876  }
877 
878  #ifdef NO_Implementado_para_evitar_forzar_que_el_valor_almacenado_tenga_su_metodo_OK
879  if (! check_ok( T.Data() ) ) { // si el valor almacenado no esta bien...
880  return false; //... tampoco lo está el árbol
881  }
882  /* Usar la función check_ok(Tree::value_type en lugar del método
883  Tree::value_type::Ok() evitar forzar a que los programadores clientes
884  que usen árboles estén obligados a implementar el método
885  Tree::value_type::Ok(), que se encarga de verificar la invariante del valor
886  almacenado en le árbol.
887  - Lindo: if (! check_ok( T.Data() ) ) //.... la función check_ok() es opcional
888  - ¡FEO!: if (! T.Data().Ok() ) //... pues obliga a que exista el método value_type::Ok()
889  */
890  #endif
891 
892  unsigned N = T.Rightmost().Child_Number();
893  for (unsigned i = 0; i < N; ++i) {
894  if ( T.Child(i).Empty() ) { // este hijo no existe
895  // continue; // con el siguiente
896  }
897  else if ( T.Child(i).Father() != T.Root() ) { // ==> ! T.Father.Empty()
898  return false; // parece que este hijo no es mi hijo...
899  }
900  else if ( i != T.Child(i).Child_Number() ) {
901  return false; // no estoy registrado como el i-ésimo hijo de mi padre
902  }
903  else if ( T.Child(i).Father().Child( i ) != T.Child( i ) ) {
904  return false; // no estoy registrado como el i-ésimo hijo de mi padre
905  }
906  else if ( ! check_ok( T.Child(i) ) ) {
907  return false; // hijo roto...
908  }
909  }
910  return true;
911 
912  // Las siguientes relaciones lógicas se cumplen
913  // [ ! T.Empty() ] ==> [ T.Root()!= Tree() ]
914  // [ T.Child(i).Father() == T.Root()] ==> [ ! T.Father.Empty() ]
915 
916  /* Si este método retorna es porque el árbol está bien construido. Sin embargo,
917  una invocación a check_ok() con un árbol mal construido posiblemente nunca retorne.
918  */
919 }
920 
921 
922 /// Sustituye por \c "d" el valor almacenado en la raíz del árbol.
923 /// - Si el árbol está vacío, le agrega el nodo raíz.
924 /// \returns \c *this
925 template <class E>
927  if (m_root == 0) { // como el árbol está vacío hay que agregarle la raíz
928  m_root = Tree_Node<E>::Get_New(d); // crea el nodo raíz
929  m_root->m_left_child = 0;
930  m_root->m_right_brother = 0;
931  m_root->m_n_child = -1;
932  } else { // como no hay más referencias....
933  m_root->m_data = d; // ... cambia el valor directamente
934  }
935  return *this;
936 }
937 
938 /** Sustituye por \c "d" el valor almacenado en el hijo número \c "n" del árbol.
939  - Si no existe el hijo número \c "n", lo agrega como una hoja con valor \c "d"
940  - Si ya existe el hijo número \c "n", le sustituye su valor por \c "d"
941 
942  \pre <code> !Empty() && (0 <= n) && (n < \e infinito) </code>
943 
944  \par Complejidad:
945  O( \c Count_Children() )
946 
947  \returns <code> Child(n) </code> */
948 template <class E>
949 Tree<E> Tree<E>::Change_Child(unsigned n, const value_type &d) {
950  if (m_root == 0) { // ignora árboles vacíos
951  return Tree( );
952  }
953 
954  n++; // evita incrementar "m_n_child" en cada iteración
955 
956  if (m_root->m_left_child == 0) { // Hay que agregar un sub-árbol nuevo
958  p->m_n_child = -int(n);
959  p->m_right_brother = m_root;
960  m_root->m_left_child = p;
961  p->m_left_child = 0;
962  return Tree ( (NOT_null_pointer*) m_root->m_left_child );
963  }
964 
965  // assert( m_root->m_left_child != 0 );
966  Tree_Node<E>* brother = m_root->m_left_child;
967  unsigned n_brother = brother->Abs_n_child();
968 
969  if ( n < n_brother ) { // Hay que crear Child(n) y ponerlo de primero
971  p->m_n_child = +int(n);
972  p->m_right_brother = brother;
973  m_root->m_left_child = p;
974  p->m_left_child = 0;
975  return Tree ( (NOT_null_pointer*) p );
976  } else if ( n == n_brother ) {
977  brother->m_data = d; // le cae encima al valor anterior
978  return Tree ( (NOT_null_pointer*) brother );
979  }
980 
981  // Child(n) no es el primer hijo de "m_root"
982  // assert( m_root->m_left_child != Child(n).m_root );
983 
984  // assert( n_brother < n); // se corre hacia la derecha para encontrar "Child(n)"
985 
986  Tree_Node<E>* prev = brother;
987  for (;;) {
988  if ( brother->m_n_child < 0 ) {
989  if ( int(n) == - brother->m_n_child ) {
990  brother->m_data = d; // le cae encima al valor anterior
991  return Tree ( (NOT_null_pointer*) brother );
992  } else if (int(n) < - brother->m_n_child ) {
993  Tree_Node<E>* p = Tree_Node<E>::Get_New(d); // ... [d] ==> [brother] ==> end
994  p->m_n_child = int(n);
995  p->m_right_brother = brother;
996  prev->m_right_brother = p;
997  p->m_left_child = 0;
998  return Tree ( (NOT_null_pointer*) p );
999  } else {
1000  Tree_Node<E>* p = Tree_Node<E>::Get_New(d); // ... [brother] ==> [d] ==> end
1001  p->m_n_child = - int(n);
1002  p->m_right_brother = brother->m_right_brother;
1003  brother->m_n_child = - brother->m_n_child; // ahora el último es [d]
1004  brother->m_right_brother = p;
1005  p->m_left_child = 0;
1006  return Tree ( (NOT_null_pointer*) p );
1007  }
1008  } else { // assert( brother->m_n_child > 0 );
1009  if ( int(n) == brother->m_n_child ) {
1010  brother->m_data = d; // le cae encima al valor anterior
1011  return Tree ( (NOT_null_pointer*) brother );
1012  } else if ( brother->m_n_child < int(n) ) {
1013  prev = brother;
1014  brother = brother->m_right_brother;
1015  } else { // como se acaba de pasar ==> hay que agregarlo después de "prev"
1017  p->m_n_child = int(n); // como "brother" no es el último, tampoco lo será "p"
1018  p->m_right_brother = brother;
1019  prev->m_right_brother = p;
1020  p->m_left_child = 0;
1021  return Tree ( (NOT_null_pointer*) p );
1022  }
1023  }
1024  }
1025 }
1026 
1027 /** Sustituye por \c "d" el valor almacenado en el hermano inmediatamente anterior del sub-árbol.
1028  - Si <code> n == Child_Number() </code> cambia el valor
1029  del hijo número \c "n-1" de \c Father()
1030  - Si no existe el hijo número \c "n-1" de \c Father() lo agrega como
1031  una hoja con valor \c "d"
1032  - Si ya existe ese hijo número \c "n-1", le sustituye su valor por \c "d"
1033  - Retorna un árbol vacío si no es posible que exista el hijo número \c "n-1" de \c Father()
1034 
1035  \pre <code> !Empty() && (1 <= Child_Number()) </code>
1036 
1037  \par Complejidad:
1038  O( <code> Father().Count_Children() </code> )
1039 
1040  \returns El hermano izquierdo, <code> Sibling(-1) </code> */
1041 template <class E>
1043  unsigned n = Child_Number();
1044  if (n > 0 ) {
1045  return Father().Change_Child( n-1, d );
1046  } else {
1047  return Tree( );
1048  }
1049 }
1050 
1051 /** Sustituye por \c "d" el valor almacenado en el hermano inmediatamente posterior del sub-árbol.
1052  - Si <code> n == Child_Number() </code> cambia el valor
1053  del hijo número \c "n+1" de \c Father()
1054  - Si no existe el hijo número \c "n+1" de \c Father() lo agrega como
1055  una hoja con valor \c "d"
1056  - Si ya existe ese hijo número \c "n+1", le sustituye su valor por \c "d"
1057  - Retorna un árbol vacío si no es posible que exista el hijo número \c "n+1" de \c Father()
1058 
1059  \pre <code> !Empty() && ( Child_Number() < \e infinito ) </code>
1060 
1061  \par Complejidad:
1062  O( \c 1 )
1063 
1064  \returns El hermano derecho, <code> Sibling(+1) </code> */
1065 template <class E>
1067  if (m_root == 0) {
1068  return Tree( );
1069  }
1070  if ( m_root->m_right_brother == 0 ) { // es la raíz del árbol y por eso no tiene hermanos
1071  return Tree( );
1072  }
1073 
1074  Tree_Node<E> * brother;
1075  if ( m_root->m_n_child < 0 ) { // "*this" es el último hijo
1076  m_root->m_n_child = - m_root->m_n_child; // ya "m_root" no es el último hijo
1077 
1078  brother = Tree_Node<E>::Get_New( d );
1079  brother->m_n_child = - ( m_root->m_n_child + 1 ); // "brother" es el último hijo
1080 
1081  brother->m_left_child = 0;
1082  brother->m_right_brother = m_root->m_right_brother;
1083  m_root->m_right_brother = brother;
1084 
1085  return Tree( (NOT_null_pointer*) brother );
1086  }
1087 
1088  // assert( m_root->m_n_child > 0 );
1089  int n_brother = m_root->m_right_brother->Abs_n_child();
1090  if ( m_root->m_n_child + 1 == n_brother ) {
1091  m_root->m_right_brother->m_data = d;
1092  return Tree( (NOT_null_pointer*) m_root->m_right_brother );
1093  } else {
1094  brother = Tree_Node<E>::Get_New( d );
1095  brother->m_n_child = m_root->m_n_child + 1; // "brother" no puede ser el último hijo
1096 
1097  brother->m_left_child = 0;
1098  brother->m_right_brother = m_root->m_right_brother;
1099  m_root->m_right_brother = brother;
1100 
1101  return Tree( (NOT_null_pointer*) brother );
1102  }
1103 }
1104 
1105 /** Elimina recursivamente a \c "*p" y a todos sus descendientes.
1106  - Implementación recursiva para \c Erase()
1107  - Borra el nodo sólo después de que constata que ya no hay punteros que le apunten
1108  - No saca a \c "*p" de la lista de hijos del padre ==> ese es el trabajo
1109  de \c Graft() o \c Erase()
1110  - La rutina llamadora invoca \c Erase0() porque sabe que al decrementar
1111  \c "p->m_refCount" queda en cero
1112  - No decrementa \c "p->m_refCount" porque ya el invocador sabe que hay que destruir \c "*p"
1113  - Recursivamente, borra a los descendientes de \c "*p"
1114 
1115  \code
1116  // Forma usual de invocación
1117  if ( child->m_refCount <= 1 ) { // Ya no hay más referencias a "child"
1118  Erase0( child ); // lo elimina
1119  } else {
1120  child->m_refCount--; // uno menos le apunta
1121  child->m_n_child = -1;
1122  child->m_right_brother = 0; // ya no es hijo de nadie
1123  }
1124  \endcode
1125 
1126  \pre <code> (p != 0) && (p->m_refCount == 1) </code>
1127  \post No cambia \c "p" porque trabaja con una copia de su valor */
1128 template <class E>
1130  // assert( p != 0 );
1131  // assert( p->m_refCount == 1 );
1132 
1133  // Primero hay que matar hijos...
1134  if ( p->m_left_child != 0 ) {
1135  Tree_Node<E> *next, *child = p->m_left_child;
1136  while ( child != 0 ) { // como hay hijos, decide a a cuáles matar
1137  if ( child->m_n_child < 0 ) {
1138  next = 0; // lo obliga a salir porque "child" es el último
1139  } else {
1140  next = child->m_right_brother; // recuerda quién es el siguiente
1141  }
1142  if ( child->m_refCount == 1 ) {
1143  Erase0( child ); // lo mata porque ésta es la última referencia
1144  // OJO: "child" está destruido ==> "child->m_right_brother" es un error
1145  } else {
1146  child->m_refCount--; // ya "*p" no le apunta
1147  child->m_n_child = -1; // ya no tiene padre porque "*p" va a morir
1148  child->m_right_brother = 0; // ni tampoco tiene hermanos
1149  }
1150  child = next; // hay que evitar usar "child->m_right_brother" si "child" ya está destruido
1151  }
1152  }
1153  #ifdef USE_v_Alive
1154  // Elimina a "p" de m_v_Alive[]
1155  for (unsigned j = 0; j < Tree_Node<E>::N_Alive; ++j) {
1156  if (p == Tree_Node<E>::m_v_Alive[j]) { // busca hasta que encuentra al puntero
1157  break;
1158  }
1159  }
1160  if (j < Tree_Node<E>::N_Alive) { // sí lo encontró
1161  for (unsigned k = j; k < Tree_Node<E>::N_Alive-1; ++k) { // corre a los demás para atrás
1163  }
1164  Tree_Node<E>::m_n_Alive--; // ahora hay uno menos
1166  } else {
1167  for (unsigned k = 0; k<3; ++j) { // marca "feos" los del final
1168  Tree_Node<E>::m_v_Alive[Tree_Node<E>::N_Alive-1-k] = (Tree::Tree_Node<E> *)(-1);
1169  }
1170  }
1171  #endif
1172  // Después de matar a los hijos, mata al nodo...
1173  delete p; // ... porque esta es la última referencia
1174 }
1175 
1176 /** Elimina el árbol y sus descendientes.
1177  \par Complejidad:
1178  O( \c Count() ) + O( <code> Father().Count() </code> ) ==> tiempo <br>
1179  O( \c Height() ) ==> espacio
1180 
1181  \see http://www.di-mare.com/adolfo/binder/c04.htm#sc03 */
1182 template <class E>
1184  if (m_root == 0) {
1185  return;
1186  }
1187 
1188  // Encuentra el padre de "m_root"
1189  Tree_Node<E>* brother = m_root; // camina sobre los hermanos hasta llegar al padre
1190  while (brother->m_n_child > 0) {
1191  brother = brother->m_right_brother; // se brinca los que no tienen el puntero al padre
1192  }
1193  Tree_Node<E>* father = brother->m_right_brother;
1194  // assert( Father().Same( Tree( brother ) ) );
1195 
1196  // Desconecta a "m_root" de la lista de hijos del padre
1197  if (father == 0) { // sólo la raíz tiene en blanco el puntero "m_right_brother"
1198  // no hay que desenlazar a la raíz porque nunca está en una lista de hermanos
1199  } else {
1200  // busca al "nodo anterior" para sacar a "m_root" de la lista de sus hermanos
1201  if ( m_root == father->m_left_child ) { // "m_root" es el hijo más izquierdo
1202  if ( m_root->m_n_child < 0 ) {
1203  father->m_left_child = 0; // elimina la lista de hijos porque "m_root" no tiene hermanos
1204  } else {
1205  father->m_left_child = m_root->m_right_brother; // desenlaza al primer hijo
1206  }
1207  } else {
1208  brother = father->m_left_child; // hijo más izquierdo de Father()
1209  while ( m_root != brother->m_right_brother ) {
1210  brother = brother->m_right_brother;
1211  }
1212  brother->m_right_brother = m_root->m_right_brother; // saca a "m_root" de la lista de hermanos
1213  }
1214  }
1215 
1216  // ahora ya puede detruir al nodo
1217  if ( m_root->m_refCount == 1 ) {
1218  Erase0(m_root); // mata al nodo porque ésta es la última referencia
1219  } else {
1220  m_root->m_refCount--; // lo va a desconectar de "m_root"
1221  m_root->m_n_child = -1; // ya no tiene padre
1222  m_root->m_right_brother = 0; // ni tampoco tiene hermanos
1223  }
1224  m_root = 0;
1225 }
1226 
1227 // Esta documentación para Tree::Erase_Son() aparece acá porque Doxygen no permite
1228 // incluir un párrafo aparte "\par" en la documentación de 1 sólo renglón.
1229 
1230 /** \fn void Tree::Erase_Son(unsigned n)
1231 
1232  \brief Elimina el sub-árbol número \c "n"
1233 
1234  \par Complejidad:
1235  O( <code> Child(n).Count() </code> ) ==> tiempo <br>
1236  O( <code> Height( Child(n) ) </code> ) ==> espacio
1237 */
1238 
1239 /** Elimina el sub-árbol número \c "n-1" y retorna un puntero al nodo anterior al borrado.
1240  - Esta es la rutina que en realidad hace el trabajo de \c Erase_Son().
1241  - Elimina el sub-árbol número \c "n-1", como también lo hace \c Erase_Son().
1242  - La única diferencia con \c Erase_Son() es que este método retorna un puntero
1243  al nodo anterior al nodo eliminado.
1244  - "prev" apunta al nodo que está antes de "prev" en el árbol.
1245  - Trabaja con \c "n-1" porque no incrementa el valor de \c "n", pues se supone que
1246  la rutina invocadora ya hizo ese ajuste en el valor originar de \c "n".
1247  - Esta rutina existe para compartir el código que se necesita para implementar
1248  \c Erase_Son() y \c Graft().
1249  - Si retorna <code> 0 == NULL </code> es porque <code> Nodo[n-1] </code>
1250  debe ser el primero en la lista de hijos del padre.
1251 
1252  \remark [Eliminado porque ya no hace falta]
1253  - "prev_prev" apunta al nodo que está antes de "prev" en el árbol.
1254  - Si "prev" y "prev_prev" son la misma variable, el valor correcto para "prev" es
1255  calculado. */
1256 template <class E>
1257 void Tree<E>::Erase_Son_Prev(unsigned n, Tree_Node<E>* & prev /*, Tree_Node<E>* & prev_prev */) {
1258  // prev_prev = 0; // el que está "antes" de "prev"
1259  prev = 0; // nodo que antecede a "child"
1260  if (m_root == 0) { // ignora árboles vacíos
1261  return;
1262  }
1263  Tree_Node<E>* child = m_root->m_left_child; // "child" es el nodo que hay que eliminar
1264  if ( child == 0 ) { // no hay hijos ==> el Nodo[n] es un sub-árbol vacío
1265  return;
1266  }
1267 
1268  // n++; // sobra, porque la rutina invocadora ya ajustó el valor a cotejar con "m_n_child"
1269 
1270  // camina sobre los hermanos hasta llegar a Nodo[n]
1271  if ( child->m_n_child <= 0 ) { // sólo hay un hijo
1272  unsigned n_child = - child->m_n_child;
1273  if ( n == n_child ) { // es el único hijo y hay que eliminarlo
1274  if ( child->m_refCount <= 1 ) { // aquí saca a "child" de la lista de hijos de "m_root"
1275  Erase0( child );
1276  } else {
1277  child->m_refCount--;
1278  child->m_n_child = -1;
1279  child->m_right_brother = 0; // ya no es hijo de nadie
1280  }
1281  m_root->m_left_child = 0;
1282  return;
1283  } else { // no hace falta eliminar a nadie pues Child(n) es un sub-árbol vacío
1284  // hay que determinar adónde debe apuntar "prev"
1285  if ( n > n_child ) {
1286  // prev_prev = prev;
1287  prev = child;
1288  return; // porque el n-ésimo hijo estará después de "child"
1289  } else { // assert( n < n_child );
1290  return; // el n-ésimo hijo quedará de primero en la lista de hijos del padre
1291  }
1292  }
1293  }
1294 
1295  // assert( (child->m_n_child > 0) && (Count_Children() > 1) );
1296  for (;;) {
1297  if (child->m_n_child <= 0) { // hay que eliminar el último hijo
1298  if ( unsigned(- child->m_n_child) == n ) { // assert( prev != 0 );
1299  prev->m_right_brother = child->m_right_brother;
1300  prev->m_n_child = - prev->m_n_child; // este es el nuevo último
1301  if ( child->m_refCount <= 1 ) {
1302  Erase0( child );
1303  } else {
1304  child->m_refCount--;
1305  child->m_n_child = -1;
1306  child->m_right_brother = 0; // ya no es hijo de nadie
1307  }
1308  } else if ( unsigned(- child->m_n_child) < n ) {
1309  // no encontró al hermano con m_n_child == n
1310  // prev_prev = prev;
1311  prev = child;
1312  }
1313  break;
1314  } else if ( unsigned(child->m_n_child) == n ) {
1315  if ( prev == 0 ) {
1316  m_root->m_left_child = child->m_right_brother;
1317  } else {
1318  prev->m_right_brother = child->m_right_brother;
1319  }
1320  if ( child->m_refCount <= 1 ) {
1321  Erase0( child );
1322  } else {
1323  child->m_refCount--;
1324  child->m_n_child = -1;
1325  child->m_right_brother = 0; // ya no es hijo de nadie
1326  }
1327  break;
1328  } else if ( unsigned(child->m_n_child) < n) {
1329  // prev_prev = prev;
1330  prev = child;
1331  child = child->m_right_brother;
1332  } else { // assert( unsigned(child->m_n_child) > n );
1333  break; // no encontró al hermano con m_n_child == n
1334  }
1335  }
1336 }
1337 
1338 /** Verifica que se cumpla la invariante de la clase, o sea, que el objeto esté bien construido.
1339  - Además de todo el trabajo que hace \c check_ok(Tree& T), acá hay que constatar que
1340  el nodo raíz no tiene padre, que es la diferencia fundamental entre un árbol y un sub-árbol
1341 
1342  \post Retorna \c "true" si el árbol es un objeto bien construido
1343 
1344  \deprecated Los árboles y los sub-árboles son la misma cosa.
1345 
1346  \see \c check_ok(Tree&) */
1347 template <class E>
1348 inline bool check_ok_Tree(Tree<E>& T) {
1349  if ( T.Root().Empty() ) {
1350  return true;
1351  } else {
1352  return ( T.Root().Father().Empty() ) && check_ok( Tree<E> (T) );
1353  }
1354 }
1355 
1356 /** Hace una copia profunda nodo por nodo del árbol cuyo nodo raíz es \c "*p".
1357  - Implementación recursiva para \c Tree::Copy_Deep()
1358  - No altera \c p->m_refCount porque copia los nodos
1359  - El campo \c p->m_right_brother queda con basura porque no queda inicializado
1360  - Le corresponde a la rutina invocadora inicializar \c p->m_right_brother
1361 
1362  \pre <code> p != 0 </code>
1363  \post No cambia \c "p" porque trabaja con una copia de su valor
1364 
1365  \returns Puntero al nodo raíz del árbol copiado */
1366 template <class E>
1368  Tree_Node<E> * q; // resultado
1369  q = Tree_Node<E>::Get_New(p->m_data); // m_refCount = 1;
1370  q->m_n_child = p->m_n_child;
1371 
1372  if ( p->m_left_child == 0 ) {
1373  q->m_left_child = 0;
1374  } else { // cuando hay hijos los copia
1375  Tree_Node<E> * pChild = p->m_left_child;
1376  Tree_Node<E> * qChild = Copy_Deep0( pChild ); // copia el primer nodo
1377  q->m_left_child = qChild;
1378  while ( pChild->m_n_child > 0 ) {
1379  pChild = pChild->m_right_brother;
1380  qChild->m_right_brother = Copy_Deep0( pChild );
1381  qChild = qChild->m_right_brother;
1382  }
1383  qChild->m_right_brother = q; // "q" es el padre de todos
1384  }
1385  return q;
1386 }
1387 
1388 /** Copia profunda de \c "o".
1389  - Copia todo el valor de \c "o" sobre \c "*this", de forma que el nuevo valor de
1390  \c "*this" sea un duplicado exacto del valor de \c "o"
1391  - El valor anterior de \c "*this" se pierde
1392  - El objeto \c "o" mantiene su valor anterior
1393  - Luego de la copia, cuando el valor de \c "o" cambia, el de \c "*this" no cambiará,
1394  y viceversa, pues la copia es una copia profunda; no es superficial
1395  - Si \c "*this" es \c "o" entonces su valor no cambia
1396  - Después de esta operación siempre ocurre que <code> *this == o </code>
1397 
1398  \par Complejidad:
1399  O( \c Count() ) + O( \c o.Count() )
1400 
1401  \returns \c *this
1402 
1403  \see http://www.di-mare.com/adolfo/binder/c04.htm#sc05 */
1404 template <class E>
1406  // Borra el valor actual
1407  if (m_root != 0) {
1408  if ( m_root->m_refCount == 1 ) { // como es el último...
1409  Erase0(m_root); // ...lo mata
1410  } else {
1411  m_root->m_refCount--;
1412  }
1413  }
1414 
1415  // Hace la copia desde "o"
1416  if (o.m_root != 0 ) {
1417  m_root = Copy_Deep0( o.m_root );
1418  m_root->m_n_child = -1; // es el nodo raíz
1419  m_root->m_right_brother = 0;
1420  m_root->m_refCount = 1;
1421  } else {
1422  m_root = 0;
1423  }
1424  return *this;
1425 }
1426 
1427 /** Injerta \c "o" para que sea el \c "n"-ésimo hijo de \c "*this".
1428  - Si \c "o" es sub-árbol de otro árbol, dejara de serlo para pasar ser hijo de \c "*this"
1429  - Si \c "*this" tiene un \c "n"-ésimo hijo, ese hijo desaparece
1430  - Si \c "o" está vacío, elimina el \c "n"-ésimo hijo del árbol [<code> Erase_Son(n) </code>]
1431 
1432  \pre
1433  - <code> ! Root().Empty() </code>
1434  - Si el árbol está vacío no tiene raíz, y por lo tanto tampoco puede tener hijos
1435  - <code> ! Ancestor(o, *this) </code>
1436  - "o" no puede ser ancestro de *this"
1437  - <code> (0 <= n) && (n < \e infinito) </code>
1438  - <code> ! Root(). Same( o.Root() ) </code>
1439 
1440  \post
1441  - \c "o" deja de ser sub-árbol del árbol en que estaba
1442  - <code> o.Father() .Same( Root() ) </code>
1443 
1444  \remarks
1445  - Un sub-árbol puede ser hijo (o sub-árbol) de otro árbol
1446  - Un sub-árbol puede ser hijo únicamente de un árbol
1447  - Este método no hace nada cuando [ <code> ! Root() .Same( o.Root() ) </code> ]
1448  - Injertar un sub-árbol vacío es una forma de eliminar a un hijo junto con
1449  toda su descendencia
1450 
1451  \returns "o" ==> El árbol recién injertado
1452 
1453  \par Complejidad::
1454  O( \c Count_Children() ) + O( <code> o.Father().Count_Children() </code> ) */
1455 template <class E>
1456 Tree<E> Tree<E>::Graft(unsigned n, Tree &o) {
1457  if (m_root == 0) { // ignora árboles vacíos
1458  return Tree( );
1459  }
1460  if (m_root == o.m_root) { // evita auto-borrado
1461  return *this;
1462  }
1463  #ifdef FALTA_verificar_en_Graft
1464  bool Ancestor( Tree & Child, Tree & Father );
1465  assert( ! Ancestor( o, *this ) ); // "o" no puede ser ancestro de *this"
1466  #endif
1467 
1468  n++; // lo incrementa para no incrementar "m_n_child" para cada hijo de "m_root" o de "o"
1469 
1470  if ( o.m_root == 0 ) { // Sólo hay que eliminar el hijo número "n" de "m_root"
1471  Tree_Node<E> * prev;
1472  Erase_Son_Prev(n, prev /*, prev */);
1473  return Tree( ); // si se vale repetir "prev" en Erase_Son_Prev()
1474  }
1475  // assert( o.m_root != 0 );
1476 
1477  // Determina quién es el padre de "o"
1478  Tree_Node<E> * brother = o.m_root;
1479  while ( brother->m_n_child > 0 ) {
1480  brother = brother->m_right_brother;
1481  }
1482  Tree_Node<E> * o_father = brother->m_right_brother; // éste es el padre de "o"
1483  Tree_Node<E> * prev;
1484 
1485  if ( o_father != m_root ) {
1486  /* El puntero "prev" apunta al nodo después del que hay que injertar "o".
1487  - Si "prev == 0" hay que poner a "o" de primero en lista de hijos de "m_root".
1488  - Si "prev != 0" hay que instalar "o" después de "prev".
1489  - Aquí es donde se usa Erase_Son_Prev().
1490  */
1491  // Elimina el hijo número "n" de "m_root"
1492  Erase_Son_Prev(n, prev /*, prev */);
1493  // assert( Child(n-1).Empty() ); // Ojo: mata "Child(n-1)" porque ya "n" está incrementado
1494  } else { // assert( o_father == m_root ); // Caso especial ==> T.Graft( T.Child(n), n ± i );
1495  unsigned o_n_child = o.m_root->Abs_n_child();
1496  if ( o_n_child == n ) { // Caso especial cuando "o" ya es hijo de "m_root"
1497  // "o" está en su lugar ==> no hay que hacer nada
1498  // [y hay que evitar borrarlo con Erase_Son(n)]
1499  return Tree( (NOT_null_pointer*) o.m_root );
1500  }
1501 
1502  Erase_Son_Prev(n, prev /*, prev */);
1503 
1504  if ( (prev == o.m_root) || (prev != 0 && prev->m_right_brother == o.m_root ) ) {
1505  // ya "o" está en donde debe
1506  if ( o.m_root->m_right_brother == m_root ) { // basta cambiar "m_n_child"
1507  o.m_root->m_n_child = - int(n);
1508  } else {
1509  o.m_root->m_n_child = + int(n);
1510  }
1511  return Tree( (NOT_null_pointer*) o.m_root );
1512  }
1513  }
1514 
1515  if (o_father != 0) { // Saca a "o" de la lista de hijos de su padre
1516  o.m_root->m_refCount--; // pues no estará en la lista de hijos de su padre actual
1517  assert( o_father->m_left_child != 0 );
1518  if ( o.m_root == o_father->m_left_child ) { // "o" es el primer hijo
1519  if ( o.m_root->m_n_child < 0 ) { // "o" es el único hijo
1520  o_father->m_left_child = 0;
1521  } else { // "o" tiene hermanos
1522  o_father->m_left_child = o.m_root->m_right_brother;
1523  }
1524  } else {
1525  brother = o_father->m_left_child; // hermano más izquierdo de "o"
1526  while ( brother->m_right_brother != o.m_root ) {
1527  brother = brother->m_right_brother;
1528  }
1529  brother->m_right_brother = o.m_root->m_right_brother;
1530  if ( o.m_root->m_n_child < 0 ) { // "o" estaba de último hijo
1531  brother->m_n_child = - brother->m_n_child; // hay un nuevo hijo de último
1532  }
1533  }
1534  }
1535  // assert( o.Father().Empty() ); // ya "o" está solito y sin familia
1536 
1537  o.m_root->m_refCount++; // lo incrementa porque lo va a enlazar como hijo de "m_root"
1538 
1539  if ( prev == 0 ) { // enlaza "o" al principio de la lista de hijos de "m_root"
1540  if ( m_root->m_left_child == 0 ) {
1541  o.m_root->m_right_brother = m_root; // "o" será el único hijo de "m_root"
1542  o.m_root->m_n_child = - int(n);
1543  m_root->m_left_child = o.m_root;
1544  } else {
1545  o.m_root->m_right_brother = m_root->m_left_child;
1546  // assert( o.m_root->m_right_brother != m_root );
1547  o.m_root->m_n_child = + int(n);
1548  m_root->m_left_child = o.m_root;
1549  }
1550  } else { // assert( prev != 0 );
1551  // enlaza en el medio de la lista de hijos de "m_root"
1552  o.m_root->m_right_brother = prev->m_right_brother;
1553  prev->m_right_brother = o.m_root;
1554  if ( o.m_root->m_right_brother == m_root ) {
1555  prev->m_n_child = - prev->m_n_child; // ya "prev" no está de último
1556  o.m_root->m_n_child = - int(n);
1557  } else {
1558  o.m_root->m_n_child = + int(n);
1559  }
1560  }
1561 
1562  return Tree( (NOT_null_pointer*) o.m_root );
1563 
1564 
1565 /* ¿Por qué hay que usar "prev_prev"? En realidad no hace falta, pero sí hay que
1566  destacar un caso especial, cuando "o" es hijo de "*this", o sea cuando:
1567  - ( Root(). Same( o.Root() ) )
1568  R T.Erase(); T = 'R';
1569  / \ T.Change_Child(1, '1');
1570  1 3 T.Change_Child(3, '3');
1571 
1572  Al ejecutar T.Graft( 5 , T.Child(3) ); lo que hay que hacer es desligar el Nodo['3'] de su
1573  padre, el árbol T que tiene por raíz a Nodo['A'], para ligarlo de nuevo como Nodo['5'].
1574 
1575  Para este caso, "prev" apunto a T.Child(3), pues es después de Nodo['3'] en donde habría
1576  que enlazar a Nodo['5']. Desafortunadamente, como el primer paso del algoritmo saca de
1577  T a Nodo[3], al tratar de enlazarlo luego de "prev" en realidad lo que se haría es
1578  enlazar al nodo después de sí mismo; estor resulta en la "desaparición misteriosa"
1579  de Nodo['3']. Por eso, la solución a este caso especial, es retornar no "prev", sino
1580  "prev_prev", que apunta al nodo anterio al Nodo[5], que en este caso es Nodo['1'].
1581 */
1582 } // Graft()
1583 
1584 } // namespace TL
1585 
1586 #endif // Tree_L_h
1587 
1588 // EOF: Tree_L.h
~Tree()
Destructor.
Definition: Tree_L.h:250
Tree Previous_Sibling() const
Sinónimo de Left_Sibling()
Definition: Tree_L.h:164
Tree Left() const
Sub-árbol izquierdo [en un árbol binario].
Definition: Tree_L.h:429
bool check_ok(const E &)
unsigned Size() const
Usa Count() para retornar la cantidad de valores almacenados en el sub-árbol.
Definition: Tree_L.h:94
Tree_Node(const value_type &d)
Constructor de vector.
Definition: Tree_L.h:36
void NOT_null_pointer
Truco para usar el constructor que no verifica (p != 0)
Definition: Tree_L.h:82
friend bool operator!=(const Tree< X > &p, const Tree< X > &q)
¿¿¿ (p != q) ???
bool operator!=(const Tree< E > &p, const Tree< E > &q)
Definition: Tree_L.h:806
unsigned Count() const
Retorna la cantidad de valores almacenados en el sub-árbol.
Definition: Tree_L.h:770
Tree Father() const
Acceso al padre.
Definition: Tree_L.h:355
Tree & Copy(const Tree &o)
Copia superficial desde &quot;o&quot;.
Definition: Tree_L.h:279
E value_type
Nombre estándar del tipo de elemento contenido.
Definition: Tree_L.h:34
friend bool operator==(const Tree< X > &p, const Tree< X > &q)
¿¿¿ (p == q) ???
static bool Comp0(const Tree_Node< E > *p, const Tree_Node< E > *q)
Compara recursivamente los árboles cuyos nodo raíz son &quot;*p&quot; y &quot;*q&quot;.
Definition: Tree_L.h:811
static void Erase0(Tree_Node< E > *p)
Elimina recursivamente a &quot;*p&quot; y a todos sus descendientes.
Definition: Tree_L.h:1129
unsigned Child_Number() const
Retorna &quot;n&quot; si &quot;*this&quot; es el n-ésimo hijo de su padre, si no retorna 0 (cero)
Definition: Tree_L.h:175
static Tree_Node< E > * Get_New(const value_type &d)
Crea un nuevo nodo y lo inicializa con &quot;d&quot;.
Definition: Tree_L.h:224
value_type & Data()
Valor almacenado en la raíz del sub-árbol.
Definition: Tree_L.h:133
unsigned Count_Children() const
Retorna la cantidad de hijos del árbol.
Definition: Tree_L.h:784
friend bool check_ok(const Tree< E > &T)
Verifica que se cumpla la invariante de la clase, o sea, que el objeto esté bien construido.
Tree Change_Left_Sibling_Inmediate(const value_type &d)
Sustituye por &quot;d&quot; el valor almacenado en el hermano inmediatamente anterior del sub-árbol.
Definition: Tree_L.h:1042
Tree Graft(unsigned n, Tree &o)
Injerta &quot;o&quot; para que sea el &quot;n&quot;-ésimo hijo de &quot;*this&quot;.
Definition: Tree_L.h:1456
bool Is_Root() const
Retorna &quot;true&quot; si el árbol no tiene padre.
Definition: Tree_L.h:183
bool Equals(const Tree &o) const
¿¿¿ (*this==o) ???
Definition: Tree_L.h:146
unsigned use_count() const
Cantidad de referencias de la raíz del árbol.
Definition: Tree_L.h:185
bool operator==(const Tree< E > &p, const Tree< E > &q)
Definition: Tree_L.h:804
Tree Change_Root(const value_type &d)
Sustituye por &quot;d&quot; el valor almacenado en la raíz del árbol.
Definition: Tree_L.h:926
value_type m_data
Valor almacenado en el nodo.
Definition: Tree_L.h:40
bool Same(const Tree &o) const
Retorna true si &quot;o&quot; comparte la raíz con &quot;*this&quot;.
Definition: Tree_L.h:148
Tree Prev_Sibling() const
Sinónimo de Left_Sibling()
Definition: Tree_L.h:165
Tree & Move(Tree &o)
Traslada el valor de &quot;o&quot; a &quot;*this&quot;.
Definition: Tree_L.h:311
static Tree & CastTo_Sub_Tree_Ref(Tree_Node< E > *&p)
Convierte el puntero al nodo en un referencia a Tree.
Definition: Tree_L.h:192
bool Is_Leaf() const
Retorna &quot;true&quot; si el árbol es una hoja.
Definition: Tree_L.h:181
void Erase()
Elimina el árbol y sus descendientes.
Definition: Tree_L.h:1183
Tree & Copy_Deep(const Tree &o)
Copia profunda de &quot;o&quot;.
Definition: Tree_L.h:1405
Tree Right_Sibling() const
Obtiene el hermano no vacío siguiente, que está hacia la derecha.
Definition: Tree_L.h:521
unsigned Leftmost_N() const
Retorna &quot;n&quot; si el hijo más izquierdo de &quot;*this&quot; es el n-ésimo hijo, si no retorna 0 (cero) ...
Definition: Tree_L.h:177
Tree Leftmost() const
Obtiene el hijo más izquierdo del árbol.
Definition: Tree_L.h:698
Tree Sibling(int n) const
&quot;n&quot;-ésimo hermano a partir de &quot;*this&quot;.
Definition: Tree_L.h:625
const value_type & Data() const
Valor almacenado en la raíz del sub-árbol.
Definition: Tree_L.h:136
Tree Next_Sibling() const
Sinónimo de Right_Sibling()
Definition: Tree_L.h:166
bool Ok()
Usa check_ok(Tree&amp; T) para verificar la invariante de Tree.
Definition: Tree_L.h:96
Tree Change_Right_Sibling_Inmediate(const value_type &d)
Sustituye por &quot;d&quot; el valor almacenado en el hermano inmediatamente posterior del sub-árbol.
Definition: Tree_L.h:1066
Tree()
Constructor de vector.
Definition: Tree_L.h:74
bool Empty() const
Retorna &quot;true&quot; si el sub-árbol está vacío.
Definition: Tree_L.h:91
value_type & operator*()
Valor almacenado en la raíz del sub-árbol.
Definition: Tree_L.h:134
unsigned Abs_n_child() const
Retorna el valor absoluto del campo &quot;m_n_child&quot;.
Definition: Tree_L.h:594
Tree_Node< E > * m_root
Un árbol &quot;es&quot; el puntero al nodo raíz.
Definition: Tree_L.h:205
Tree Left_Sibling() const
Obtiene el hermano no vacío anterior, que está hacia la izquierda.
Definition: Tree_L.h:474
int m_n_child
Soy el el hijo número &quot;(m_n_child - 1)&quot; de mi padre.
Definition: Tree_L.h:42
Tree & operator=(const Tree &o)
Sinónimo de this-&gt;Copy(o)
Definition: Tree_L.h:111
Los métodos para trabajar con árboles regresan &quot;referencias&quot; que son sub-árboles. ...
Definition: Tree_L.h:25
Tree Right_Sibling_Inmediate() const
Obtiene el hermano que está inmediatamente hacia la derecha.
Definition: Tree_L.h:551
Tree(Tree_Node< E > *p)
Constructor a partir de un nodo.
Definition: Tree_L.h:80
Tree Left_Sibling_Inmediate() const
Obtiene el hermano que está inmediatamente hacia la izquierda.
Definition: Tree_L.h:540
void Erase_Son(unsigned n)
Elimina el sub-árbol número &quot;n&quot;.
Definition: Tree_L.h:103
static void Count0(const Tree_Node< E > *p, unsigned &n)
Implementación recursiva para Count().
Definition: Tree_L.h:744
Tree Rightmost() const
Obtiene el hijo más derecho del árbol.
Definition: Tree_L.h:721
void Erase_Son_Prev(unsigned n, Tree_Node< E > *&)
Elimina el sub-árbol número &quot;n-1&quot; y retorna un puntero al nodo anterior al borrado.
Definition: Tree_L.h:1257
Tree_Node< E > * m_right_brother
Puntero al nodo hermano o al padre.
Definition: Tree_L.h:44
Tree & operator=(const value_type &d)
Usa Change_Root() para sustituir por &quot;d&quot; el valor almacenado en la raíz del árbol.
Definition: Tree_L.h:117
value_type * operator->()
Puntero al valor almacenado en la raíz del sub-árbol.
Definition: Tree_L.h:135
unsigned m_refCount
Cantidad de punteros hacia mi.
Definition: Tree_L.h:41
E value_type
Nombre estándar del tipo de elemento contenido.
Definition: Tree_L.h:70
Nodos almacenados en el árbol.
Definition: Tree_L.h:31
bool check_ok_Tree(Tree< E > &T)
Verifica que se cumpla la invariante de la clase, o sea, que el objeto esté bien construido.
Definition: Tree_L.h:1348
Tree_Node< E > * m_left_child
Puntero al nodo hijo más izquierdo.
Definition: Tree_L.h:43
Tree Child(unsigned n) const
Acceso al &quot;n&quot;-ésimo hijo.
Definition: Tree_L.h:375
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 &quot;*p&quot;.
Definition: Tree_L.h:1367
Tree(NOT_null_pointer *p)
Constructor a partir de un nodo [ requiere p != 0 ].
Definition: Tree_L.h:84
Tree & Swap(Tree &o)
Intercambia los valores de &quot;*this&quot; y &quot;o&quot;.
Definition: Tree_L.h:342
Tree Change_Child(unsigned n, const value_type &d)
Sustituye por &quot;d&quot; el valor almacenado en el hijo número &quot;n&quot; del árbol.
Definition: Tree_L.h:949
Tree Right() const
Sub-árbol derecho [en un árbol binario].
Definition: Tree_L.h:445
Tree Root() const
Raíz del sub-árbol.
Definition: Tree_L.h:154
unsigned Rightmost_N() const
Retorna &quot;n&quot; si el hijo más derecho de &quot;*this&quot; es el n-ésimo hijo, si no retorna 0 (cero) ...
Definition: Tree_L.h:179