Del básico al intermedio: Colas, listas y árboles (VI)

Introducción

En el artículo anterior, Del básico al intermedio: Clases (III), concluimos la presentación de los conceptos básicos e introductorios sobre qué es y cómo funciona la programación orientada a objetos. La finalidad de presentar estos conceptos es que comprendas, mi querido lector, lo que implementaremos en los próximos artículos. Esto se debe a que retomaremos la explicación de un tema muy importante y, al mismo tiempo, muy interesante, tanto desde el punto de vista práctico como teórico.

Bien, sin más preámbulos, volvamos al tema que realmente nos interesa. Para ello, pasemos a un nuevo tema.

Colas, listas y árboles (VI)

En el último artículo dedicado a este tema, Del básico al intermedio: Colas, listas y árboles (V), vimos el comienzo de una implementación básica de un árbol genérico. Sin embargo, nos encontramos con un problema que no podía corregirse sin explicar antes algunos conceptos. Estos conceptos se abordaron en los tres últimos artículos, cuyo objetivo principal fue presentar y demostrar cómo se crean y destruyen los objetos de una clase.

Sin estos conocimientos sobre constructores y destructores, resulta prácticamente imposible comprender por qué tanto los códigos ya implementados como los que todavía implementaremos funcionarán sin errores. Sin embargo, si intentaras modificarlos, ya sea con fines de estudio o para adaptarlos a otros propósitos, podrías acabar con un código que continuara generando errores al finalizar su ejecución.

Para entender mejor lo que quiero decir, revisemos uno de los códigos presentados en el artículo mencionado. Puedes verlo a continuación.

01. //+------------------------------------------------------------------+
02. #property copyright "Daniel Jose"
03. //+------------------------------------------------------------------+
04. class stTree
05. {
06.     public:
07.         int     info;
08.         stTree  *left,
09.                 *right;
10. };
11. //+------------------------------------------------------------------+
12. stTree *store(stTree *root, stTree *r, int info)
13. {
14.     if (r == NULL)
15.     {
16.         r = new stTree;
17. 
18.         (*r).left = NULL;
19.         (*r).right = NULL;
20.         (*r).info = info;
21.         if (root == NULL) return r;
22.         if (info < (*root).info) (*root).left = r;
23.         else (*root).right = r;
24. 
25.         return r;
26.     }
27.     if (info < (*r).info) return store(r, (*r).left, info);
28.     return store(r, (*r).right, info);
29. }
30. //+------------------------------------------------------------------+
31. string inorder(stTree *root)
32. {
33.     static string sz0 = "In Order: ";
34. 
35.     if (root == NULL) return sz0;
36. 
37.     inorder((*root).left);
38.     sz0 += (root != NULL ? StringFormat("%d  ", (*root).info) : "");
39.     inorder((*root).right);
40. 
41.     return sz0;
42. }
43. //+------------------------------------------------------------------+
44. string preorder(stTree *root)
45. {
46.     static string sz0 = "Pre Order: ";
47. 
48.     if (root == NULL) return sz0;
49. 
50.     sz0 += (root != NULL ? StringFormat("%d  ", (*root).info) : "");
51.     preorder((*root).left);
52.     preorder((*root).right);
53. 
54.     return sz0;
55. }
56. //+------------------------------------------------------------------+
57. string postorder(stTree *root)
58. {
59.     static string sz0 = "Post Order: ";
60. 
61.     if (root == NULL) return sz0;
62. 
63.     postorder((*root).left);
64.     postorder((*root).right);
65.     sz0 += (root != NULL ? StringFormat("%d  ", (*root).info) : "");
66. 
67.     return sz0;
68. }
69. //+------------------------------------------------------------------+
70. void OnStart(void)
71. {
72.     stTree *root = NULL;
73. 
74.     root = store(root, root, 10);
75.     store(root, root, -6);
76.     store(root, root, 47);
77.     store(root, root, 35);
78.     store(root, root, 85);
79. 
80.     Print(inorder(root));
81.     Print(preorder(root));
82.     Print(postorder(root));
83. }
84. //+------------------------------------------------------------------+

Código 01

Este código 01, explicado en el artículo citado al comienzo de este tema, contiene un fallo. En realidad, funciona correctamente en cuanto a los resultados que produce. Sin embargo, cuando finaliza su ejecución, se genera un problema que MetaTrader 5 notifica, como se muestra en la imagen siguiente.

Imagen 01

El fallo es precisamente el que aparece en la región marcada de la imagen 01. Pero espera un momento. ¿Me estás diciendo que el código contiene un error y que ese error se encuentra en la región marcada de la imagen 01 anterior? A mi parecer, eso no sería realmente un error, sino una advertencia de que algo no se está realizando. En cierto modo, tienes razón, mi querido lector. Sin embargo, no es exactamente así.

Lo que aparece marcado en la imagen 01 es realmente un error, porque estamos asignando recursos y no los estamos liberando. En este caso, el recurso asignado es la memoria. Sin embargo, para evitar la rápida degradación de este recurso, MetaTrader 5 la libera de una forma algo forzada, lo que supone una sobrecarga adicional de procesamiento para la plataforma, perfectamente evitable.

En procesos sencillos como los que analizamos en estos artículos, este tipo de fallos puede tolerarse, precisamente porque estamos practicando y estudiando un tema. Sin embargo, no es aceptable que existan en una aplicación que se considere terminada o que tenga un ámbito de uso más amplio, ya que podrían comprometer la integridad de los datos generados o procesados.

Por tanto, para resolver este tipo de fallo, que puede verse en la imagen 01, debemos recurrir a los conocimientos y conceptos presentados en los tres últimos artículos, donde hablamos sobre clases. Solo así podremos implementar la solución sin grandes dificultades ni sobresaltos y corregir definitivamente el problema mostrado en la imagen 01.

Bien, para empezar, haremos algunos cambios en el código 01 para inicializar correctamente los datos de la clase. Los primeros cambios pueden verse en el código siguiente.

