Do básico ao intermediário: Filas, Listas e Árvores (VI)

Introdução

No artigo anterior Do básico ao intermediário: Classes (III), foi finalizado a demonstração dos conceitos básicos e iniciais sobre o que seria e como funcionaria a programação orientada em objetos. Tais conceitos demonstrados ali, tem como finalidade permitir que você, meu caro leitor, consiga compreender o que será implementado nos próximos artigos. Isto por conta que iremos retomar a explicação a respeito de um tema bastante importante e que ao mesmo tempo é muito interessante. Tanto pelo ponto de vista prático, quanto pelo ponto de vista teórico.

Ok, então sem mais delongas, vamos voltar ao assunto que realmente nos interessa. E para isto vamos a um novo tópico.

Filas, listas e árvores (VI)

No último artigo que tratamos a respeito deste tema, Do básico ao intermediário: Filas, Listas e Árvores (V), vimos como seria o início de uma implementação básica de uma árvore genérica. Porém, toda via e, entretanto, estávamos tendo um problema do qual, não seria possível corrigir sem que antes fosse feita uma explicação a respeito de algumas coisas. No caso tais coisas foram explicadas nos três últimos artigos, onde o foco principal, foi o de apresentar e demonstrar como uma classe seria construída e também destruída.

Isto por conta de que, sem este conhecimento sobre o que seriam os constructores e os destructores, é praticamente impossível compreender por que os códigos que estão e serão implementados ainda, de fato teria um funcionamento sem falhas. Mas se você fosse tentar modificar os mesmos, seja por motivos de estudos, seja por motivos de necessidade em se adaptar o código para outros propósitos. Poderia acabar ficando com um código que continuaria gerando erros, ao ser finalizado.

Para entender melhor o que estou querendo dizer, vamos rever um dos códigos vistos no artigo acima mencionado. Este pode ser observado logo abaixo.

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, que foi explicado no artigo mencionado no início deste tópico, contém uma falha. Na verdade, este código 01 funciona de maneira correta, no que diz respeito aos resultados produzidos pelo mesmo. Porém, quando ele é finalizado, ocorre um problema, que será reportado pelo MetaTrader 5, conforme pode ser visualizado na imagem logo abaixo.

Imagem 01

A falha em si, é justamente esta região que se encontra demarcada na imagem 01. Mas espere um pouco. Você está me dizendo que o código contém um erro? E que este erro é esta região demarcada na imagem 01, logo acima? Porém ao meu ver, isto não seria de fato um erro. Mas sim um alerta de que algo não está sendo feito. De certo modo você está correto sobre isto, meu caro leitor. Porém, não é bem assim.

Isto que está sendo marcado na imagem 01, é de fato um erro. Justamente por conta de que estamos alocando recursos e não os estamos devolvendo. No caso o recurso alocado, se trata justamente de memória. No entanto, para evitar uma rápida degradação deste recurso, o MetaTrader 5, a está liberando de maneira um tanto quanto forçada. O que impõem um certo esforço de processamento extra que a plataforma terá de fazer. Algo que pode ser perfeitamente evitado.

Durante processos simples, como o que estamos vendo nestes artigos, tais falhas, podem ser admitidas, devido justamente ao fato de que estamos praticando e estudando sobre algo. Porém, toda via e, entretanto, não é aceitável que tais falhas venham a existir em uma aplicação, dita já finalizada. Ou com um objetivo mais amplo de utilização. Visto que isto possa de fato vir a comprometer a integridade dos dados que estarão sendo gerados ou processados.

Assim sendo, para conseguir resolver este tipo de falha, que pode ser visualizada na imagem 01. Precisamos recorrer ao conhecimento, e aos conceitos vistos nos três últimos artigos, onde falamos sobre classes. Somente assim, poderemos implementar as coisas sem muitas dificuldades e sem sobressaltos. Corrigindo definitivamente o problema visto na imagem 01.

Ok, para começar vamos fazer algumas mudanças no código 01. Isto a fim de começar a promover a correta inicialização dos dados dentro da classe. Para isto, as primeiras mudanças podem ser vistas no código logo abaixo.

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

Agora perceba que o código que antes está disperso dentro do arquivo, agora está contido dentro de uma classe. Com isto, passamos a contar com a proteção dos dados a fim de evitar acesso indevido aos mesmos. Podendo assim comprometer a integridade da informação contida na árvore que estará sendo construída.

