From Basic to Intermediate: Queues, Lists, and Trees (VI)

Introduction

In the previous article “From Basic to Intermediate: Classes (III)”, we concluded our introduction to the basic concepts of object-oriented programming and how it works. The purpose of explaining these concepts is to help you, dear reader, understand exactly what we will be implementing in the following articles. This is because we will return to discussing a topic that is both very important and very interesting—from both a practical and a theoretical perspective.

Well, without further ado, let's get back to the topic that really interests us. To do that, let's move on to the next part of the topic.

Queues, Lists, and Trees (VI)

In the most recent article on this topic, “From Basic to Intermediate: Queues, Lists, and Trees (V)”, we discussed the beginning of the implementation of a basic generic tree. However, we ran into a problem that could not be resolved without first explaining a few concepts. These concepts were discussed in the last three articles, the main purpose of which was to demonstrate and explain how class objects are created and destroyed.

Without this understanding of constructors and destructors, it is practically impossible to understand why both the code we have already written and the code we have yet to write will run without errors. However, if you try to modify this code—whether for educational purposes or to adapt it to other tasks—you may end up with code that still causes errors on shutdown.

To better understand what I am talking about, let's take a look at one of the code snippets from the aforementioned article. You can see it below:

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. //+------------------------------------------------------------------+

Code 01

This Code 01, which was explained in the article mentioned at the beginning of this topic, contains an error. In fact, it works correctly in terms of the results it produces. However, after it finishes running, a problem occurs, and MetaTrader 5 reports it as shown in the following image.

Image 01

The problem is precisely in the area marked in Image 01. "But wait a minute. Are you saying that there is an error in the code and that it is located in the highlighted area in Image 01 above? In my opinion, this is not exactly an error, but rather a warning that something is not being executed." In a sense, you are right, dear reader. However, that is not quite true.

What is marked in Image 01 is indeed an error, because we are allocating resources but not freeing them. In this case, the allocated resource is memory. However, to avoid the rapid degradation of this resource, MetaTrader 5 frees it in a somewhat forced manner, which creates additional computational load for the platform that could easily be avoided.

In simple processes, such as those we are discussing in these articles, such shortcomings can be tolerated, precisely because we are practicing and learning about the subject. However, their presence in an application that is considered complete or has a broader use is unacceptable, as this could compromise the integrity of the data being created or processed.

Therefore, to resolve the problem shown in Image 01, we need to draw on the knowledge and concepts presented in the last three articles, where we discussed classes. This is the only way we can implement the solution without any major difficulties or unnecessary complications and permanently resolve the problem shown in Image 01.

So, to start, we will make some changes to Code 01 to initialize the class data correctly. You can see the first changes in the following code:

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. //+------------------------------------------------------------------+

Code 02

Now note that the code, which used to be scattered throughout the file, is now contained within a class. This keeps the data protected, preventing unauthorized access that could compromise the integrity of the data stored in the tree we are creating.

However, despite this minor change, Code 02 will still produce the same message shown in Image 01. Nevertheless, dear reader, I would like you to pay attention to one detail. Compare the `Store` function from Code 01 with the same function from Code 02. As you can see, we no longer need to worry about initializing the `left` and `right` pointers inside the `Store` function. This is due to the class constructor, which is called on line 21 of Code 02, ensuring that the internal object members are initialized correctly. If this explanation is not entirely clear to you, please refer to the last three articles for more detailed information.

Great, we have already implemented the part related to the constructor. So, let's move on to the destructor. However, the logic of the tree destructor needs to be thought through very carefully, because depending on exactly how we want to destroy the tree, we will have to implement more or less code. However, since the goal here is purely educational, we will take a slightly simpler approach, even if that means modifying the current code.

First, we need to change part of the code because it is starting to look a little confusing. Trees themselves can already be quite confusing, depending on how we plan to use them. More experienced programmers might consider what I am about to do a waste of time. However, for those just starting out, this change could be the deciding factor in whether or not they understand the code we are about to implement. But if you already have some experience, I want you to take another look at Code 02 and answer completely honestly. Can you correctly understand what happens inside the OnStart function? Can you tell the difference between the `root` declaration on line 77, which represents a node, and the `Tree` declaration on line 78, which will contain a binary tree? If the answer is yes, great. However, many beginners will find it difficult to tell the difference. That is precisely why we should rethink the implementation using a slightly different approach.

