От начального до среднего уровня: Очереди, списки и деревья (VI)

Введение

В предыдущей статье «От начального к среднему: Классы (III)» мы завершили изложение основных вводных понятий о том, что такое объектно-ориентированное программирование и как оно работает. Цель изложения этих понятий состоит в том, чтобы вы, уважаемый читатель, поняли, что именно мы будем реализовывать в следующих статьях. Это связано с тем, что мы вернёмся к объяснению одной очень важной и в то же время очень интересной темы — как с практической, так и с теоретической точки зрения.

Что ж, без лишних предисловий вернёмся к теме, которая нас действительно интересует. Для этого давайте перейдём к новой теме.

Очереди, списки и деревья (VI)

В последней статье, посвящённой этой теме, «От начального к среднему: очереди, списки и деревья (V)», мы рассмотрели начало реализации базового обобщённого дерева. Однако мы столкнулись с проблемой, которую нельзя было исправить, не объяснив предварительно некоторые понятия. Эти понятия рассматривались в трёх последних статьях, основная цель которых состояла в том, чтобы показать и объяснить, как создаются и уничтожаются объекты класса.

Без этих знаний о конструкторах и деструкторах практически невозможно понять, почему и уже реализованный код, и тот, который нам ещё предстоит реализовать, будут работать без ошибок. Однако если вы попытаетесь изменить этот код — будь то в учебных целях или для адаптации к другим задачам, — вы можете получить код, который по-прежнему будет вызывать ошибки при завершении работы.

Чтобы лучше понять, о чём я говорю, давайте рассмотрим один из кодов, приведённых в упомянутой статье. Вы можете увидеть его ниже:

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

Код 01

Этот код 01, который объяснили в статье, упомянутой в начале этой темы, содержит ошибку. На самом деле он работает правильно с точки зрения получаемых результатов. Однако по завершении его работы возникает проблема, о которой сообщает MetaTrader 5, как показано на следующем изображении.

Изображение 01

Проблема находится именно в области, отмеченной на изображении 01. "Но подожди минутку. Вы хотите сказать, что в коде есть ошибка и что она находится в выделенной области на изображении 01 выше? На мой взгляд, это не совсем ошибка, а скорее предупреждение о том, что что-то не выполняется". В некотором смысле вы правы, уважаемый читатель. Однако это не совсем так.

То, что отмечено на изображении 01, действительно является ошибкой, поскольку мы выделяем ресурсы, но не освобождаем их. В данном случае выделенным ресурсом является память. Однако, чтобы избежать быстрой деградации этого ресурса, MetaTrader 5 освобождает его несколько принудительным образом, что создаёт для платформы дополнительную вычислительную нагрузку, которой вполне можно избежать.

В простых процессах, подобных тем, которые мы рассматриваем в этих статьях, подобные недочёты можно терпеть, именно потому, что мы практикуемся и изучаем тему. Однако их наличие в приложении, которое считается завершённым или имеет более широкую сферу применения, недопустимо, поскольку это может поставить под угрозу целостность создаваемых или обрабатываемых данных.

Поэтому, чтобы устранить проблему, которую можно увидеть на изображении 01, нам нужно обратиться к знаниям и понятиям, представленным в трёх последних статьях, где мы говорили о классах. Только так мы сможем реализовать решение без особых трудностей и лишних осложнений и окончательно устранить проблему, показанную на изображении 01.

Итак, для начала мы внесём некоторые изменения в код 01, чтобы правильно инициализировать данные класса. Первые изменения можно увидеть в следующем коде:

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

Код 02

Теперь обратите внимание, что код, который раньше был разбросан по всему файлу, теперь заключён в класс. Таким образом, данные остаются защищёнными, что предотвращает несанкционированный доступ, который мог бы поставить под угрозу целостность данных, хранящихся в создаваемом нами дереве.

Однако, несмотря на это небольшое изменение, код 02 по-прежнему будет приводить к тому же сообщению, что показан на изображении 01. Тем не менее, уважаемый читатель, я хочу, чтобы вы обратили внимание на одну деталь. Сравни функцию Store из кода 01 с той же функцией из кода 02. Как видите, теперь нам больше не нужно беспокоиться об инициализации указателей `left` и `right` внутри функции `Store`. Это связано с конструктором класса, который вызывается в строке 21 кода 02, что гарантирует правильную инициализацию внутренних членов объекта. Если вам не совсем понятно это объяснение, обратитесь к трём последним статьям за более подробной информацией.