No entanto apesar desta pequena mudança que fizemos, este código 02, ainda assim irá produzir o mesmo tipo de resultado que é visto na imagem 01. Porém quero que você se atente a um fato aqui, meu caro leitor. Compare a função Store presente no código 01 com a mesma função presente no código 02. Você irá perceber que agora já não estamos nos preocupando com o fato de que os ponteiros left e right, precisarão ser inicializados na função Store. Isto justamente por conta do constructor da classe, que será acessado na linha 21 do código 02. Garantindo assim a correta e perfeita inicialização dos valores internos da classe. Se você não está entendendo o que está sendo explicado, veja os três últimos artigos para mais detalhes.

Muito bem, então já temos a fase do constructor sendo implementada. Portanto já podemos pensar na fase do destructor. Porém o destructor para uma árvore, precisa trabalhar de uma maneira um tanto quanto bem pensada. Isto por que, dependendo da forma como queremos e iremos destruir a árvore. Precisaremos de mais ou menos código sendo implementado. No entanto, devido ao fato de que, o objetivo aqui é pura e simplesmente a didática, iremos trabalhar em um caminho um tanto quanto mais simples, apesar de isto nos forçar a mudar o código que está sendo implementado.

Para começar, precisamos mudar uma coisa no código. Isto porque ele começa a ficar um tanto quanto confuso. E árvores por si só já podem vir a ser bastante confusas, dependendo de como estamos planejando as utilizar. Programadores com mais experiência, talvez achem o que irei fazer, pura perda de tempo. No entanto, para programadores iniciantes, o que será feito, pode ser a diferença entre conseguir ou não entender o código que estará sendo implementado. Mas para quem já tem alguma experiência, quero que você olhe novamente este código 02, e responda com toda a sinceridade. Você consegue entender de maneira adequada o que está sendo feito dentro do procedimento OnStart? Consegue separar o fato de que a declaração root, feita na linha 77 indica um node, e que a declaração Tree, feita na linha 78, é que irá conter a árvore binária? Se a resposta é sim, ok. Porém, muitos iniciantes terão dificuldade em fazer esta separação. Justamente devido a isto, precisamos modelar as coisas utilizando uma abordagem um pouco diferente.

Para começar, se você realmente, sabe o que é uma árvore e a que tipo de proposito ela normalmente é destinada. Sabe muito bem, que NÃO permitimos um acesso direto a certas características presentes dentro de uma árvore. Uma destas características é justamente a raiz da mesma, ou seja, a variável declarada na linha 77 do código 02. Permitir isto, apesar de não ser um erro, pode provocar uma série enorme de problemas. Sendo a maior parte deles, responsáveis por impedir o correto funcionamento e utilização da árvore construída. Para evitar justamente este tipo de situação, que muitas das vezes é um tanto quanto constrangedora. Normalmente separamos as coisas em blocos um pouco menores. Isto a fim de facilitar tanto a implementação, quanto também possíveis modificações e melhorias no código final.

Sendo assim, meu caro leitor, vamos dar um passo para trás. E começar a implementar o código para construir a árvore de uma outra maneira. Esta pode ser vista logo abaixo.

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

Agora preste atenção a uma coisa aqui meu caro leitor. Agora temos duas classes sendo construídas. Uma com o objetivo de armazenar cada node da árvore, sendo esta implementada na linha quatro. E outra, que irá de fato construir a nossa árvore. Sendo esta implementada na linha 29.

Fazendo assim, agora começamos a ter um direcionamento um pouco melhor. Isto por que, não ficamos presos a questões que dificultam imensamente o trabalho de implementação. E também nos dá um maior grau de liberdade e segurança na própria implementação. Isto por conta de que limitamos o acesso as informações que realmente precisam ser acessadas. Veja que agora, na linha 32, dentro da classe que irá implementar a tal árvore, indicamos uma variável para conter o node raiz. Com isto, agora dentro do próprio procedimento OnStart, apenas precisamos declarar uma variável que irá ser a nossa árvore, nos liberando do fardo de precisar controlar e manter o node raiz.