First of all: if you really know what a tree is and what it is typically used for, then you know that we do NOT allow direct access to certain internal elements of the tree. One of these is precisely the tree root—that is, the variable declared on line 77 of Code 02. Although this kind of access is not an error in and of itself, it can lead to many problems, many of which will prevent the constructed tree from functioning properly and being used correctly. To avoid situations like these, which can often be quite problematic, we usually break the code down into smaller blocks. This makes both implementation and any future changes or improvements to the final code easier.

So, dear reader, let's take a step back and try a different approach to implementing the code for building the tree. You can see it below:

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. //+------------------------------------------------------------------+

Code 03

Now, take a moment to notice one detail. We have two classes: one is designed to represent each node in the tree and is implemented on line 4, and the other will build our tree and is implemented on line 29.

As a result, the implementation begins to follow a more appropriate structure, since we are no longer dependent on aspects that make implementation very difficult, and we gain more freedom and security. This is because we restrict access to only the information that is strictly necessary. Note that now, on line 32 inside the class that will implement the tree, we declare a variable to store the tree root. Therefore, within the OnStart function itself, we only need to declare a variable that will hold an instance of our tree, which eliminates the need to separately manage and maintain the tree root.

"Okay, so how do we now implement what was done in the previous code snippets?" Well, dear reader, this is the easiest and most exciting part of all our work. To reproduce the same behavior in our new code that Code 02 provided, we need to implement a few things. You will see that, in the end, it will turn out to be much simpler than what is implemented, for example, in Code 02. So, our next step is to implement what is shown below:

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. //+------------------------------------------------------------------+

Code 04

Since I forgot to implement one small detail in the C_TreeNode class in Code 03, here in Code 04 I am correcting that minor oversight. Now take a look at one detail in Code 04. This code behaves exactly the same way as the previous code examples. However, compare the code of the OnStart function in Code 04 with that in versions 01 and 02. Notice that the code has become much simpler here.

This does not mean that Code 04 has stopped working the way it did before. In other words, despite the changes made to simplify the use of the C_Tree class, Code 04 still relies internally on the same principles as before. In other words, the entire tree is still created completely recursively. Therefore, you can see that the private methods of the C_Tree class in Code 04 are very similar to what was done in Codes 01 and 02. That is precisely why we hardly need to go back and explain everything from the beginning, since the entire methodology has been preserved, but the available functions have become much easier to use.

However, despite the changes made to Code 04, we still have the same problem we encountered at the beginning of this article: the warnings highlighted in Image 01. Nevertheless, since Code 04 is now better implemented and has become much clearer, we can finally move on to the destructor of the C_Tree class. To do this, we only need to carefully examine the private methods of the C_Tree class. To delete—or, more precisely, to free—the allocated memory, we will have to do something very similar to what we do during tree traversal. Let's take a moment to think about this.

As you study the tree traversal functions, you will notice one interesting detail that is important to us. When we use the inOrder function shown on line 55, we call it to find the leftmost node. When we find it, we begin processing node values one node at a time. However, after traversing the left nodes, we begin traversing the right ones. In other words, we cannot delete the central node without making access to the nodes on the right more difficult.

As for the preOrder function, which is shown on line 68, the situation here is even more complicated. This is because we first visit the current—or central—node, and only then move on to the nodes to the left and right. Without a doubt, this complicates matters considerably. Remember that our goal is to delete the tree.

Well, we have one last option left: the postOrder function, which is shown on line 81. This function is actually very well suited for our task precisely because of the way it traverses the tree. Please note that we first look for nodes located deeper in the tree. Only after we reach them do we begin to visit the central node. This looks promising, because once this central node is no longer connected to any other node—neither to the left child nor to the right child—we will be able to delete it without any problems. Thus, we will be able to implement the class's destructor. All right, let's see how we can implement this code by applying the principle we just identified while observing how the already-implemented code works. The new code, which will now include a destructor, is shown below:

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. //+------------------------------------------------------------------+

Code 05

Wow, what a strange thing you are teaching us. I always thought it would be much harder. But seeing how you do it, I realize that it's much easier than I had imagined. Now I'm really starting to enjoy programming in MQL5.