Отлично, мы уже реализовали часть, связанную с конструктором. Итак, мы можем перейти к деструктору. Однако логику деструктора дерева нужно продумать очень тщательно, поскольку в зависимости от того, как именно мы хотим уничтожить дерево, нам придётся реализовать больше или меньше кода. Тем не менее, поскольку здесь цель чисто учебная, мы будем использовать несколько более простой подход, даже если для этого придётся изменить текущий код.

Для начала нам нужно изменить часть кода, потому что он начинает выглядеть несколько запутанно. Сами по себе деревья уже могут быть довольно запутанными — в зависимости от того, как мы собираемся их использовать. Более опытные программисты, возможно, сочтут то, что я собираюсь сделать, пустой тратой времени. Однако для тех, кто только начинает, это изменение может стать решающим фактором в том, поймут они или нет код, который мы собираемся реализовать. Но если у вас уже есть некоторый опыт, я хочу, чтобы вы ещё раз посмотрели на этот код 02 и ответили совершенно честно. Можете ли вы правильно понять, что делается внутри функции OnStart? Можете ли вы провести различие между объявлением `root` в строке 77, которое представляет узел, и объявлением `Tree` в строке 78, которое будет содержать бинарное дерево? Если ответ утвердительный, отлично. Однако многим новичкам будет трудно провести это различие. Именно поэтому нам следует переосмыслить реализацию, используя немного иной подход.

Для начала: если вы действительно знаете, что такое дерево и для чего оно обычно используется, то знаете, что мы НЕ допускаем прямого доступа к определённым внутренним элементам дерева. Одним из них является как раз корень дерева, то есть переменная, объявленная в строке 77 кода 02. Хотя сам по себе такой доступ не является ошибкой, он может привести к множеству проблем, многие из которых не позволят построенному дереву правильно работать и корректно использоваться. Чтобы избежать подобных ситуаций, которые нередко оказываются довольно проблемными, мы обычно разбиваем код на более мелкие блоки. Это облегчает как реализацию, так и возможные изменения и улучшения конечного кода.

Итак, уважаемый читатель, давайте сделаем шаг назад и начнём по-другому реализовывать код для построения дерева. Вы можете увидеть это ниже:

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

Код 03

А теперь обратите внимание на одну деталь. У нас есть два класса: один предназначен для представления каждого узла дерева и реализован в строке 4, а другой будет строить наше дерево и реализован в строке 29.

Таким образом, реализация начинает следовать более подходящей структуре, поскольку мы перестаём зависеть от аспектов, которые сильно затрудняют реализацию, и получаем больше свободы и безопасности. Это связано с тем, что мы ограничиваем доступ только к строго необходимой информации. Обратите внимание, что теперь в строке 32 внутри класса, который будет реализовывать дерево, мы объявляем переменную для хранения корня дерева. Таким образом, внутри самой функции OnStart нам нужно лишь объявить переменную, которая будет содержать экземпляр нашего дерева, что избавляет нас от необходимости отдельно контролировать и поддерживать корень дерева.

"Хорошо, так как же нам теперь реализовать то, что было сделано в предыдущих кодах?" Что ж, уважаемый читатель, это самая лёгкая и увлекательная часть всей нашей работы. Чтобы в нашем новом коде снова получить то же поведение, которое обеспечивал код 02, нам нужно реализовать несколько вещей. Вы увидите, что в конечном итоге всё окажется гораздо проще, чем то, что реализовано, например, в коде 02. Итак, наш следующий шаг — реализовать то, что показано ниже:

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

Код 04

Поскольку я забыл реализовать одну небольшую деталь в классе C_TreeNode в коде 03, здесь, в коде 04, я исправляю это небольшое упущение. Теперь обратите внимание на одну деталь в коде 04. Поведение этого кода идентично поведению предыдущих кодов. Однако сравните код функции OnStart в коде 04 с кодом в версиях 01 и 02. Обратите внимание, что здесь код стал гораздо проще.

Это не означает, что код 04 перестал работать так, как раньше. То есть, несмотря на изменения, внесённые для упрощения использования класса C_Tree, код 04 по-прежнему внутренне опирается на те же принципы, что и раньше. Другими словами, всё дерево по-прежнему создаётся полностью рекурсивно. Поэтому можно заметить, что приватные методы класса C_Tree в коде 04 очень похожи на то, что делалось в кодах 01 и 02. Именно поэтому нам практически не нужно возвращаться к объяснению с самого начала, поскольку вся методология сохранилась, но пользоваться доступными функциями стало гораздо удобнее.