Ok, mas então como será feita agora a implementação do que foi feito dentro dos códigos anteriores? Bem meu caro leitor, está agora é a parte divertida e fácil de todo o nosso trabalho. Para voltarmos a ter o mesmo tipo de comportamento que era implementado pelo código 02. E isto agora dentro do que será o nosso novo código. Precisamos criar algumas coisas. Mas você irá ver que no final as coisas serão bem mais simples do que estava sendo feito, por exemplo no código 02. Assim sendo, o nosso próximo passo é implementar o que é mostrado logo abaixo.

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 eu a via me esquecido de implementar um pequeno detalhe na classe C_TreeNode no código 03. Aqui no código 04, estou corrigindo aquela pequena falha minha. Agora preste atenção a uma coisa aqui, neste código 04. Este mesmo código, tem um comportamento idêntico ao que era feito antes. No entanto, compare o código presente no procedimento OnStart, visto neste código 04, com o que era visto nos códigos 01 e 02. Note que aqui no código 04, as coisas são muito mais simples.

No entanto, isto não quer dizer que o código 04, deixou de trabalhar como era feito anteriormente. Isto é, mesmo com as modificações feitas no código, a fim de tornar o uso da classe C_Tree, mais simples. Internamente o código 04, continua utilizando os mesmos princípios que eram adotados anteriormente. Ou seja, toda a árvore continua sendo criada de forma totalmente recursiva. Por conta disto, você pode observar que as funções privativas dentro da classe C_Tree, vista neste código 04, se parecem em muito com o que era feito, nos códigos 01 e 02. Devido justamente a isto, praticamente não precisamos retomar a explicação desde o início. Já que toda a metodologia, foi mantida, porém com um aspecto muito mais agradável, no momento de se utilizar as funções presentes ali.

Porém, apesar do que foi feito no código 04, ainda assim, continuamos tendo o mesmo problema que nos assolava no início deste artigo. Que é justamente as informações destacadas na imagem 01. Mas devido justamente ao fato de que o código 01, se encontra melhor implementado. Facilitando assim, em muito o entendimento do mesmo. Podemos finalmente trabalhar na questão do destructor da classe C_Tree. Para fazer isto, precisamos apenas observar atentamente as funções privativas da classe C_Tree. Isto por que, para conseguir remover, ou melhor dizendo, devolver a memória alocada, precisaremos efetuar algo muito parecido como o que é feito a fim de ler a árvore. Então vamos pensar um pouco.

Se você observar as funções de leitura da árvore, irá notar um fato interessante. Porém importante para nós. Quando usamos a função inOrder, que pode ser vista na linha 55. Temos uma chamada a fim de procurar o node o mais à esquerda possível. Quando este node é encontrado começamos a ler os valores. Um node de cada vez. No entanto, depois de ter lido os nodes a esquerda, iremos começar a varrer os nodes a direita. Ou seja, não podemos destruir o node central, sem que isto torne complexo acessar os nodes a direita.

Com relação a função preOrder, vista na linha 68, temos uma situação ainda mais complicada. Isto por conta de que primeiro iremos ver o node atual, ou central, para somente depois acessar os nodes da esquerda e da direita. Definitivamente isto complica muito as coisas. Lembrando que o objetivo aqui é destruir a árvore.

Ok, então nos restou uma última tentativa. Que seria justamente o de tentar a função postOrder, que pode ser vista na linha 81. Esta função sim, é bem interessante para nosso objetivo. Isto devido justamente a forma como a árvore é varrida. Note que iremos buscar na árvore as posições mais profundas na mesma. Somente quando estas posições são alcançadas é que começaremos a ver o node central. Hum, isto parece promissor. Já que uma vez que este node central, não estará ligado a nenhum outro, seja à esquerda, seja à direita. Podemos simplesmente deletar este node sem nenhum problema. Tornando assim possível a confecção do destructor da classe. Muito bem, então vejamos como o código poderia ser feito, fazendo uso deste princípio que acabamos de notar, apenas observando o que já havia sido implementado no código. Este novo código, que agora irá possuir o destructor, pode ser observado logo abaixo.

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

Rapaz, que coisa mais maluca esta, que você está nos mostrando como fazer. Sempre achei que as coisas seriam muito mais complicadas e difíceis de serem feitas. Mas vendo você mostrar como as consegue fazer, percebo que tudo é bem mais fácil e simples do que eu imaginava. Agora sim, estou começando a tomar gosto pela programação MQL5.