01. //+------------------------------------------------------------------+
02. #property copyright "Daniel Jose"
03. //+------------------------------------------------------------------+
04. class C_Tree
05. {
06.     private :
07.         int     info;
08.         C_Tree  *left,
09.                 *right;
10.     public  :
11.         C_Tree()
12.             :left(NULL),
13.              right(NULL)
14.         {
15.         }
16. //+----------------+
17.         C_Tree *Store(C_Tree *root, C_Tree *r, int arg)
18.         {
19.             if (r == NULL)
20.             {
21.                 r = new C_Tree;
22.                 
23.                 (*r).info = arg;
24.                 if (root == NULL) return r;
25.                 if (arg < (*root).info) (*root).left = r;
26.                 else (*root).right = r;
27. 
28.                 return r;
29.             }
30.             if (arg < (*r).info) return Store(r, (*r).left, arg);
31.             return Store(r, (*r).right, arg);
32.         }
33. //+----------------+
34.         string inorder(C_Tree *root)
35.         {
36.             static string sz0 = "In Order: ";
37. 
38.             if (root == NULL) return sz0;
39. 
40.             inorder((*root).left);
41.             sz0 += (root != NULL ? StringFormat("%d  ", (*root).info) : "");
42.             inorder((*root).right);
43. 
44.             return sz0;
45.         }
46. //+----------------+
47.         string preorder(C_Tree *root)
48.         {
49.             static string sz0 = "Pre Order: ";
50. 
51.             if (root == NULL) return sz0;
52. 
53.             sz0 += (root != NULL ? StringFormat("%d  ", (*root).info) : "");
54.             preorder((*root).left);
55.             preorder((*root).right);
56. 
57.             return sz0;
58.         }
59. //+----------------+
60.         string postorder(C_Tree *root)
61.         {
62.             static string sz0 = "Post Order: ";
63. 
64.             if (root == NULL) return sz0;
65. 
66.             postorder((*root).left);
67.             postorder((*root).right);
68.             sz0 += (root != NULL ? StringFormat("%d  ", (*root).info) : "");
69. 
70.             return sz0;
71.         }
72. //+----------------+
73. };
74. //+------------------------------------------------------------------+
75. void OnStart(void)
76. {
77.     C_Tree *root = NULL,
78.             Tree;
79. 
80.     root = Tree.Store(root, root, 10);
81.     Tree.Store(root, root, -6);
82.     Tree.Store(root, root, 47);
83.     Tree.Store(root, root, 35);
84.     Tree.Store(root, root, 85);
85. 
86.     Print(Tree.inorder(root));
87.     Print(Tree.preorder(root));
88.     Print(Tree.postorder(root));
89. }
90. //+------------------------------------------------------------------+

Código 02

Ahora observa que el código que antes estaba disperso por el archivo ahora está contenido en una clase. De este modo, los datos quedan protegidos, lo que evita accesos indebidos que podrían comprometer la integridad de los datos almacenados en el árbol que estamos construyendo.

Sin embargo, a pesar de este pequeño cambio, el código 02 seguirá produciendo el mismo tipo de resultado que aparece en la imagen 01. Aun así, quiero que prestes atención a un detalle, mi querido lector. Compara la función Store del código 01 con la misma función del código 02. Verás que ya no tenemos que preocuparnos por inicializar los punteros left y right dentro de la función Store. Esto se debe al constructor de la clase, que se invoca en la línea 21 del código 02, lo que garantiza la inicialización correcta de los miembros internos del objeto. Si no comprendes esta explicación, consulta los tres últimos artículos para obtener más detalles.

Muy bien, ya tenemos implementada la fase correspondiente al constructor. Por tanto, podemos pasar al destructor. Sin embargo, la lógica del destructor de un árbol debe planificarse con bastante cuidado, porque, según cómo queramos destruir el árbol, tendremos que implementar más o menos código. No obstante, como aquí el objetivo es puramente didáctico, seguiremos un enfoque algo más sencillo, aunque esto nos obligue a modificar el código actual.

Para empezar, debemos modificar una parte del código, porque comienza a resultar algo confuso. Los árboles ya pueden resultar bastante confusos por sí solos, según cómo pensemos utilizarlos. Los programadores con más experiencia quizá consideren que lo que haré es una pérdida de tiempo. Sin embargo, para quienes están empezando, este cambio puede marcar la diferencia entre comprender o no el código que vamos a implementar. Pero, si ya tienes cierta experiencia, quiero que vuelvas a observar este código 02 y respondas con total sinceridad. ¿Puedes entender correctamente lo que se hace dentro de la función OnStart? ¿Puedes distinguir entre la declaración root de la línea 77, que representa un nodo, y la declaración Tree de la línea 78, que contendrá el árbol binario? Si la respuesta es afirmativa, perfecto. Sin embargo, muchos principiantes tendrán dificultades para establecer esta distinción. Precisamente por eso, debemos replantear la implementación mediante un enfoque ligeramente distinto.

Para empezar, si realmente sabes qué es un árbol y para qué suele utilizarse, sabrás que NO permitimos el acceso directo a determinados elementos internos del árbol. Una de ellas es precisamente la raíz, es decir, la variable declarada en la línea 77 del código 02. Aunque permitir este acceso no constituye un error, puede provocar una gran cantidad de problemas, muchos de los cuales impedirían que el árbol construido funcionara y se utilizara correctamente. Para evitar este tipo de situaciones, que a menudo resultan bastante comprometedoras, normalmente dividimos el código en bloques más pequeños. Esto facilita tanto la implementación como las posibles modificaciones y mejoras del código final.

Así pues, mi querido lector, demos un paso atrás y comencemos a implementar de otra manera el código para construir el árbol. Puedes verlo a continuación.

01. //+------------------------------------------------------------------+
02. #property copyright "Daniel Jose"
03. //+------------------------------------------------------------------+
04. class C_TreeNode
05. {
06.     private :
07. //+----------------+
08.         int         info;
09.         C_TreeNode  *left,
10.                     *right;
11. //+----------------+
12.     public  :
13. //+----------------+
14.         C_TreeNode()
15.             :left(NULL),
16.             right(NULL)
17.         {}
18. //+----------------+
19.         void SetInfo(int arg) { info = arg; }
20. //+----------------+
21.         int GetInfo(void) const { return info; }
22. //+----------------+
23.         C_TreeNode *GetLeft(void) const { return left; }
24. //+----------------+
25.         C_TreeNode *GetRight(void) const { return right; }
26. //+----------------+
27. };
28. //+------------------------------------------------------------------+
29. class C_Tree
30. {
31.     private :
32.         C_TreeNode *root;
33.     public  :
34. //+----------------+
35.         C_Tree()
36.             :root(NULL)
37.         {}
38. //+----------------+
39. };
40. //+------------------------------------------------------------------+
41. void OnStart(void)
42. {
43.     C_Tree Tree;
44. }
45. //+------------------------------------------------------------------+

Código 03

Ahora presta atención a un detalle, mi querido lector. Tenemos dos clases: una destinada a representar cada nodo del árbol, implementada en la línea cuatro, y otra que construirá nuestro árbol, implementada en la línea 29.

De este modo, la implementación comienza a seguir una estructura más adecuada, porque dejamos de estar condicionados por aspectos que dificultan enormemente la implementación y obtenemos un mayor grado de libertad y seguridad. Esto se debe a que limitamos el acceso a la información estrictamente necesaria. Observa que ahora, en la línea 32, dentro de la clase que implementará el árbol, declaramos una variable para almacenar el nodo raíz. De este modo, dentro de la propia función OnStart solo necesitamos declarar una variable que contendrá la instancia de nuestro árbol, lo que nos libera de tener que controlar y mantener el nodo raíz.

Bien, entonces ¿cómo implementaremos ahora lo que se hizo en los códigos anteriores? Pues bien, mi querido lector, esta es la parte fácil y divertida de todo nuestro trabajo. Para volver a obtener en nuestro nuevo código el mismo comportamiento que ofrecía el código 02, debemos implementar algunas cosas. Verás que, al final, todo será mucho más sencillo que lo implementado, por ejemplo, en el código 02. Así pues, nuestro siguiente paso consiste en implementar lo que se muestra a continuación.