Однако, несмотря на изменения, внесённые в код 04, у нас по-прежнему остаётся та же проблема, с которой мы столкнулись в начале этой статьи: отмеченные на изображении 01 предупреждения. Тем не менее, поскольку код 04 теперь реализован лучше и стал гораздо понятнее, мы наконец можем перейти к деструктору класса C_Tree. Для этого нам достаточно внимательно изучить приватные методы класса C_Tree. Чтобы удалить, а точнее, освободить выделенную память, нам придётся сделать нечто очень похожее на то, что мы делаем при обходе дерева. Давайте на минуту задумаемся.

Изучая функции обхода дерева, вы заметите одну интересную и важную для нас деталь. Когда мы используем функцию inOrder, показанную в строке 55, мы вызываем её для поиска самого левого узла. Когда мы его находим, начинаем обрабатывать значения узел за узлом. Однако после обхода левых узлов мы начинаем обходить правые. То есть мы не можем удалить центральный узел, не затруднив при этом доступ к узлам справа.

Что касается функции preOrder, которая приводится в строке 68, то здесь ситуация ещё сложнее. Это связано с тем, что сначала мы посещаем текущий, или центральный, узел, а уже потом обращаемся к узлам слева и справа. Без сомнения, это значительно усложняет дело. Помните, что наша цель — удалить дерево.

Что ж, у нас осталась только одна последняя попытка: попробовать функцию postOrder, которая приводится в строке 81. Эта функция действительно очень хорошо подходит для нашей задачи именно благодаря тому, как она обходит дерево. Обратите внимание, что сначала мы ищем узлы, расположенные глубже в дереве. Только после того, как мы достигаем их, мы начинаем посещать центральный узел. Это выглядит многообещающе, ведь когда этот центральный узел уже не будет связан ни с каким другим узлом — ни с левым дочерним, ни с правым, — мы сможем без проблем удалить его. Таким образом, мы сможем реализовать деструктор класса. Хорошо, давайте посмотрим, как можно реализовать этот код, применив принцип, который мы только что выявили, наблюдая за работой уже реализованного кода. Новый код, который теперь будет включать деструктор, приведён ниже:

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

Код 05

Надо же, какой странной вещи вы нас учите. Я всегда думал, что всё будет гораздо сложнее. Но, видя, как у вас это получается, я понимаю, что всё гораздо проще, чем я себе представлял. Вот теперь я действительно начинаю наслаждаться программированием на MQL5.

Уважаемый читатель, очень часто люди совершенно напрасно всё усложняют. Программирование — это очень интересно и увлекательно. Однако, вопреки тому, что многие могли бы подумать, хороший программист — это не тот, кто умеет писать сложный код, а тот, кто, используя свои знания и понимая простые концепции, способен создать практически любое решение на основе чего-то, что он увидел когда-то раньше в своей жизни. А поскольку он постоянно учится и практикуется, у него развивается более острое восприятие деталей, которые часто остались бы незамеченными.

Вернёмся к коду. Обратите внимание, что в строке 110 кода 05 мы реализовали деструктор класса. Я хочу, чтобы код оставался простым и понятным. Поэтому мы продолжим использовать рекурсию для реализации этого процесса. Поэтому деструктор вызовет другую процедуру, реализованную в строке 94. Обратите внимание, что эта процедура делает почти то же самое, что и функция postOrder в строке 81, но с одним отличием: в строке 89 мы получали значение, хранящееся в центральном узле, тогда как здесь, в процедуре из строки 94, мы будем удалять этот узел. Это происходит при выполнении инструкции в строке 101. При выполнении кода 05 мы получим результат, показанный на следующем изображении.

Изображение 02

"Ну вы и сумасшедший. Но мне понравилось, как вы объяснили и показали, как всё это делается. Тем не менее у меня есть некоторые вопросы по поводу этого кода 05. Первый вопрос такой: я заметил, что функция postOrder в строке 81 по ряду аспектов напоминает метод Destroy, реализованный в строке 94. Вопрос в следующем: нет ли способа упростить код 05, чтобы избежать кажущегося дублирования, которое мы видим в этих двух местах?"

Что ж, этот вопрос интересен и в то же время несколько интригует. В зависимости от программиста и от того, насколько ему интересно вносить те или иные изменения, код можно доработать или оставить без изменений, чтобы уменьшить такое дублирование. Как правило, на практике этого не делают, так как в большинстве случаев это совершенно не нужно.