De fato, meu caro leitor, muitas das vezes, as pessoas complicam as coisas de maneira completamente desnecessária. Programação é algo bem interessante e muito divertido. Porém, diferente do que muitos podem imaginar, um bom programador, não é aquele que consegue escrever códigos complicados. Mas sim aquele que consegue, fazendo uso de conhecimento e entendendo conceitos simples. Criar qualquer tipo de solução, com base em algo que ele viu em outro momento de sua vida. E como ele está sempre estudando e praticando. Consegue ter uma visão mais apurada de coisas que muitas das vezes passaria despercebidas.

Mas vamos voltar ao código. Você pode notar que na linha 110 deste código 05, estamos implementando o destructor da classe. Porém, toda via e, entretanto, quero manter o fato de que o código seja simples e fácil de entender. Assim continuaremos a utilizar a recursividade para nos ajudar a implementar as coisas. Portanto e por este motivo, este destructor, irá chamar um outro procedimento. Este é implementado na linha 94. Agora observe que este procedimento estará fazendo algo muito parecido com o que era efetuado na função postOrder, vista na linha 81. Com um detalhe, diferente do que acontecia na linha 89, onde capturávamos o valor presente no node central. Aqui no procedimento da linha 94, iremos deletar o node. Isto é efetuado quando a linha 101 for executada. Com isto, ao executarmos este código 05, teremos como resposta o que é visto na imagem logo abaixo.

Imagem 02

Cara, você é muito doido. Mas gostei da forma como você explicou e mostrou como as coisas podem ser feitas. Porém estou com algumas dúvidas relacionadas a este código 05. A primeira delas é a seguinte: Estou percebendo que a função postOrder, presente na linha 81, se parece em diversos aspectos com o procedimento Destroy, que é implementado na linha 94. A questão é: Será que não existe alguma forma de simplificarmos este código 05, a fim de não ter uma aparente duplicidade, como podemos notar nestes dois pontos mencionados?

Bem, meu caro leitor, de fato esta questão é algo interessante e ao mesmo tempo um tanto quanto intrigante. Isto por conta que dependendo do programador, ou do quanto ele esteja de fato interessado em fazer certas coisas. Podemos ou não ter uma mudança no código a fim de reduzir um pouco estes pontos duplicados. Normalmente isto na prática de fato não ocorre, já que na maior parte das vezes fazer isto é algo completamente desnecessário.

Porém, como aqui o objetivo é de fato a didática, acredito ser algo valido, mostrar como este mesmo código 05, pode ser modificado a fim de o tornar menos disperso, por assim dizer. Para fazer isto, precisamos analisar algumas coisas que estão presentes no código, e compreender muito bem como o mesmo funciona. Isto é uma tarefa que deixo como lição de casa, para que cada um gere a sua própria interpretação do que está acontecendo no código. Porém, irei mostrar uma alternativa, com algumas simplificações. E ao implementar algumas mudanças no código 05, poderemos gerar algo parecido como o código visto logo abaixo.

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

Observe que neste código 06, apenas adaptei o código a um formato um pouco mais agradável. Porém, ainda assim podemos melhorar algumas outras questões. E tais mudanças, podem ser feitas de forma a conseguir o código visto logo na sequência.

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

Ao meu ver, este código 07 é muito, mais muito melhor do que os anteriores. Isto por conta de que este código 07, está definitivamente agrupando as coisas de uma forma a tornar simples qualquer ajuste que venhamos a pretender implementar. Visto justamente por conta do fato de que, quatro operações que antes eram feitas em pontos diferentes do código, foram concentradas em um único ponto. Que no caso é o procedimento presente na linha 60.

Existe um outro detalhe neste código 07, no qual irei explicar em um outro artigo. Já que neste momento, não estamos fazendo uso direto, ou de maneira explicita, de tal conceito. Que de certa maneira é muito importante que seja bem compreendido, já que pode ser que você venha a precisar utiliza-lo de maneira explicita em algum de seus códigos futuros. Mas por hora, vamos deixar isto para ser explicado em outro momento.