001. //+------------------------------------------------------------------+
002. #property copyright "Daniel Jose"
003. //+------------------------------------------------------------------+
004. class C_TreeNode
005. {
006.     private :
007. //+----------------+
008.         int         info;
009.         C_TreeNode  *left,
010.                     *right;
011. //+----------------+
012.     public  :
013. //+----------------+
014.         C_TreeNode()
015.             :left(NULL),
016.             right(NULL)
017.         {}
018. //+----------------+
019.         void SetInfo(int arg) { info = arg; }
020. //+----------------+
021.         void SetLeft(C_TreeNode *ptr) { left = ptr; }
022. //+----------------+
023.         void SetRight(C_TreeNode *ptr) { right = ptr; }
024. //+----------------+
025.         int GetInfo(void) const { return info; }
026. //+----------------+
027.         C_TreeNode *GetLeft(void) const { return left; }
028. //+----------------+
029.         C_TreeNode *GetRight(void) const { return right; }
030. //+----------------+
031. };
032. //+------------------------------------------------------------------+
033. class C_Tree
034. {
035.     private :
036.         C_TreeNode *root;
037. //+----------------+
038.         C_TreeNode *Insert(C_TreeNode *arg, C_TreeNode *ptr, int info)
039.         {
040.             if (ptr == NULL)
041.             {
042.                 ptr = new C_TreeNode;
043. 
044.                 (*ptr).SetInfo(info);
045.                 if (arg == NULL) return ptr;
046.                 if (info < (*arg).GetInfo()) (*arg).SetLeft(ptr);
047.                 else (*arg).SetRight(ptr);
048. 
049.                 return ptr;
050.             }
051.             if (info < (*ptr).GetInfo()) return Insert(ptr, (*ptr).GetLeft(), info);
052.             else return Insert(ptr, (*ptr).GetRight(), info);
053.         }
054. //+----------------+
055.         string inOrder(C_TreeNode *ptr)
056.         {
057.             static string sz0 = "In Order: ";
058. 
059.             if (ptr == NULL) return sz0;
060. 
061.             inOrder((*ptr).GetLeft());
062.             sz0 += (ptr != NULL ? StringFormat("%d  ", (*ptr).GetInfo()) : "");
063.             inOrder((*ptr).GetRight());
064. 
065.             return sz0;
066.         }
067. //+----------------+
068.         string preOrder(C_TreeNode *ptr)
069.         {
070.             static string sz0 = "Pre Order: ";
071. 
072.             if (ptr == NULL) return sz0;
073. 
074.             sz0 += (ptr != NULL ? StringFormat("%d  ", (*ptr).GetInfo()) : "");
075.             preOrder((*ptr).GetLeft());
076.             preOrder((*ptr).GetRight());
077. 
078.             return sz0;
079.         }
080. //+----------------+
081.         string postOrder(C_TreeNode *ptr)
082.         {
083.             static string sz0 = "Post Order: ";
084. 
085.             if (ptr == NULL) return sz0;
086. 
087.             postOrder((*ptr).GetLeft());
088.             postOrder((*ptr).GetRight());
089.             sz0 += (ptr != NULL ? StringFormat("%d  ", (*ptr).GetInfo()) : "");
090. 
091.             return sz0;
092.         }
093. //+----------------+
094.     public  :
095. //+----------------+
096.         C_Tree()
097.             :root(NULL)
098.         {}
099. //+----------------+
100.         void Store(int info)
101.         {
102.             if (root == NULL) root = Insert(root, root, info);
103.             else Insert(root, root, info);
104.         }
105. //+----------------+
106.         string In_Order(void)
107.         {
108.             return inOrder(root);
109.         }
110. //+----------------+
111.         string Pre_Order(void)
112.         {
113.             return preOrder(root);
114.         }
115. //+----------------+
116.         string Post_Order(void)
117.         {
118.             return postOrder(root);
119.         }
120. //+----------------+
121. };
122. //+------------------------------------------------------------------+
123. void OnStart(void)
124. {
125.     C_Tree Tree;
126. 
127.     Tree.Store(10);
128.     Tree.Store(-6);
129.     Tree.Store(47);
130.     Tree.Store(35);
131.     Tree.Store(85);
132. 
133.     Print(Tree.In_Order());
134.     Print(Tree.Pre_Order());
135.     Print(Tree.Post_Order());
136. }
137. //+------------------------------------------------------------------+

Código 04

Como había olvidado implementar un pequeño detalle en la clase C_TreeNode del código 03, aquí, en el código 04, corrijo ese pequeño fallo. Ahora presta atención a un detalle de este código 04. El comportamiento de este código es idéntico al de los códigos anteriores. Sin embargo, compara el código de la función OnStart de este código 04 con el de los códigos 01 y 02. Observa que aquí el código resulta mucho más sencillo.

Esto no significa que el código 04 haya dejado de funcionar como antes. Es decir, pese a las modificaciones realizadas para simplificar el uso de la clase C_Tree, internamente el código 04 continúa aplicando los mismos principios que antes. En otras palabras, todo el árbol sigue creándose de forma completamente recursiva. Por eso, puedes observar que las funciones privadas de la clase C_Tree de este código 04 se parecen mucho a lo que se hacía en los códigos 01 y 02. Precisamente por ello, prácticamente no necesitamos retomar la explicación desde el principio, ya que se mantuvo toda la metodología, pero con una forma mucho más cómoda de utilizar las funciones disponibles.

Sin embargo, pese a las modificaciones realizadas en el código 04, seguimos teniendo el mismo problema que nos afectaba al comienzo de este artículo: las indicaciones destacadas en la imagen 01. No obstante, como el código 04 se encuentra ahora mejor implementado y resulta mucho más fácil de entender, finalmente podemos abordar el destructor de la clase C_Tree. Para ello, solo debemos observar atentamente las funciones privadas de la clase C_Tree. Para eliminar o, mejor dicho, liberar la memoria reservada, tendremos que hacer algo muy parecido a lo que hacemos para recorrer el árbol. Pensemos un momento.

Al observar las funciones de recorrido del árbol, notarás un detalle interesante e importante para nosotros. Cuando utilizamos la función inOrder, que aparece en la línea 55, realizamos una llamada para buscar el nodo situado más a la izquierda. Cuando lo encontramos, comenzamos a leer los valores nodo por nodo. Sin embargo, después de recorrer los nodos de la izquierda, empezamos a recorrer los de la derecha. Es decir, no podemos destruir el nodo central sin dificultar el acceso a los nodos de la derecha.

En cuanto a la función preOrder, que aparece en la línea 68, tenemos una situación aún más complicada. Esto se debe a que primero visitamos el nodo actual, o central, y solo después accedemos a los nodos de la izquierda y de la derecha. Sin duda, esto complica mucho las cosas. Recuerda que nuestro objetivo es destruir el árbol.