Однако, поскольку здесь цель дидактическая, думаю, стоит показать, как можно изменить этот же код 05, чтобы его логика была, так сказать, менее фрагментированной. Для этого нам нужно проанализировать некоторые элементы кода и как следует понять, как они работают. Я оставляю вам это задание в качестве упражнения, чтобы вы сами составили своё представление о том, что происходит в коде. Тем не менее, я покажу альтернативный вариант с некоторыми упрощениями. Внеся определённые изменения в код 05, мы можем получить код, подобный приведённому ниже.

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

Код 06

Обратите внимание, что в этом коде 06 я лишь привёл код к несколько более ясной структуре. Тем не менее, мы можем улучшить и другие аспекты. В результате этих изменений мы получаем код, приведённый ниже:

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

Код 07

На мой взгляд, этот код 07 намного, намного лучше предыдущих. Это связано с тем, что в нём операции сгруппированы так, что это упрощает любые изменения, которые мы захотим внести. Четыре операции, которые раньше выполнялись в разных местах кода, теперь сосредоточены в одном месте: в методе на строке 60.

В этом коде 07 есть ещё одна деталь, которую я объясню в другой статье, поскольку сейчас мы не используем это понятие ни напрямую, ни явно. Очень важно хорошо понять эту концепцию, так как, возможно, в одном из ваших будущих кодов вам понадобится явно её использовать. Но пока мы оставим это объяснение на другой раз.

Обратите внимание, что предложенное мной упрощение приводит к гораздо более простому коду. Однако здесь возникает небольшая проблема или неудобство. Если вы рассматривали код, связанный с очередями и списками, то, вероятно, заметили, что в них можно было использовать данные любого типа. Однако в случае деревьев мы ограничены использованием только целочисленных типов. Вопрос в следующем: как мы можем устранить это ограничение? Многие могли бы сказать или подумать, что решить эту задачу очень просто. Теоретически да, решить это легко. Однако есть одна небольшая проблема. Чтобы это понять, давайте сосредоточимся на коде 07.

С самого начала эта реализация задумывалась как самоупорядоченное дерево. Говоря более понятно, уважаемый читатель: по мере вставки новых значений в дерево они помещаются справа или слева от узла в зависимости от значения, которое хранится в этом узле, независимо от того, является ли этот узел корнем дерева или любым другим узлом. Именно строка 51 кода 07 отвечает за этот процесс. Обратите внимание на эту простую деталь: если входное значение больше или равно значению узла — да, оно может быть и равным, — то оно помещается справа. Если оно меньше значения узла, то помещается слева. Эта небольшая деталь существенно влияет на конечный результат.

Таким образом, в зависимости от типа данных элемента дерева, используемого для определения направления, мы оказываемся ограничены самой реализацией. Один из способов решить эту проблему — заранее указать, в каком направлении следует идти. Мы также могли бы реализовать механизм автоматической балансировки, чтобы решить эту проблему. Однако я пока не хочу этого делать, потому что бывают случаи, когда нам НЕ НУЖНО сбалансированное дерево.

ВАЖНОЕ ПРЕДУПРЕЖДЕНИЕ: Как правило, деревья работают лучше и обеспечивают более высокую производительность, когда они правильно сбалансированы. Поэтому для достижения максимальной производительности настоятельно рекомендуется ВСЕГДА стараться поддерживать дерево как можно более сбалансированным.

Вопрос балансировки будет рассмотрен позже. А пока давайте сосредоточимся на нашей конкретной проблеме. Поскольку дерево автоматически упорядочивается благодаря логике, реализованной в строке 51, в принципе мы не сможем использовать любой тип данных. По крайней мере пока нам придётся ограничиться самыми простыми типами данных.

Тем не менее, это решение не мешает нам попытаться немного обобщить реализацию. Чтобы этого добиться, нам понадобится обратиться к концепции, описанной в других статьях этой же серии: к использованию шаблонов.

Хорошо, чтобы расширить нашу реализацию с помощью шаблонов, нам придётся изменить код и применить немного иной подход. Таким образом, мы получим новый код, основанный на том, что увидели в коде 07. Ниже вы можете увидеть его полностью:

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

Код 08

"Ради всего святого! Что это такое? Надо же, код мне был понятен вплоть до 32-й строки. Но как только мы дошли до той части, где нужно было реализовать класс C_Tree, всё, забудь об этом. С этого момента я уже совершенно ничего не мог понять. Так что, пожалуйста, помоги мне разобраться в некоторых вещах. Сначала позвольте мне показать вам, что мне удалось понять, а потом объясните мне остальное. Договорились?