Dear reader, people very often make things more complicated than they need to be. Programming is very interesting and exciting. However, contrary to what many might think, a good programmer is not someone who can write complex code, but someone who can use their knowledge and understanding of simple concepts to create virtually any solution based on something they once saw earlier in life. And since such a programmer is constantly learning and practicing, they develop a keener eye for details that would often go unnoticed.

Let's get back to the code. Please note that on line 110 of code 05, we implemented the class destructor. I want the code to remain simple and easy to understand. Therefore, we will continue to use recursion to implement this process. Therefore, the destructor will call another procedure implemented on line 94. Note that this procedure does almost the same thing as the postOrder function on line 81, with one difference: on line 89, we retrieved the value stored in the central node, whereas here, in the procedure on line 94, we will delete that node. This happens when the instruction on line 101 is executed. When we run code 05, we will get the result shown in the following image.

Image 02

"Well, you really are crazy. But I liked how you explained and demonstrated how it's all done. However, I have a few questions about code 05. My first question is this: I noticed that the postOrder function on line 81 resembles the Destroy method implemented on line 94 in several ways. My question is this: is there a way to simplify code 05 to avoid the apparent duplication we see in these two places?"

Well, this question is interesting and, at the same time, somewhat intriguing. Depending on the programmer and on how interested they are in making such changes, the code can either be reworked to reduce this duplication or left unchanged. As a rule, this is not done in practice, since in most cases it is completely unnecessary.

However, since the purpose here is educational, I think it is worth showing how we can modify this same code 05 so that its logic is, so to speak, less fragmented. To do this, we need to analyze some parts of the code and properly understand how they work. I am leaving this task for you as an exercise so that you can form your own understanding of what is happening in the code. Nevertheless, I will present an alternative approach with a few simplifications. By making certain changes to Code 05, we can obtain code similar to that shown below.

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. //+------------------------------------------------------------------+

Code 06

Please note that in Code 06, I have simply given the code a somewhat clearer structure. Nevertheless, we can improve other aspects as well. As a result of these changes, we get the code shown below:

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. //+------------------------------------------------------------------+

Code 07

In my opinion, Code 07 is much, much better than the previous versions. This is because the operations are grouped in it in a way that simplifies any changes we might want to make. Four operations that were previously performed in different parts of the code are now concentrated in one place: in the method on line 60.

There is one more detail in Code 07 that I will explain in another article, since we are not using this concept either directly or explicitly right now. It is very important to understand this concept well, since you may need to use it explicitly in one of your future code projects. But for now, we will save that explanation for another time.

Please note that the simplification I proposed results in much simpler code. However, this creates a small issue or inconvenience. If you looked at the code related to queues and lists, you probably noticed that it allowed data of any type to be used. However, in the case of trees, we are limited to using only integer types. The question is this: how can we remove this restriction? Many people might say or think that solving this problem is very easy. Theoretically, yes, it is easy to solve. However, there is one small problem. To understand this, let's focus on Code 07.

From the very beginning, this implementation was conceived as a self-ordering tree. To put it more simply, dear reader: as new values are inserted into the tree, they are placed to the right or left of a node depending on the value stored in that node, regardless of whether that node is the tree root or any other node. Line 51 of Code 07 is specifically responsible for this process. Note this simple detail: if the input value is greater than or equal to the node value—yes, it can even be equal to it—then it is placed to the right. If it is less than the node value, it is placed to the left. This small detail has a significant impact on the final result.

Thus, depending on the data type of the tree element used to determine the direction, we are limited by the implementation itself. One way to solve this problem is to specify in advance which direction to take. We could also implement an automatic balancing mechanism to address this issue. However, I do not want to do that just yet, because there are times when we DO NOT NEED a balanced tree.

IMPORTANT WARNING: As a general rule, trees work better and deliver higher performance when they are properly balanced. Therefore, to achieve maximum performance, it is strongly recommended that you ALWAYS try to keep the tree as balanced as possible.

The issue of balancing will be addressed later. For now, let's focus on our specific problem. Since the tree automatically orders itself thanks to the logic implemented in line 51, in principle, we will not be able to use just any data type. At least for now, we will have to stick to the simplest data types.