Bien, solo nos queda un último intento: probar la función postOrder, que aparece en la línea 81. Esta función sí resulta muy adecuada para nuestro objetivo, precisamente por la forma en que recorre el árbol. Observa que primero buscamos los nodos situados a mayor profundidad en el árbol. Solo después de alcanzarlas comenzamos a visitar el nodo central. Hum, esto parece prometedor, ya que, cuando ese nodo central ya no esté conectado a ningún otro nodo, ni al hijo izquierdo ni al derecho, podremos eliminarlo sin problemas. De este modo, podremos implementar el destructor de la clase. Muy bien, veamos cómo podría implementarse el código aplicando el principio que acabamos de identificar al observar el código ya implementado. El nuevo código, que ahora incluirá el destructor, se muestra a continuación.

001. //+------------------------------------------------------------------+
002. #property copyright "Daniel Jose"
003. //+------------------------------------------------------------------+
004. class C_TreeNode
005. {
006.     private :
007. //+----------------+
008.         int         info;
009.         C_TreeNode  *left,
010.                     *right;
011. //+----------------+
012.     public  :
013. //+----------------+
014.         C_TreeNode()
015.             :left(NULL),
016.             right(NULL)
017.         {}
018. //+----------------+
019.         void SetInfo(int arg) { info = arg; }
020. //+----------------+
021.         void SetLeft(C_TreeNode *ptr) { left = ptr; }
022. //+----------------+
023.         void SetRight(C_TreeNode *ptr) { right = ptr; }
024. //+----------------+
025.         int GetInfo(void) const { return info; }
026. //+----------------+
027.         C_TreeNode *GetLeft(void) const { return left; }
028. //+----------------+
029.         C_TreeNode *GetRight(void) const { return right; }
030. //+----------------+
031. };
032. //+------------------------------------------------------------------+
033. class C_Tree
034. {
035.     private :
036.         C_TreeNode *root;
037. //+----------------+
038.         C_TreeNode *Insert(C_TreeNode *arg, C_TreeNode *ptr, int info)
039.         {
040.             if (ptr == NULL)
041.             {
042.                 ptr = new C_TreeNode;
043. 
044.                 (*ptr).SetInfo(info);
045.                 if (arg == NULL) return ptr;
046.                 if (info < (*arg).GetInfo()) (*arg).SetLeft(ptr);
047.                 else (*arg).SetRight(ptr);
048. 
049.                 return ptr;
050.             }
051.             if (info < (*ptr).GetInfo()) return Insert(ptr, (*ptr).GetLeft(), info);
052.             else return Insert(ptr, (*ptr).GetRight(), info);
053.         }
054. //+----------------+
055.         string inOrder(C_TreeNode *ptr)
056.         {
057.             static string sz0 = "In Order: ";
058. 
059.             if (ptr == NULL) return sz0;
060. 
061.             inOrder((*ptr).GetLeft());
062.             sz0 += (ptr != NULL ? StringFormat("%d  ", (*ptr).GetInfo()) : "");
063.             inOrder((*ptr).GetRight());
064. 
065.             return sz0;
066.         }
067. //+----------------+
068.         string preOrder(C_TreeNode *ptr)
069.         {
070.             static string sz0 = "Pre Order: ";
071. 
072.             if (ptr == NULL) return sz0;
073. 
074.             sz0 += (ptr != NULL ? StringFormat("%d  ", (*ptr).GetInfo()) : "");
075.             preOrder((*ptr).GetLeft());
076.             preOrder((*ptr).GetRight());
077. 
078.             return sz0;
079.         }
080. //+----------------+
081.         string postOrder(C_TreeNode *ptr)
082.         {
083.             static string sz0 = "Post Order: ";
084. 
085.             if (ptr == NULL) return sz0;
086. 
087.             postOrder((*ptr).GetLeft());
088.             postOrder((*ptr).GetRight());
089.             sz0 += (ptr != NULL ? StringFormat("%d  ", (*ptr).GetInfo()) : "");
090. 
091.             return sz0;
092.         }
093. //+----------------+
094.         void Destroy(C_TreeNode *ptr)
095.         {
096.             if (ptr == NULL) return;
097. 
098.             Destroy((*ptr).GetLeft());
099.             Destroy((*ptr).GetRight());
100. 
101.             delete ptr;
102.         }
103. //+----------------+
104.     public  :
105. //+----------------+
106.         C_Tree()
107.             :root(NULL)
108.         {}
109. //+----------------+
110.         ~C_Tree()
111.         {
112.             Destroy(root);
113.         }
114. //+----------------+
115.         void Store(int info)
116.         {
117.             if (root == NULL) root = Insert(root, root, info);
118.             else Insert(root, root, info);
119.         }
120. //+----------------+
121.         string In_Order(void)
122.         {
123.             return inOrder(root);
124.         }
125. //+----------------+
126.         string Pre_Order(void)
127.         {
128.             return preOrder(root);
129.         }
130. //+----------------+
131.         string Post_Order(void)
132.         {
133.             return postOrder(root);
134.         }
135. //+----------------+
136. };
137. //+------------------------------------------------------------------+
138. void OnStart(void)
139. {
140.     C_Tree Tree;
141. 
142.     Tree.Store(10);
143.     Tree.Store(-6);
144.     Tree.Store(47);
145.     Tree.Store(35);
146.     Tree.Store(85);
147. 
148.     Print(Tree.In_Order());
149.     Print(Tree.Pre_Order());
150.     Print(Tree.Post_Order());
151. }
152. //+------------------------------------------------------------------+

Código 05

Vaya, qué cosa tan disparatada nos estás enseñando a hacer. Siempre pensé que todo sería mucho más complicado y difícil. Pero, al ver cómo consigues hacerlo, comprendo que resulta mucho más fácil y sencillo de lo que imaginaba. Ahora sí estoy empezando a disfrutar de la programación en MQL5.

Mi querido lector, muchas veces las personas complican las cosas de forma completamente innecesaria. La programación es muy interesante y divertida. Sin embargo, a diferencia de lo que muchos podrían imaginar, un buen programador no es quien consigue escribir código complicado, sino quien, utilizando sus conocimientos y comprendiendo conceptos sencillos, puede crear cualquier tipo de solución a partir de algo que vio en otro momento de su vida. Y como estudia y practica constantemente, desarrolla una percepción más aguda de detalles que muchas veces pasarían inadvertidos.

Volvamos al código. Observa que en la línea 110 de este código 05 implementamos el destructor de la clase. Quiero mantener el código sencillo y fácil de entender. Por eso, seguiremos utilizando la recursividad para implementar este proceso. Debido a ello, el destructor llamará a otro procedimiento que se implementa en la línea 94. Observa que este procedimiento hace algo muy parecido a lo que hacía la función postOrder de la línea 81, pero con una diferencia: en la línea 89 obteníamos el valor almacenado en el nodo central, mientras que aquí, en el procedimiento de la línea 94, eliminaremos el nodo. Esto ocurre cuando se ejecuta la instrucción de la línea 101. Al ejecutar este código 05, obtendremos el resultado que se muestra en la imagen siguiente.

Imagen 02

Vaya, estás loco. Pero me gustó cómo explicaste y mostraste la forma de hacer las cosas. Sin embargo, tengo algunas dudas relacionadas con este código 05. La primera es la siguiente: observo que la función postOrder de la línea 81 se parece en varios aspectos al método Destroy implementado en la línea 94. La cuestión es: ¿no existe alguna forma de simplificar este código 05 para evitar la aparente duplicación que podemos observar en esos dos puntos?

