Нерекурсивная версия также могла бы рисовать кривые более высоких порядков, но построение кривых Серпинского с порядком выше 8 или 9 непрактично. Все эти факты определяют преимущество рекурсивного алгоритма.
Программа Sierp2 использует этот нерекурсивный алгоритм для построения кривых Серпинского. Задавайте вначале построение несложных кривых (меньше 6 порядка), пока не определите, насколько быстро будет выполняться эта программа на вашем компьютере.
При применении рекурсивных алгоритмов следует избегать трех основных опасностей:
· Бесконечной рекурсии. Убедитесь, что условия остановки вашего алгоритма прекращают все рекурсивные пути.
· Глубокой рекурсии. Если алгоритм достигает слишком большой глубины рекурсии, он может привести к переполнению стека. Минимизируйте использование стека за счет уменьшения числа определяемых в процедуре переменных, использования глобальных переменных, или определения переменных как статических. Если процедура все равно приводит к переполнению стека, перепишите алгоритм в нерекурсивном виде, используя устранение хвостовой рекурсии.
· Ненужной рекурсии. Обычно это происходит, если алгоритм типа рекурсивного вычисления чисел Фибоначчи, многократно вычисляет одни и те же промежуточные значения. Если вы столкнетесь с этой проблемой в своей программе, попробуйте переписать алгоритм, используя подход снизу вверх. Если алгоритм не позволяет прибегнуть к подходу снизу вверх, создайте таблицу промежуточных значений.
Применение рекурсии не всегда неправильно. Многие задачи являются рекурсивными по своей природе. В этих случаях рекурсивный алгоритм будет проще понять, отлаживать и поддерживать, чем его нерекурсивную версию. В качестве примера можно привести алгоритмы построения кривых Гильберта и Серпинского. Оба по своей природе рекурсивны и намного понятнее, чем их нерекурсивные модификации. При этом рекурсивные версии даже выполняются немного быстрее.
Если у вас есть алгоритм, который рекурсивен по своей природе, но вы не уверены, будет ли рекурсивная версия лишена проблем, запишите алгоритм в рекурсивном виде и выясните это. Может быть, проблемы не возникнут. Если же они возникнут, то, возможно, окажется проще преобразовать эту рекурсивную версию в нерекурсивную, чем написать нерекурсивную версию с нуля.
======115
Во 2 главе приводились способы создания динамических связных структур, таких, как изображенные на рис 6.1. Такие структуры данных называются графами (graphs). В 12 главе алгоритмы работы с графами и сетями обсуждаются более подробно. В этой главе рассматриваются графы особого типа, которые называются деревьями (trees).
В начале этой главы приводится определение дерева и разъясняются некоторые термины. Затем в ней описываются некоторые методы реализации деревьев различных типов на языке Visual Basic. В последующих разделах рассматривается несколько алгоритмов обхода для деревьев, записанных в этих разных форматах. Глава заканчивается обсуждением некоторых специальных типов деревьев, включая упорядоченные деревья (sorted trees), деревья со ссылками[RV7] (threaded trees), боры[RV8] (tries) и квадродеревья[RV9] (quadtrees).
В 7 и 8 главе обсуждаются более сложные темы — сбалансированные деревья и деревья решений.
@Рис. 6.1. Графы
=====117
Можно рекурсивно определить дерево как:
* Пустую структуру или
* Узел, называемый корнем (node) дерева, связанный с нулем или более поддеревьев (subtrees).
На рис. 6.2 показано дерево. Корневой узел A связан с тремя поддеревьями, начинающимися в узлах B, C и D. Эти узлы связаны с поддеревьями с корнями E, F и G, и эти узлы, в свою очередь связаны с поддеревьями с корнями H, I и J.
Терминология деревьев представляет собой смесь терминов, позаимствованных из ботаники и генеалогии. Из ботаники пришли термины, такие как узел (node), определяемый как точка, в которой может начинаться ветвление, ветвь (branch), определяемая как связь между двумя узлами, и лист (leaf) — узел, из которого не выходят другие ветви.
Из генеалогии пришли термины, которые описывают родство. Если один узел находится непосредственно над другим, верхний узел называется родителем (parent), а нижний дочерним узлом (child). Узлы на пути вверх от узла до корня называются предками (ancestors) узла. Например, на рис. 6.2 узлы E, B и A — это все предки узла I.
Узлы, которые находятся ниже какого‑либо узла дерева, называются потомками (descendants) этого узла. Узлы E, H, I и J на рис. 6.2 — это все потомки узла B.
Иногда узлы, имеющие одного родителя, называются узлами‑братьями или узлами‑сестрами (sibling nodes).
Существует еще несколько терминов, которые не пришли из ботаники или генеалогии. Внутренним узлом (internal node) называется узел, который не является листом. Порядком узла (node degree) называется число его дочерних узлов. Порядок дерева — это наибольший порядок его узлов. Дерево на рис. 6.2 — третьего порядка, потому что узлы с наибольшим порядком, узлы A и E, имеют по 3 дочерних узла.
Глубина (depth) дерева равна числу его предков плюс 1. На рис. 6.2 глубина узла E равна 3. Глубиной (depth) или высотой (height) дерева называется наибольшая глубина его узлов. Глубина дерева на рис. 6.2 равна 4.
Дерево 2 порядка называется двоичным деревом (binary tree). Деревья третьего порядка иногда называются троичными[RV10] (ternary) деревьями. Более того, деревья порядка N иногда называются N‑ичными (N‑ary) деревьями.
@Рис. 6.2. Дерево
======118
Дерево порядка 12, например, называется 12‑ричным (12‑ary) деревом, а не додекадеричным (dodecadary) деревом. Некоторые избегают употребления лишних терминов и просто говорят «деревья 12 порядка».
Рис. 6.3 иллюстрирует некоторые из этих терминов.
Теперь, когда вы познакомились с терминологией, вы можете представить себе способы реализации деревьев на языке Visual Basic. Один из способов — создать отдельный класс для каждого типа узлов дерева. Для построения дерева, показанного на рис. 6.3, вы можете определить структуры данных для узлов, которые имеют ноль, один, два или три дочерних узла. Этот подход был бы довольно неудобным. Кроме того, что нужно было бы управлять четырьмя различными классами, в классах потребовались бы какие‑то флаги, которые бы указывали тип дочерних узлов. Алгоритмы, которые оперировали бы этими деревьями, должны были бы уметь работать со всем различными типами деревьев.
В качестве простого решения можно определить один тип узлов, который содержит достаточное число указателей на потомков для представления всех нужных узлов. Я называю это методом полных узлов, так как некоторые узлы могут быть большего размера, чем необходимо на самом деле.
Дерево, изображенное на рис 6.3, имеет 3 порядок. Для построения этого дерева с использованием метода полных узлов (fat nodes), требуется определить единственный класс, который содержит указатели на три дочерних узла. Следующий код демонстрирует, как эти указатели могут быть определены в классе TernaryNode.
Public LeftChild As TernaryNode
Public MiddleChild As TernaryNode
Public RightChild As TernaryNode
@Рис. 6.3. Части троичного (3 порядка) дерева
======119
При помощи этого класса можно построить дерево, используя записи Child узлов, для связи их друг с другом. Следующий фрагмент кода строит два верхних уровня дерева, показанного на рис. 6.3.
Dim A As New TernaryNode
Dim B As New TernaryNode
Dim C As New TernaryNode
Dim D As New TernaryNode
:
Set A.LeftChild = B
Set A.MiddleChild = C
[RV11] :
Программа Binary, показанная на рис. 6.4, использует метод полных узлов для работы с двоичным деревом. Когда вы выбираете узел с помощью мыши, программа подсвечивает кнопку Add Left (Добавить слева), если узел не имеет левого потомка и кнопку Add Right (Добавить справа), если узел не имеет правого потомка. Кнопка Remove (Удалить) разблокируется, если выбранный узел не является корневым. Если вы нажмете на кнопку Remove, программа удалит узел и всех его потомков.
Поскольку программа позволяет создать узлы с нулевым числом, одним или двумя дочерними узлами, она использует представление в виде полных узлов. Вы можете легко распространить этот пример на деревья более высоких порядков.
Если порядки узлов в дереве сильно различаются, метод полных узлов приводит к напрасному расходованию большого количества памяти. Чтобы построить дерево, показанное на рис. 6.5 с использованием полных узлов, вам понадобится определить в каждом узле по шесть указателей, хотя только в одном узле все шесть из них используются. Это представление дерева потребует 72 указателей на дочерние узлы, из которых в действительности будет использоваться только 11.
@Рис. 6.4. Программа Binary
======120
Некоторые программы добавляют и удаляют узлы, изменяя порядок узлов в процессе выполнения. В этом случае метод полных узлов не будет работать. Такие динамически изменяющиеся деревья можно представить, поместив дочерние узлы в списки. Есть несколько подходов, которые можно использовать для создания списков дочерних узлов. Наиболее очевидный подход заключается в создании в классе узла открытого (public) массива дочерних узлов, как показано в следующем коде. Тогда для оперирования дочерними узлами можно использовать методы работы со списками на основе массивов.
Public Children() As TreeNode
Public NumChildren As Integer
К сожалению, Visual Basic не позволяет определять открытые массивы в классах. Это ограничение можно обойти, определив массив как закрытый (private), и оперируя элементами массива при помощи процедур свойств.
Private m_Chirdren() As TreeNode
Private m_NumChildren As Integer