Nevertheless, this decision does not prevent us from trying to generalize the implementation a bit. To achieve this, we'll need to draw on a concept described in other articles in this series: the use of templates.

All right, to extend our implementation using templates, we'll have to modify the code and take a slightly different approach. This will give us new code based on what we saw in Code 07. You can see the full version below:

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. //+------------------------------------------------------------------+

Code 08

"For heaven's sake! What is this? Wow, I actually understood the code right up to line 32. But as soon as we got to the part where we had to implement the C_Tree class, that was it—forget about it. From that moment on, I couldn't understand a single thing. So, please help me figure some things out. First, let me show you what I've managed to figure out, and then please explain the rest to me. Is that a deal?

As far as I understand, the elements we stored in the tree were of type int. Therefore, when you added the template declaration on line 4, all you had to do was adapt the code to this new type. That is precisely why changes were made to lines 9, 20, and 26. Up to this point, everything is correct; I was able to understand it because it makes perfect sense. However, once that section was finished and we began implementing the code for the C_Tree class, I could no longer understand why those changes were necessary. From that moment on, everything turned into a real mess."

Well then, dear reader. In a way, you managed to figure out part of what needed to be changed in the code. However, you may not have fully understood another point that was also discussed in this article. During the transition from Code 02 to Code 04, the C_TreeNode class was introduced; its instances represent nodes and store their elements. An important detail: C_TreeNode does not contain the tree itself; it merely defines how each element is connected to the others within the tree. Understanding this is essential to understanding the C_Tree class itself. Now think about it for a moment. If C_TreeNode provides the mechanisms for creating a tree, and each instance stores an element corresponding to a node in the tree, how could we specify which elements it will contain? Keep in mind that we will not be working directly with C_TreeNode, but rather with C_Tree—the class that implements the tree.

When you look at it from this perspective, it becomes clearer why C_Tree should also be a template class, just like C_TreeNode. For this reason, line 34 was added to the code, turning C_Tree into a template class. And now comes the easiest and most exciting part. Since C_Tree is a template class and must create C_TreeNode objects, which must also use the same type as that defined for C_Tree, the most natural approach is to parameterize C_TreeNode with that same type. To do this, we will modify the tree root declaration, as shown in line 42.

Thus, C_TreeNode will be parameterized with the same type as our tree. But that is not all. Since all elements can be of any type, all declarations within the C_Tree class that refer to C_TreeNode must be adjusted accordingly. Therefore, it was necessary to edit the code for the C_Tree class. Dear reader, you may find some of the lines in this class a bit strange. However, to make things easier for you and help you better understand Code 08, we can make a small change. This change is shown below:

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. //+------------------------------------------------------------------+

Code 09

Now, take a look at something very interesting. If you look at the implementation of the C_Tree class in Code 09 and compare it to Code 07, you will notice that they are essentially the same. No more, no less. However, if you compare Code 09 with Code 08, you will see that the C_Tree class is different. This is precisely because I added a preprocessor directive on line 34 in Code 09. This directive will cause the code for the C_Tree class to be adjusted so that, to the compiler, it will be equivalent to the code in Code 08, while another programmer will see something similar to what is shown in Code 07. Simply magnificent.

Therefore, to use any data type, all you need to do is change the type specified on line 137. As a result, our tree implementation will have a much wider range of applications. Keep in mind that we still need to address the issue with line 54 of Code 09, but we will go into more detail on that later.

Concluding Thoughts

In this article, we experimented and had some fun refining our code for creating a tree. However, we have not finished working on and implementing the generic tree yet. You may already be completely satisfied with what we have done here, but we still have some features to implement that were included in the implementations of queues and lists. One of them is the ability to delete elements from the tree.

The topic of our next article is how to do this. So study and practice what we have covered here, making the most of the code provided in the appendix. The next topic will be a tough nut to crack, but I will show you just how fascinating it can be to figure it out: deleting elements from the tree.

MQ5 file	Description
Code 01	Simple Tree
Code 02	Simple Tree
Code 03	Simple Tree
Code 04	Simple Tree
Code 05	Simple Tree
Code 06	Simple Tree
Code 07	Simple Tree
Code 08	Simple Tree