Bien, mi querido lector, esta cuestión es interesante y, al mismo tiempo, algo intrigante. Dependiendo del programador y de cuánto le interese realizar determinados ajustes, el código podrá modificarse o mantenerse sin cambios para reducir estas duplicaciones. Normalmente, esto no se hace en la práctica, ya que la mayoría de las veces resulta completamente innecesario.

Sin embargo, como aquí el objetivo es didáctico, creo que conviene mostrar cómo puede modificarse este mismo código 05 para que su lógica quede menos fragmentada, por así decirlo. Para ello, debemos analizar algunos elementos del código y comprender muy bien su funcionamiento. Te dejo esta tarea como ejercicio para que te formes tu propia interpretación de lo que ocurre en el código. No obstante, mostraré una alternativa con algunas simplificaciones. Al introducir ciertos cambios en el código 05, podemos obtener un código similar al que se muestra a continuación.

001. //+------------------------------------------------------------------+
002. #property copyright "Daniel Jose"
003. //+------------------------------------------------------------------+
004. class C_TreeNode
005. {
006.     private :
007. //+----------------+
008.         int         info;
009.         C_TreeNode  *left,
010.                     *right;
011. //+----------------+
012.     public  :
013. //+----------------+
014.         C_TreeNode()
015.             :left(NULL),
016.             right(NULL)
017.         {}
018. //+----------------+
019.         void SetInfo(int arg) { info = arg; }
020. //+----------------+
021.         void SetLeft(C_TreeNode *ptr) { left = ptr; }
022. //+----------------+
023.         void SetRight(C_TreeNode *ptr) { right = ptr; }
024. //+----------------+
025.         int GetInfo(void) const { return info; }
026. //+----------------+
027.         C_TreeNode *GetLeft(void) const { return left; }
028. //+----------------+
029.         C_TreeNode *GetRight(void) const { return right; }
030. //+----------------+
031. };
032. //+------------------------------------------------------------------+
033. class C_Tree
034. {
035. //+----------------+
036.     #define def_InfoToString(A) (A != NULL ? StringFormat("%d ", (*A).GetInfo()) : "")
037. //+----------------+
038.     private :
039.         C_TreeNode *root;
040.         string      m_szInfo;
041. //+----------------+
042.         C_TreeNode *Insert(C_TreeNode *arg, C_TreeNode *ptr, int info)
043.         {
044.             if (ptr == NULL)
045.             {
046.                 ptr = new C_TreeNode;
047. 
048.                 (*ptr).SetInfo(info);
049.                 if (arg == NULL) return ptr;
050.                 if (info < (*arg).GetInfo()) (*arg).SetLeft(ptr);
051.                 else (*arg).SetRight(ptr);
052. 
053.                 return ptr;
054.             }
055.             if (info < (*ptr).GetInfo()) return Insert(ptr, (*ptr).GetLeft(), info);
056.             else return Insert(ptr, (*ptr).GetRight(), info);
057.         }
058. //+----------------+
059.         void inOrder(C_TreeNode *ptr)
060.         {
061.             if (ptr == NULL) return;
062. 
063.             inOrder((*ptr).GetLeft());
064.             m_szInfo += def_InfoToString(ptr);
065.             inOrder((*ptr).GetRight());
066.         }
067. //+----------------+
068.         void preOrder(C_TreeNode *ptr)
069.         {
070.             if (ptr == NULL) return;
071. 
072.             m_szInfo += def_InfoToString(ptr);
073.             preOrder((*ptr).GetLeft());
074.             preOrder((*ptr).GetRight());
075.         }
076. //+----------------+
077.         void postOrder(C_TreeNode *ptr)
078.         {
079.             if (ptr == NULL) return;
080. 
081.             postOrder((*ptr).GetLeft());
082.             postOrder((*ptr).GetRight());
083.             m_szInfo += def_InfoToString(ptr);
084.         }
085. //+----------------+
086.         void Destroy(C_TreeNode *ptr)
087.         {
088.             if (ptr == NULL) return;
089. 
090.             Destroy((*ptr).GetLeft());
091.             Destroy((*ptr).GetRight());
092. 
093.             delete ptr;
094.         }
095. //+----------------+
096.     public  :
097. //+----------------+
098.         C_Tree()
099.             :root(NULL)
100.         {}
101. //+----------------+
102.         ~C_Tree()
103.         {
104.             Destroy(root);
105.         }
106. //+----------------+
107.         void Store(int info)
108.         {
109.             if (root == NULL) root = Insert(root, root, info);
110.             else Insert(root, root, info);
111.         }
112. //+----------------+
113.         string In_Order(void)
114.         {
115.             m_szInfo = "In Order: ";
116.             inOrder(root);
117.             
118.             return m_szInfo;
119.         }
120. //+----------------+
121.         string Pre_Order(void)
122.         {
123.             m_szInfo = "Pre Order: ";
124.             preOrder(root);
125. 
126.             return m_szInfo;
127.         }
128. //+----------------+
129.         string Post_Order(void)
130.         {
131.             m_szInfo = "Post Order: ";
132.             postOrder(root);
133. 
134.             return m_szInfo;
135.         }
136. //+----------------+
137.     #undef def_InfoToString
138. //+----------------+
139. };
140. //+------------------------------------------------------------------+
141. void OnStart(void)
142. {
143.     C_Tree Tree;
144. 
145.     Tree.Store(10);
146.     Tree.Store(-6);
147.     Tree.Store(47);
148.     Tree.Store(35);
149.     Tree.Store(85);
150. 
151.     Print(Tree.In_Order());
152.     Print(Tree.Pre_Order());
153.     Print(Tree.Post_Order());
154. }
155. //+------------------------------------------------------------------+

Código 06

Observa que, en este código 06, solo he adaptado el código a una estructura algo más clara. Aun así, podemos mejorar otros aspectos. Con estos cambios obtenemos el código que se muestra a continuación.