Então, veja que na minha proposta de resumo do código, temos algo realmente bem mais simples. No entanto, temos um pequeno problema, ou inconveniente aqui. Se você observou os códigos referentes a filas e listas, deve ter notado que poderíamos utilizar qualquer tipo de dado dentro das filas e listas. No entanto, aqui para as árvores, estamos limitados a poder utilizar apenas e tão somente tipos inteiros. A pergunta é: Como podemos resolver esta dependência? Muitos podem dizer, ou imaginar que resolver isto é algo muito simples. Bem, em tese sim, é algo simples de ser resolvido. No entanto, existe um pequeno problema. E para entender o problema, vamos focar no código 07.

Desde o início, esta implementação de árvore foi pensada e imaginada para ser uma árvore auto ordenada. Ou para que fique mais claro em sua mente, meu caro leitor. Conforme novos valores fossem sendo inseridos na árvore, eles iriam ficar à direita ou a esquerda do valor presente no node. Fosse este node a raiz da árvore, fosse este node, um outro elemento qualquer. Porém a parte responsável por administrar isto é justamente a linha 51 no código 07. Preste atenção a este simples fato. Se o valor de entrada é maior ou igual, e sim ele pode ser igual, que o valor no node, o valor de entrada será direcionado para a direita. Se este mesmo valor for menor que o valor no node ele será direcionado para a esquerda. Este simples detalhe faz toda a diferença no final das contas.

Então dependendo do tipo de informação, contida no elemento da árvore, e que será usada para dizer a direção a ser tomada. Ficamos reféns da própria implementação. Existe uma forma de corrigir isto, que seria dizer previamente qual a direção a ser seguida. Assim, como também podemos adicionar uma implementação de auto balanceamento, a fim de corrigir esta questão. Porém ainda não quero fazer isto. Já que existem casos, em que NÃO QUEREMOS uma árvore balanceada.

AVISO IMPORTANTE: Normalmente árvores são melhor utilizadas, ou tem um desempenho melhor, quando estão devidamente balanceadas. Portanto, é bastante prudente que você, SEMPRE procure deixar a árvore, o mais balanceada possível. Isto para ter o melhor desempenho possível.

Esta questão do balanceamento será explicada depois. Por hora vamos focar no nosso problema em particular. E como nossa árvore está sendo auto ordenada, graças à está linha 51. Não poderemos, a princípio, fazer uso de qualquer tipo de dado. Precisaremos, pelo menos por hora, ficar apenas nos tipos mais simples de dados.

Mas o fato de tomarmos esta decisão, não nos impede de tentar generalizar um pouco as coisas. E para criar tal generalização, precisaremos recorrer a um conhecimento e conceito explicado em outros artigos, aqui nesta mesma sequência. O conceito do qual me refiro é justamente o de templates.

Muito bem, assim sendo, para que possamos ampliar e aplicar templates na nossa implementação. Precisaremos modificar o código para algo um pouco diferente. Assim, um novo código irá surgir, com base no que foi visto no código 07. E ele é mostrado na íntegra logo abaixo.

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

Pelo amor de DEUS. Minha virgem santa Maria. O que é isto? Cara, até a linha 32 eu consegui entender o código. Mas uma vez que entrou na parte onde iriamos implementar a classe C_Tree. Esquece. Daí em diante, não consegui entender absolutamente nada. Então por favor, me ajude a entender algumas coisas aqui. Primeiro deixe-me lhe mostrar o que consegui entender. Depois você explica o resto. Ok?

Até onde consegui entender, os elementos que estaremos gravando na árvore, eram do tipo int. Então quando você adicionou o template ao código, e isto na linha quatro. Simplesmente, foi preciso adaptar o código a este novo tipo. Devido a isto, foram feitas as mudanças nas linhas nove, vinte e vinte seis. Até aí tudo certo e consegui compreender. Já que de fato faz total sentido. Porém quando terminou esta parte, e entramos na parte onde começa a ser implementado o código da classe C_Tree. Passei a não entender o motivo das modificações. E daí ficou tudo uma verdadeira bagunça.