Насколько я понял, элементы, которые мы хранили в дереве, были типа int. Поэтому, когда вы добавили объявление шаблона в строке 4, потребовалось лишь адаптировать код к этому новому типу. Именно поэтому были внесены изменения в строки 9, 20 и 26. До этого момента всё верно; я смог это понять, потому что это вполне логично. Однако, когда эта часть закончилась и мы приступили к реализации кода класса C_Tree, я перестал понимать, зачем понадобились эти изменения. С этого момента всё превратилось в настоящую путаницу".

Что ж, уважаемый читатель. В некотором смысле вам удалось понять часть того, что нужно было изменить в коде. Однако, возможно, вы не до конца поняли ещё один вопрос, который также рассматривался в этой статье. В ходе перехода от кода 02 к коду 04 появился класс C_TreeNode, экземпляры которого представляют узлы и хранят их элементы. Важная деталь: C_TreeNode не содержит само дерево; он лишь определяет, как каждый элемент связан с остальными внутри дерева. Понимание этого крайне важно для понимания самого класса C_Tree. А теперь подумайте немного. Если C_TreeNode содержит механизмы, позволяющие создать дерево, и при этом каждый экземпляр хранит элемент, соответствующий узлу дерева, то как мы могли бы указать, какие элементы он будет содержать? Имейте в виду, что мы будем обращаться не напрямую к C_TreeNode, а к C_Tree — классу, реализующему дерево.

Если посмотреть на это с такой точки зрения, становится понятнее, почему C_Tree тоже должен быть шаблонным классом, как и C_TreeNode. По этой причине в код была добавлена строка 34, превратившая C_Tree в шаблонный класс. А теперь начинается самая простая и увлекательная часть. Поскольку C_Tree является шаблонным классом и должен создавать объекты C_TreeNode, которые также должны использовать тот же тип, что определён для C_Tree, наиболее естественно параметризовать C_TreeNode этим же типом. Для этого мы изменим объявление корня дерева, как показано в строке 42.

Таким образом, C_TreeNode будет параметризована тем же типом, что и наше дерево. Но на этом всё не заканчивается. Поскольку все элементы могут быть любого типа, все объявления внутри класса C_Tree, в которых есть ссылка на C_TreeNode, нужно соответствующим образом скорректировать. Поэтому потребовалось отредактировать код класса C_Tree. Дорогой читатель, возможно, некоторые строки этого класса покажутся вам странными. Однако, чтобы упростить вам задачу и помочь лучше понять код 08, мы можем внести небольшое изменение. Это изменение показано ниже:

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

Код 09

А теперь обратите внимание на кое-что очень интересное. Если вы рассмотрите реализацию класса C_Tree в этом коде 09 и сравните её с кодом 07, то заметите, что они в основном одинаковы. Ни больше ни меньше. Однако, сравнив этот код 09 с кодом 08, вы увидите, что класс C_Tree отличается. Это связано именно с тем, что в этом коде 09 я добавил директиву препроцессора в строке 34. Эта директива приведёт к тому, что код класса C_Tree будет скорректирован так, что для компилятора он окажется эквивалентен коду 08, тогда как другой программист увидит нечто похожее на показанное в коде 07. Просто великолепно.

Таким образом, чтобы использовать любой тип данных, достаточно будет изменить тип, указанный в строке 137. Таким образом, у нашей реализации дерева появится гораздо более широкий спектр возможностей применения. Помните, что нам ещё предстоит рассмотреть вопрос со строкой 54 кода 09, но подробнее мы остановимся на нём позже.

Заключительные замечания

В этой статье мы поиграли и неплохо повеселились, совершенствуя наш код, предназначенный для создания дерева. Однако мы ещё не закончили с работой и реализацией обобщённого дерева. Возможно, вы уже полностью довольны тем, что мы здесь сделали, но нам ещё предстоит реализовать некоторые возможности, которые были в реализациях очередей и списков. Одна из них — возможность удалять элементы из дерева.

Тема нашей следующей статьи — как это сделать. Поэтому изучайте и отрабатывайте на практике то, что мы здесь рассмотрели, максимально используя коды, приведённые в приложении. Следующая тема будет крепким орешком, но я покажу вам, насколько увлекательным может быть его раскусить: удаление элементов из дерева.

Файл MQ5	Описание
Код 01	Простое дерево
Код 02	Простое дерево
Код 03	Простое дерево
Код 04	Простое дерево
Код 05	Простое дерево
Код 06	Простое дерево
Код 07	Простое дерево
Код 08	Простое дерево