001. //+------------------------------------------------------------------+
002. #property copyright "Daniel Jose"
003. //+------------------------------------------------------------------+
004. class C_TreeNode
005. {
006.     private :
007. //+----------------+
008.         int         info;
009.         C_TreeNode  *left,
010.                     *right;
011. //+----------------+
012.     public  :
013. //+----------------+
014.         C_TreeNode()
015.             :left(NULL),
016.             right(NULL)
017.         {}
018. //+----------------+
019.         void SetInfo(int arg) { info = arg; }
020. //+----------------+
021.         void SetLeft(C_TreeNode *ptr) { left = ptr; }
022. //+----------------+
023.         void SetRight(C_TreeNode *ptr) { right = ptr; }
024. //+----------------+
025.         int GetInfo(void) const { return info; }
026. //+----------------+
027.         C_TreeNode *GetLeft(void) const { return left; }
028. //+----------------+
029.         C_TreeNode *GetRight(void) const { return right; }
030. //+----------------+
031. };
032. //+------------------------------------------------------------------+
033. class C_Tree
034. {
035. //+----------------+
036.     #define def_InfoToString(A) (A != NULL ? StringFormat("%d ", (*A).GetInfo()) : "")
037.     enum E_SEQ {eInOrder, ePreOrder, ePostOrder, eDestroy};
038. //+----------------+
039.     private :
040.         C_TreeNode *root;
041.         string      m_szInfo;
042. //+----------------+
043.         C_TreeNode *Insert(C_TreeNode *arg, C_TreeNode *ptr, int info)
044.         {
045.             if (ptr == NULL)
046.             {
047.                 ptr = new C_TreeNode;
048. 
049.                 (*ptr).SetInfo(info);
050.                 if (arg == NULL) return ptr;
051.                 if (info < (*arg).GetInfo()) (*arg).SetLeft(ptr);
052.                 else (*arg).SetRight(ptr);
053. 
054.                 return ptr;
055.             }
056.             if (info < (*ptr).GetInfo()) return Insert(ptr, (*ptr).GetLeft(), info);
057.             else return Insert(ptr, (*ptr).GetRight(), info);
058.         }
059. //+----------------+
060.         void Seq(C_TreeNode *ptr, const E_SEQ type)
061.         {
062.             if (ptr == NULL) return;
063. 
064.             switch (type)
065.             {
066.                 case eInOrder   :
067.                 case ePostOrder :
068.                 case eDestroy   :
069.                     Seq((*ptr).GetLeft(), type);
070.                     if (type == eInOrder) break;
071.                     Seq((*ptr).GetRight(), type);
072.             }
073.             m_szInfo += def_InfoToString(ptr);
074.             switch (type)
075.             {
076.                 case ePreOrder  :
077.                     Seq((*ptr).GetLeft(), type);
078.                 case eInOrder   :
079.                     Seq((*ptr).GetRight(), type);
080.                     break;
081.                 case eDestroy   :
082.                     delete ptr;
083.             }
084.         }
085. //+----------------+
086.     public  :
087. //+----------------+
088.         C_Tree()
089.             :root(NULL)
090.         {}
091. //+----------------+
092.         ~C_Tree()
093.         {
094.             Seq(root, eDestroy);
095.         }
096. //+----------------+
097.         void Store(int info)
098.         {
099.             if (root == NULL) root = Insert(root, root, info);
100.             else Insert(root, root, info);
101.         }
102. //+----------------+
103.         string In_Order(void)
104.         {
105.             m_szInfo = "In Order: ";
106.             Seq(root, eInOrder);
107.             
108.             return m_szInfo;
109.         }
110. //+----------------+
111.         string Pre_Order(void)
112.         {
113.             m_szInfo = "Pre Order: ";
114.             Seq(root, ePreOrder);
115. 
116.             return m_szInfo;
117.         }
118. //+----------------+
119.         string Post_Order(void)
120.         {
121.             m_szInfo = "Post Order: ";
122.             Seq(root, ePostOrder);
123. 
124.             return m_szInfo;
125.         }
126. //+----------------+
127.     #undef def_InfoToString
128. //+----------------+
129. };
130. //+------------------------------------------------------------------+
131. void OnStart(void)
132. {
133.     C_Tree Tree;
134. 
135.     Tree.Store(10);
136.     Tree.Store(-6);
137.     Tree.Store(47);
138.     Tree.Store(35);
139.     Tree.Store(85);
140. 
141.     Print(Tree.In_Order());
142.     Print(Tree.Pre_Order());
143.     Print(Tree.Post_Order());
144. }
145. //+------------------------------------------------------------------+

Código 07

A mi parecer, este código 07 es mucho, pero mucho mejor que los anteriores. Esto se debe a que agrupa las operaciones de una manera que simplifica cualquier ajuste que pretendamos realizar. Cuatro operaciones que antes se realizaban en distintos puntos del código se han concentrado en uno solo: el método de la línea 60.

Existe otro detalle en este código 07 que explicaré en otro artículo, ya que en este momento no utilizamos ese concepto de forma directa ni explícita. Es muy importante comprender bien este concepto, pues quizá necesites utilizarlo explícitamente en alguno de tus futuros códigos. Pero, por ahora, dejaremos su explicación para otro momento.

Observa que mi propuesta de simplificación da como resultado un código mucho más sencillo. Sin embargo, tenemos aquí un pequeño problema o inconveniente. Si observaste los códigos relacionados con las colas y las listas, habrás notado que podíamos utilizar cualquier tipo de dato en ellas. Sin embargo, en el caso de los árboles, estamos limitados a utilizar únicamente tipos enteros. La pregunta es: ¿cómo podemos eliminar esta limitación? Muchos podrían decir o pensar que resolverla es muy sencillo. En teoría, sí, es fácil de resolver. Sin embargo, existe un pequeño problema. Para comprenderlo, centrémonos en el código 07.

Desde el principio, esta implementación se concibió como un árbol autoordenado. Dicho de una forma más clara, mi querido lector: a medida que se insertan nuevos valores en el árbol, estos se insertan a la derecha o a la izquierda del nodo según el valor que este almacena, tanto si ese nodo es la raíz como si es cualquier otro nodo. La línea 51 del código 07 es precisamente la encargada de gestionar este proceso. Presta atención a este sencillo detalle: si el valor de entrada es mayor o igual que el valor del nodo —sí, también puede ser igual—, se dirige hacia la derecha. Si es menor que el valor del nodo, se dirige hacia la izquierda. Este sencillo detalle marca una gran diferencia en el resultado final.

Por tanto, según el tipo de dato del elemento del árbol utilizado para determinar la dirección, quedamos condicionados por la propia implementación. Una forma de resolverlo sería indicar previamente qué dirección debe seguirse. También podríamos implementar un mecanismo de equilibrado automático para abordar esta cuestión. Sin embargo, todavía no quiero hacerlo, porque existen casos en los que NO QUEREMOS un árbol equilibrado.

AVISO IMPORTANTE: Normalmente, los árboles suelen funcionar mejor y ofrecer un mayor rendimiento cuando están correctamente equilibrados. Por tanto, es muy recomendable que SIEMPRE procures mantener el árbol lo más equilibrado posible para obtener el mejor rendimiento.

La cuestión del equilibrado se explicará más adelante. Por ahora, centrémonos en nuestro problema concreto. Como el árbol se ordena automáticamente gracias a la lógica implementada en la línea 51, en principio no podremos utilizar cualquier tipo de dato. Al menos por ahora, tendremos que limitarnos a los tipos de datos más sencillos.

Sin embargo, esta decisión no nos impide intentar generalizar un poco la implementación. Para conseguirlo, necesitaremos recurrir a un concepto explicado en otros artículos de esta misma serie: el uso de plantillas.

Muy bien, para ampliar nuestra implementación mediante plantillas, tendremos que modificar el código y adoptar un enfoque ligeramente distinto. De este modo, obtendremos un nuevo código basado en lo que vimos en el código 07. Puedes verlo íntegramente a continuación.