Ok, meu caro leitor. De certa maneira, você conseguiu entender uma parte do que precisou ser modificado no código. No entanto, você talvez não entendeu uma outra questão, que também foi abordada neste artigo. Quando saímos do código 02 para o código 04, tivemos um momento de transição entre eles. Tal momento, fez surgir o que seria a classe C_TreeNode. Que é justamente a responsável por armazenar os elementos dentro da árvore. Detalhe, C_TreeNode não contém a árvore, ela apenas diz como cada elemento se liga a outros dentro da árvore. Entender isto é importante para entender a própria classe C_Tree. Agora pense um pouco. Se C_TreeNode contém os mecanismos que permitem criar a árvore, ao mesmo tempo que irá armazenar os elementos em um node da árvore. Como poderíamos dizer a C_TreeNode, que tipo de elementos ela irá conter? Isto sabendo que não teremos acesso direto a C_TreeNode, mas sim a C_Tree, que é a classe que de fato implementa a árvore.

Bem, pensando assim, agora começa a fazer um pouco mais de sentido, o fato de que C_Tree, também precisa ser uma classe template. Assim como está ocorrendo com C_TreeNode. Por conta disto foi adicionada a linha 34 ao código. Tornando assim C_Tree em uma classe template. Agora vem a parte divertida e fácil de entender. Como C_Tree é uma classe template, e ela precisa criar elementos, dentro da classe C_TreeNode, que também seguirão o mesmo tipo que esteja definido para a classe C_Tree. Nada mais natural do que permitir a transferência de tipo para a classe C_TreeNode. E para conseguir fazer isto, mudamos a declaração da raiz, para o que pode ser visto na linha 42.

Desta forma agora, a própria classe C_TreeNode, será definida com base no que vier a ser criado para ser a nossa árvore. Porém não para por aí. Note que como todos os elementos podem vir a ser de qualquer tipo. Toda e qualquer declaração dentro da classe C_Tree, que vier a fazer referência a classe C_TreeNode, precisará sofre algum tipo de ajuste. Desta forma para ajustar adequadamente as coisas, o código da classe C_Tree, teve que passar por alguma edição. Por conta disto que você, meu caro leitor, pode estar estranhando algumas linhas dentro da classe C_Tree. Mas para simplificar a sua vida, e talvez lhe ajudar a entender melhor este mesmo código 08, podemos efetuar uma simples mudança no mesmo. Esta é mostrada logo abaixo.

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

Observe agora que coisa mais interessante. Olhando a própria implementação da classe C_Tree, este código 09. E o comparando com o código 07, você nota que é basicamente a mesma coisa. Sem mais nem menos. Porém, comparando este código 09, com o código 08, você nota que a classe C_Tree, está diferente. Mas isto se deve justamente ao fato de que neste código 09, adicionei uma diretiva de compilação na linha 34. Esta diretiva irá fazer com que o código dentro da classe C_Tree seja corrigido de modo que para o compilador, teremos o que é visto no código 08. Porém para um outro programador, teremos algo parecido com o que foi visto no código 07. Simplesmente magnifico.

Com isto, para que possamos vir a utilizar qualquer tipo de dado, bastará mudar o tipo indicado na linha 137. Desta forma, passamos a ter uma gama muito maior de possibilidades de uso da nossa implementação de árvore. Lembrando que ainda temos a questão da linha 54, vista no código 09. Mas isto será melhor trabalhado no futuro.

Considerações finais

Neste artigo, brincamos e nos divertimos bastante melhorando o nosso código, cujo objetivo seria justamente o de criar uma árvore. Porém, ainda não terminamos com esta questão referente ao que tange o funcionamento e implementação de uma árvore genérica. Talvez você, já esteja todo satisfeito com o que está sendo feito aqui. Porém, ainda falta implementar algumas coisas, que existiam no sistema de fila e listas. Uma delas é o de deletar elementos dentro da árvore.

Porém explicar como isto é feito, será o tema para o nosso próximo artigo. Então procure estudar e praticar o que foi visto aqui, fazendo o melhor uso possível dos códigos presentes no anexo. Pois o próximo tema a ser tratado é osso duro de roer. Mas irei lhe mostrar como pode vir a ser divertido ficar roendo este osso, que é o de deletar elementos da árvore.

Arquivo MQ5	Descrição
Code 01	Árvore simples
Code 02	Árvore simples
Code 03	Árvore simples
Code 04	Árvore simples
Code 05	Árvore simples
Code 06	Árvore simples
Code 07	Árvore simples
Code 08	Árvore simples