001. //+------------------------------------------------------------------+
002. #property copyright "Daniel Jose"
003. //+------------------------------------------------------------------+
004. template <typename T>
005. class C_TreeNode
006. {
007.     private :
008. //+----------------+
009.         T           info;
010.         C_TreeNode  *left,
011.                     *right;
012. //+----------------+
013.     public  :
014. //+----------------+
015.         C_TreeNode()
016.             :left(NULL),
017.             right(NULL)
018.         {}
019. //+----------------+
020.         void SetInfo(T arg) { info = arg; }
021. //+----------------+
022.         void SetLeft(C_TreeNode *ptr) { left = ptr; }
023. //+----------------+
024.         void SetRight(C_TreeNode *ptr) { right = ptr; }
025. //+----------------+
026.         T GetInfo(void) const { return info; }
027. //+----------------+
028.         C_TreeNode *GetLeft(void) const { return left; }
029. //+----------------+
030.         C_TreeNode *GetRight(void) const { return right; }
031. //+----------------+
032. };
033. //+------------------------------------------------------------------+
034. template <typename T>
035. class C_Tree
036. {
037. //+----------------+
038.     #define def_InfoToString(A) (A != NULL ? StringFormat("%d ", (*A).GetInfo()) : "")
039.     enum E_SEQ {eInOrder, ePreOrder, ePostOrder, eDestroy};
040. //+----------------+
041.     private :
042.         C_TreeNode <T> *root;
043.         string      m_szInfo;
044. //+----------------+
045.         C_TreeNode <T> *Insert(C_TreeNode <T> *arg, C_TreeNode <T> *ptr, T info)
046.         {
047.             if (ptr == NULL)
048.             {
049.                 ptr = new C_TreeNode <T>;
050. 
051.                 (*ptr).SetInfo(info);
052.                 if (arg == NULL) return ptr;
053.                 if (info < (*arg).GetInfo()) (*arg).SetLeft(ptr);
054.                 else (*arg).SetRight(ptr);
055. 
056.                 return ptr;
057.             }
058.             if (info < (*ptr).GetInfo()) return Insert(ptr, (*ptr).GetLeft(), info);
059.             else return Insert(ptr, (*ptr).GetRight(), info);
060.         }
061. //+----------------+
062.         void Seq(C_TreeNode <T> *ptr, const E_SEQ type)
063.         {
064.             if (ptr == NULL) return;
065. 
066.             switch (type)
067.             {
068.                 case eInOrder   :
069.                 case ePostOrder :
070.                 case eDestroy   :
071.                     Seq((*ptr).GetLeft(), type);
072.                     if (type == eInOrder) break;
073.                     Seq((*ptr).GetRight(), type);
074.             }
075.             m_szInfo += def_InfoToString(ptr);
076.             switch (type)
077.             {
078.                 case ePreOrder  :
079.                     Seq((*ptr).GetLeft(), type);
080.                 case eInOrder   :
081.                     Seq((*ptr).GetRight(), type);
082.                     break;
083.                 case eDestroy   :
084.                     delete ptr;
085.             }
086.         }
087. //+----------------+
088.     public  :
089. //+----------------+
090.         C_Tree()
091.             :root(NULL)
092.         {}
093. //+----------------+
094.         ~C_Tree()
095.         {
096.             Seq(root, eDestroy);
097.         }
098. //+----------------+
099.         void Store(T info)
100.         {
101.             if (root == NULL) root = Insert(root, root, info);
102.             else Insert(root, root, info);
103.         }
104. //+----------------+
105.         string In_Order(void)
106.         {
107.             m_szInfo = "In Order: ";
108.             Seq(root, eInOrder);
109.             
110.             return m_szInfo;
111.         }
112. //+----------------+
113.         string Pre_Order(void)
114.         {
115.             m_szInfo = "Pre Order: ";
116.             Seq(root, ePreOrder);
117. 
118.             return m_szInfo;
119.         }
120. //+----------------+
121.         string Post_Order(void)
122.         {
123.             m_szInfo = "Post Order: ";
124.             Seq(root, ePostOrder);
125. 
126.             return m_szInfo;
127.         }
128. //+----------------+
129.     #undef def_InfoToString
130. //+----------------+
131. };
132. //+------------------------------------------------------------------+
133. void OnStart(void)
134. {
135.     C_Tree <int> Tree;
136. 
137.     Tree.Store(10);
138.     Tree.Store(-6);
139.     Tree.Store(47);
140.     Tree.Store(35);
141.     Tree.Store(85);
142. 
143.     Print(Tree.In_Order());
144.     Print(Tree.Pre_Order());
145.     Print(Tree.Post_Order());
146. }
147. //+------------------------------------------------------------------+

Código 08

¡Por el amor de DIOS! ¡Santa Virgen María! ¿Qué es esto? Vaya, hasta la línea 32 conseguí entender el código. Pero, en cuanto llegamos a la parte donde íbamos a implementar la clase C_Tree, olvídalo. A partir de ahí no conseguí entender absolutamente nada. Así que, por favor, ayúdame a comprender algunas cosas. Primero déjame mostrarte lo que conseguí entender y después me explicas el resto. ¿De acuerdo?

Hasta donde pude entender, los elementos que almacenábamos en el árbol eran de tipo int. Por tanto, cuando añadiste la declaración de plantilla en la línea cuatro, simplemente fue necesario adaptar el código a este nuevo tipo. Por eso se realizaron los cambios en las líneas nueve, veinte y veintiséis. Hasta ahí, todo correcto; conseguí comprenderlo porque tiene pleno sentido. Sin embargo, cuando terminó esa parte y comenzamos a implementar el código de la clase C_Tree, dejé de entender el motivo de las modificaciones. A partir de ahí, todo se convirtió en un verdadero lío.

Bien, mi querido lector. En cierto modo, has conseguido comprender una parte de lo que fue necesario modificar en el código. Sin embargo, quizá no hayas entendido otra cuestión que también se abordó en este artículo. Durante la transición del código 02 al código 04 surgió la clase C_TreeNode, cuyas instancias representan los nodos y almacenan sus elementos. Un detalle importante: C_TreeNode no contiene el árbol; solo define cómo se vincula cada elemento con los demás dentro del árbol. Comprender esto es fundamental para entender la propia clase C_Tree. Ahora piensa un momento. Si C_TreeNode contiene los mecanismos que permiten crear el árbol y, al mismo tiempo, cada instancia almacena el elemento correspondiente a un nodo del árbol, ¿cómo podríamos indicarle qué tipo de elementos contendrá? Ten en cuenta que no accederemos directamente a C_TreeNode, sino a C_Tree, que es la clase que implementa el árbol.

Visto así, empieza a tener más sentido que C_Tree también deba ser una clase de plantilla, igual que C_TreeNode. Por esta razón, se añadió la línea 34 al código, convirtiendo C_Tree en una clase plantilla. Ahora viene la parte más sencilla y entretenida. Como C_Tree es una clase plantilla y necesita crear objetos C_TreeNode, que también deben utilizar el mismo tipo definido para C_Tree, lo más natural es parametrizar C_TreeNode con ese mismo tipo. Para hacerlo, modificamos la declaración de la raíz como se muestra en la línea 42.

De este modo, C_TreeNode quedará parametrizada con el mismo tipo definido para nuestro árbol. Pero esto no termina aquí. Como todos los elementos pueden ser de cualquier tipo, toda declaración dentro de la clase C_Tree que haga referencia a C_TreeNode deberá ajustarse. Por tanto, fue necesario editar el código de la clase C_Tree. Mi querido lector, quizá te resulten extrañas algunas líneas de esta clase. Sin embargo, para simplificarte las cosas y ayudarte a comprender mejor este código 08, podemos realizar un pequeño cambio. Este cambio se muestra a continuación.

001. //+------------------------------------------------------------------+
002. #property copyright "Daniel Jose"
003. //+------------------------------------------------------------------+
004. template <typename T>
005. class C_TreeNode
006. {
007.     private :
008. //+----------------+
009.         T           info;
010.         C_TreeNode  *left,
011.                     *right;
012. //+----------------+
013.     public  :
014. //+----------------+
015.         C_TreeNode()
016.             :left(NULL),
017.             right(NULL)
018.         {}
019. //+----------------+
020.         void SetInfo(T arg) { info = arg; }
021. //+----------------+
022.         void SetLeft(C_TreeNode *ptr) { left = ptr; }
023. //+----------------+
024.         void SetRight(C_TreeNode *ptr) { right = ptr; }
025. //+----------------+
026.         T GetInfo(void) const { return info; }
027. //+----------------+
028.         C_TreeNode *GetLeft(void) const { return left; }
029. //+----------------+
030.         C_TreeNode *GetRight(void) const { return right; }
031. //+----------------+
032. };
033. //+------------------------------------------------------------------+
034. #define C_TreeNode C_TreeNode<T>
035. template <typename T>
036. class C_Tree
037. {
038. //+----------------+
039.     #define def_InfoToString(A) (A != NULL ? StringFormat("%d ", (*A).GetInfo()) : "")
040.     enum E_SEQ {eInOrder, ePreOrder, ePostOrder, eDestroy};
041. //+----------------+
042.     private :
043.         C_TreeNode *root;
044.         string      m_szInfo;
045. //+----------------+
046.         C_TreeNode *Insert(C_TreeNode *arg, C_TreeNode *ptr, T info)
047.         {
048.             if (ptr == NULL)
049.             {
050.                 ptr = new C_TreeNode;
051. 
052.                 (*ptr).SetInfo(info);
053.                 if (arg == NULL) return ptr;
054.                 if (info < (*arg).GetInfo()) (*arg).SetLeft(ptr);
055.                 else (*arg).SetRight(ptr);
056. 
057.                 return ptr;
058.             }
059.             if (info < (*ptr).GetInfo()) return Insert(ptr, (*ptr).GetLeft(), info);
060.             else return Insert(ptr, (*ptr).GetRight(), info);
061.         }
062. //+----------------+
063.         void Seq(C_TreeNode *ptr, const E_SEQ type)
064.         {
065.             if (ptr == NULL) return;
066. 
067.             switch (type)
068.             {
069.                 case eInOrder   :
070.                 case ePostOrder :
071.                 case eDestroy   :
072.                     Seq((*ptr).GetLeft(), type);
073.                     if (type == eInOrder) break;
074.                     Seq((*ptr).GetRight(), type);
075.             }
076.             m_szInfo += def_InfoToString(ptr);
077.             switch (type)
078.             {
079.                 case ePreOrder  :
080.                     Seq((*ptr).GetLeft(), type);
081.                 case eInOrder   :
082.                     Seq((*ptr).GetRight(), type);
083.                     break;
084.                 case eDestroy   :
085.                     delete ptr;
086.             }
087.         }
088. //+----------------+
089.     public  :
090. //+----------------+
091.         C_Tree()
092.             :root(NULL)
093.         {}
094. //+----------------+
095.         ~C_Tree()
096.         {
097.             Seq(root, eDestroy);
098.         }
099. //+----------------+
100.         void Store(T info)
101.         {
102.             if (root == NULL) root = Insert(root, root, info);
103.             else Insert(root, root, info);
104.         }
105. //+----------------+
106.         string In_Order(void)
107.         {
108.             m_szInfo = "In Order: ";
109.             Seq(root, eInOrder);
110.             
111.             return m_szInfo;
112.         }
113. //+----------------+
114.         string Pre_Order(void)
115.         {
116.             m_szInfo = "Pre Order: ";
117.             Seq(root, ePreOrder);
118. 
119.             return m_szInfo;
120.         }
121. //+----------------+
122.         string Post_Order(void)
123.         {
124.             m_szInfo = "Post Order: ";
125.             Seq(root, ePostOrder);
126. 
127.             return m_szInfo;
128.         }
129. //+----------------+
130.     #undef def_InfoToString
131. //+----------------+
132. };
133. #undef C_TreeNode
134. //+------------------------------------------------------------------+
135. void OnStart(void)
136. {
137.     C_Tree <int> Tree;
138. 
139.     Tree.Store(10);
140.     Tree.Store(-6);
141.     Tree.Store(47);
142.     Tree.Store(35);
143.     Tree.Store(85);
144. 
145.     Print(Tree.In_Order());
146.     Print(Tree.Pre_Order());
147.     Print(Tree.Post_Order());
148. }
149. //+------------------------------------------------------------------+

Código 09

Observa ahora algo muy interesante. Si examinas la implementación de la clase C_Tree en este código 09 y la comparas con el código 07, notarás que son básicamente iguales. Ni más ni menos. Sin embargo, al comparar este código 09 con el código 08, verás que la clase C_Tree es diferente. Esto se debe precisamente a que, en este código 09, añadí una directiva del preprocesador en la línea 34. Esta directiva hará que se ajuste el código de la clase C_Tree, de modo que para el compilador, el código será equivalente al código 08, mientras que otro programador verá algo similar a lo mostrado en el código 07. Sencillamente magnífico.

De este modo, para utilizar cualquier tipo de dato, bastará con cambiar el tipo indicado en la línea 137. Así dispondremos de una gama mucho más amplia de posibilidades de uso para nuestra implementación de árbol. Recuerda que todavía debemos abordar la cuestión de la línea 54 del código 09, pero la trataremos con más detalle en el futuro.

Consideraciones finales

En este artículo hemos jugado y nos hemos divertido bastante mejorando nuestro código, cuyo objetivo es crear un árbol. Sin embargo, todavía no hemos terminado con el funcionamiento y la implementación de un árbol genérico. Tal vez ya estés completamente satisfecho con lo que hemos hecho aquí, pero aún debemos implementar algunas funcionalidades que existían en las implementaciones de colas y listas. Una de ellas es la posibilidad de eliminar elementos del árbol.

Explicar cómo hacerlo será el tema de nuestro próximo artículo. Por tanto, estudia y practica lo que hemos visto aquí, aprovechando al máximo los códigos incluidos en el anexo. El próximo tema será un hueso duro de roer, pero te mostraré lo divertido que puede resultar roerlo: eliminar elementos del árbol.

Archivo MQ5	Descripción
Code 01	Árbol simple
Code 02	Árbol simple
Code 03	Árbol simple
Code 04	Árbol simple
Code 05	Árbol simple
Code 06	Árbol simple
Code 07	Árbol simple
Code 08	Árbol simple