Текст книги "Фундаментальные алгоритмы и структуры данных в Delphi"
Автор книги: Джулиан Бакнелл
сообщить о нарушении
Текущая страница: 21 (всего у книги 36 страниц)
Все остальные действия являются тривиальными и особого интереса не представляют – выполняется проверка правильности значений счетчиков групп, добавление новой группы, обновление исходной группы и обеспечение того, чтобы записи каталога, которые требуют изменения, указывали на новую группу.
Полный код класса TtdHashTableExtendible можно найти на Web-сайте издательства, в разделе материалов. После выгрузки материалов отыщите среди них файл TDHshExt.pas.
Резюме
В этой главе были рассмотрены хеш-таблицы – структуры данных, которые пытаются предоставить максимально быстрый доступ к своим элементам, при этом они подпадают под категорию O(1).
Мы рассмотрели различные хранящиеся в памяти таблицы, включая две наиболее важных – хеш-таблицу, использующую линейное зондирование, и хеш-таблицу, в которой применяется связывание. Мы ознакомились с преимуществами и недостатками каждого из этих методов и со способами их настройки.
И, наконец, мы выяснили, как поддерживать хеш-таблицы на диске, минимизируя при этом количество обращений к диску. Мы рассмотрели алгоритм группирования и его реализацию для создания базы данных, в основе которой лежит хеширование.
Глава 8. Бинарные деревья.
Подобно массивам и связным спискам, деревья того или иного вида – это структуры данных, которые используются программистами практически повсеместно. В главе 3 были рассмотрены односвязные списки, в которых существовала единственная связь, соединяющая узлы друг с другом (двухсвязные списки имели также связь, указывающую в противоположном направлении). Обычно связные списки рассматриваются как горизонтальные структуры (в целях экономии места на бумаге!), в которых начальный узел располагается слева, а сам связный список простирается направо. Теперь представим, что этот связный список повернут на 90 градусов по часовой стрелке, чтобы начальный узел располагался вверху, а конечный внизу. Этот случай представляет собой особый пример многопутевого дерева, в котором каждый узел имеет только один дочерний узел, расположенный непосредственно под ним. Аналогично, каждый узел имеет один родительский узел, который расположен непосредственно над ним. Естественно, такая классификация охватывает целое семейство деревьев. Примем соглашение, что самый нижний узел имеет нулевую связь, т.е. не имеет дочернего узла. Поскольку каждый узел имеет максимум один дочерний узел, односвязный список можно было бы называть унарным деревом.
Многопутевое дерево является обобщением этой концепции. Оно представляет собой коллекцию узлов, организованных так, чтобы все узлы кроме корневого (мы будем называть узел в верхушке дерева корневым, а узел, который не имеет дочерних узлов – листовым, или просто листом) имели только один родительский узел и могли иметь ноль или больше дочерних узлов. Таким образом, связный список – это особое многопутевое дерево, в котором каждый узел (кроме самого нижнего) имеет только один дочерний узел. Если каждый узел может иметь максимум n дочерних узлов, такое дерево называется n-арным деревом.
Рисунок 8.1. Бинарное дерево
Теперь рассмотрим случай, когда каждый узел имеет до двух дочерних узлов. Иначе говоря, для каждого узла существует максимум две связи с узлами следующего нижнего уровня. Эта структура называется бинарным деревом. Согласно принятому соглашению, два дочерних узла данного узла называются левым и правым дочерними узлами, поскольку при рисовании дерева с расположением его корня в вершине, дочерние узлы выстраиваются горизонтально под ним, один левее от другого. Классическое представление бинарного дерева показано на рис. 8.1.
Из приведенных рассуждений ясно, что при определении используемого узла бинарного дерева в Delphi-программе нам требуются две связи (т.е. указатели) с его дочерними узлами, связь с его родительским узлом (эта связь необязательна, но, как мы увидим, ее применение упрощает некоторые алгоритмы, работающие с деревьями) и фактические данные, которые должны храниться в узле. С целью упрощения задачи примем, что данные в узле могут быть представлены указателем, подобно TList и структурам данных, которые уже были рассмотрены в этой книге. Поскольку узел имеет фиксированный размер, мы снова воспользуемся описанным в главе 3 диспетчером узлов, когда дело дойдет до создания класса бинарного дерева. Код, приведенный в листинге 8.1, определяет расположение записей узлов.
Листинг 8.1. Расположение узлов в бинарном дереве type
TtdChildType = ( {типы дочерних узлов}
ctLeft, {.. левый дочерний узел}
ctRight);
{.. правый дочерний узел}
TtdRBColor = ( {цвета для красно-черного дерева}
rbBlack, {..черный}
rbRed);
{..красный}
PtdBinTreeNode = ^TtdBinTreeNode;
TtdBinTreeNode = packed record btParent : PtdBinTreeNode;
btChild : array [TtdChildType] of PtdBinTreeNode;
btData : pointer;
case boolean of
false : (btExtra : longint);
true : (btColor : TtdRBColor);
end;
Обратите внимание, что две дочерние связи мы определили в виде двухэлементного массива. На первый взгляд, это может показаться излишним, но когда дело дойдет до реализации операций с бинарным деревом, такое определение существенно упростит нашу задачу. Кроме того, узел бинарного дерева объявляет дополнительное поле, которое не требуется для обычных бинарных деревьев, однако упрощает задачу для красно-черного варианта дерева бинарного поиска.
Создание бинарного дерева
Само по себе создание бинарного дерева тривиально. В простейшем случае корневой узел бинарного дерева определяет все бинарное дерево.
var
MyBinaryTree : PtBinTreeNode;
Если MyBinaryTree равен nil, никакого бинарного дерева не существует, поэтому это значение служит начальным значением бинарного дерева.
{инициализировать бинарное дерево}
MyBinaryTree :=nil;
На практике принято использовать фиктивный узел, аналогичный фиктивному заглавному узлу односвязного списка, чтобы каждый реальный узел дерева, включая корневой, имел родительский узел. Корневой узел может быть как левым, так и правым дочерним узлом фиктивного узла, но для определенности примем, что он является левым.
Вставка и удаление с использованием бинарного дерева
Если мы всерьез намереваемся использовать бинарное дерево, необходимо рассмотреть, как выполняется добавление в дерево элементов (т.е. узлов), удаление элементов из дерева и посещение всех элементов дерева. Последняя операция позволит выполнять поиск конкретного элемента. Поскольку выполнение последних двух операций невозможно без рассмотрения первой, начнем с рассмотрения вставки узла в бинарное дерево.
Чтобы иметь возможность вставить узел в бинарное дерево, необходимо выбрать родительский узел, к которому можно присоединить новый узел в качестве дочернего, и более того, этот узел не может уже иметь два дочерних узла. Мы должны также знать, каким дочерним узлом – левым или правым – должен стать новый узел.
При заданном родительском узле и указании дочерних узлов слева направо код для вставки узла очень прост. Мы создаем узел, устанавливаем в качестве значения его поля данных элемент, который добавляем в дерево, и определяем обе его дочерние связи как nil. Затем, во многом подобно вставке узла в двусвязный список, мы устанавливаем соответствующий дочерний указатель родительского узла так, чтобы он указывал на новый дочерний узел, а )родительский указатель дочернего узла – на родительский узел.
Листинг 8.2. Вставка в бинарное дерево
function TtdBinaryTree.InsertAt(aParentNode : PtdBinTreeNode;
aChildType : TtdChildType; aItem : pointer): PtdBinTreeNode;
begin
{если родительский узел является нулевым, считаем, что выполняется вставка корневого узла}
if (aParentNode = nil) then begin
aParentNode := FHead;
aChildType :=ctLeft;
end;
{выполнить проверку mos о, установлена ли уже дочерняя связь}
if (aParentNode^.btChild[aChildType]<> nil) then
btError(tdeBinTreeHasChild, 'InsertAt');
{распределить новый узел и вставить в качестве требуемого дочернего узла родительского узла}
Result := BTNodeManager.AllocNode;
Result^.btParent := aParentNode;
Result^.btChild[ctLeft] :=nil;
Result^.btChild[ctRight] := nil;
Result^.btData := aItem;
Result^.btExtra := 0;
aParentNode^.btChild[aChildType] := Result;
inc(FCount);
end;
Обратите внимание, что приведенный в листинге 8.2 код вначале проверяет, является ли добавляемый узел корневым. Если да, то переданный родительский узел равен nil. В этом случае метод инициализирует родительский узел значением внутреннего заглавного узла.
Кроме этой проверки метод InsertAt убеждается, что дочерняя связь, которую предполагается использовать для нового узла, действительно не используется. В противном случае это будет грубой ошибкой.
Обратите внимание, что класс бинарного дерева (составной частью которого является этот метод) использует диспетчер узлов для распределения и освобождения узлов. Поскольку все узлы имеют одинаковый размер, в этом, как было сказано в главе 3, заложен глубокий смысл.
А как выполняется удаление узлов? Эта задача несколько сложнее, поскольку узел может иметь один или два дочерних узла. Первое правило удаления может быть сформулировано следующим образом: листовой узел (т.е. не имеющий дочерних узлов) может быть удален без каких-либо нежелательных последствий. При этом мы выясняем, каким дочерним узлом родительского узла является лист, и устанавливаем соответствующую дочернюю связь равной nil. После этого узел может быть освобожден.
Второе правило удаления из бинарного дерева применяется в отношении случая, когда удаляемый узел имеет один дочерний узел. Эта задача также достаточно проста: мы просто перемещаем дочерний узел вверх по дереву, чтобы он стал тем же дочерним узлом родительского узла, каким является удаляемый узел.
Третье правило применяется к случаю, когда удаляемый узел имеет два дочерних узла. Как и можно было предположить, это правило звучит просто: узел не может быть удален. Попытка сделать это является ошибкой. Позже мы рассмотрим вариант бинарного дерева – дерево бинарного поиска, – который содержит достаточный объем дополнительной внедренной в дерево информации, чтобы можно было обойти это ограничение.
Листинг 8.3. Удаление из бинарного дерева
procedure TtdBinaryTree.Delete(aNode : PtdBinTreeNode);
var
OurChildsType : TtdChildType;
OurType : TtdChildType;
begin
if (aNode = nil) then
Exit;
{выяснить, имеется ли единственный дочерний узел, и то, каким узлом он является; при наличии двух дочерних узлов сгенерировать ошибку}
if (aNode^.btChild[ctLeft] <> nil) then begin
if (aNode^.btChild[ctRight] <> nil) then
btError(tdeBinTree2Children, 'Delete');
OurChildsType :=ctLeft;
end
else
OurChildsType :=ctRight;
{выяснить, является ли дочерний узел левым или правым дочерним узлом данного родительского узла}
OurType := GetChildType(aNode);
{установить дочернюю связь данного родительского узла равной данной дочерней связи}
aNode^.btParent^.btChild[OurType] := aNode^.btChild[OurChildsType];
if (aNode^.btChild[OurChildsType] <> nil) then
aNode^.btChild[OurChildsType]^.btParent := aNode^.btParent;
{освободить узел}
if Assigned(FDispose) then
FDispose(aNode^.btData);
BTNodeManager.FreeNode(aNode);
dec(FCount);
end;
В листинге 8.3 не учтен случай, когда удаляемый узел является нулевым. В любом случае в этой ситуации мало что можно сделать, а генерация исключения была бы излишней. Поэтому метод проверяет, чтобы удаляемый узел не имел двух дочерних узлов. Однако он не разделяет два других случая удаления (т.е. случаи отсутствия дочерних узлов и наличия только одного дочернего узла), а объединяет их в один случай, когда один дочерний узел замещает узел, даже если дочерний узел является нулевым. GetChildType – это небольшая функция, которая возвращает информацию о том, является ли ее параметр узла левым или правым дочерним узлом родительского узла.
Перемещение по бинарному дереву
После того, как мы рассмотрели построение бинарного дерева, можно рассмотреть вопрос о том, как посетить все узлы такой структуры. Под посещением подразумевается выполнение той или иной обработки хранящегося в узле элемента. Такой обработкой могло бы быть как выполнение простой операции, подобной записи данных в узел, так и реализация более сложных действий.
В отличие от связных списков, где перемещение по структуре определено однозначно (достаточно следовать всем указателям Next (следующий), пока не будет достигнут конец списка), в бинарном дереве в каждом узле можно выбрать один из двух путей, и поэтому процесс несколько усложняется. Процедуру перемещения по дереву называют обходом (traversal). Существуют четыре основных алгоритма обхода – обходом в ширину (pre-order), симметричным обходом (in-order), обходом в глубину (post-order) и обходом по уровням (level-order). Последний алгоритм – обход по уровням – наиболее прост для визуального представления, но наиболее сложен для кодирования. Этот алгоритм предполагает посещение каждого из узлов, начиная с корневого, и просмотр узлов сверху вниз, уровень за уровнем. На каждом уровне мы посещаем узлы слева направо. Таким образом, мы посещаем корневой узел, левый дочерний узел корневого узла, правый дочерний узел корневого узла, левый дочерний узел левого дочернего узла корневого узла, правый дочерний узел левого дочернего узла корневого узла и т.д. Снова обратившись к рисунку 8.1, мы видим, что при обходе по уровням посещение узлов выполнялось бы в следующем порядке: d, b, f, а, с, е, g.
Обход в ширину, симметричный обход и обход в глубину
Прежде чем приступить к описанию остальных трех алгоритмов обхода, которые взаимосвязаны, приведем несколько иное определение бинарного дерева. Бинарное дерево состоит из корневого узла, содержащего указатели на корневые узлы двух других бинарных деревьев, называемых дочерними. Указатели на любой или оба дочерних узла могут быть нулевыми. Это определение описывает бинарное дерево очень кратко, хотя и рекурсивно. Тем не менее, оно представляет собой идеальный способ описания остальных трех видов обхода.
При обходе в ширину вначале мы посещаем корневой узел, затем, используя алгоритм обхода в ширину, выполняем обход левого дочернего дерева, а затем таким же образом выполняем обход правого дочернего дерева. (Обход дерева, изображенного на рис. 8.1, выполнялся бы в следующем порядке: d, b, а, с, /, е, g.) При симметричном обходе вначале выполняется обход левого дочернего дерева корневого узла с применением алгоритма симметричного обхода, а затем симметричный обход правого дочернего дерева. (В дереве, показанном на рис. 8.1, посещение узлов выполнялось бы в следующем порядке: а, b, с, d, е, /, g.) При обходе в глубину вначале выполняется обход в левого дочернего дерева с применением алгоритма обхода в глубину, затем таким же образом выполняется обход правого дочернего дерева, а затем посещается корневой узел. (В дереве, изображенном на рис. 8.1, посещение узлов выполнялось бы в следующем порядке: а, с, b, е, g, f, d.)
Обход в глубину чаще всего применяется для уничтожения всех узлов в бинарном дереве, когда процесс уничтожения можно было бы описать следующим образом: "чтобы уничтожить все узлы в бинарном дереве, необходимо уничтожить левое дочернее дерево корневого узла, затем правое дочернее дерево корневого узла, а затем сам коревой узел".
Создание кода, реализующего эти три алгоритма обхода, не представляет особой сложности: достаточно создать рекурсивную процедуру, которая вызывает сама себя для каждого узла. Пример простого кода выполнения рекурсивных обходов приведен в листинге 8.4.
Листинг 8.4. Обход в ширину, симметричный обход и обход в глубину
type
TtdProcessNode = procedure(aNode : PtdBinaryNode);
procedure PreOrderTraverse(aRoot : PtdBinaryNode;
aProcessNode : TtdProcessNode);
begin
if (aNode <> nil) then begin
aProcessNode(aRoot);
PreOrderTraverse(aRoot^.bnChild[ciLeft], aProcessNode);
PreOrderTraverse(aRoot^.bnChild[ciRight], aProcessNode);
end;
end;
procedure InOrderTraverse(aRoot : PtdBinaryNode;
aProcessNode : TtdProcessNode);
begin
if (aNode <> nil) then begin
InOrderTraverse(aRoot^.bnChild[ciLeft], aProcessNode);
aProcessNode(aRoot);
InOrderTraverse(aRoot^.bnChild[ciRight], aProcessNode);
end;
end;
procedure PostOrderTraverse(aRoot : PtdBinaryNode;
aProcessNode : TtdProcessNode);
begin
if (aNode <> nil) then begin
PostOrderTraverse(aRoot^.bnChild[ciLeft], aProcessNode);
PostOrderTraverse(aRoot^.bnChild[ciRight], aProcessNode);
aProcessNode(aRoot);
end;
end;
Обратите внимание на то, как каждая рекурсивная процедура проверяет, не является ли переданный ей узел нулевым. В этом случае она не выполняет никаких действий, немедленно осуществляя выход. Следовательно, со временем рекурсивный вызов процедур завершится (поскольку дерево простирается не до бесконечности).
Однако в каждом случае применения рекурсивной процедуры следует оценить, сколько раз она должна будет выполняться в ходе последовательности рекурсивных вызовов. Дело в том, что рекурсивные процедуры хранят свое состояние в стеке программы, размер которого в общем случае ограничен. Если выясняется, что рекурсивная процедура может иметь слишком много уровней, следует подумать над тем, как избавиться от рекурсии за счет применения внешнего стека. Используя внешний стек вместо стека программы, можно быть уверенным, что при необходимости размер стека в куче можно будет увеличить (пока выделенный объем кучи не будет исчерпан, однако, в общем случае этот объем значительно превышает размер стека программы).
Мы используем стек, созданный на основе связного списка класса TtdStack, который был описан в главе 3. Для выполнения обхода в ширину мы заталкиваем в стек корневой узел и выполняем цикл, который продолжается до тех пор, пока стек не опустеет. Мы выталкиваем из стека верхний узел и посещаем его. Если правая дочерняя связь этого узла является ненулевой, мы заталкиваем ее в стек. Затем заталкиваем в стек левую дочернюю связь узла, если она является ненулевой. (Заталкивание дочерних узлов в указанном порядке означает, что вначале из стека выталкивается левый дочерний узел.) Если стек не является пустым, цикл повторяется. Обход завершается немедленно после опустошения стека.
Листинг 8.5. Нерекурсивный обход в ширину
type
TtdVisitProc = procedure ( aData : pointer;
aExtraData : pointer;
var aStopVisits : boolean );
function TtdBinaryTree.btNoRecPreOrder(aAction : TtdVisitProc;
aExtraData : pointer): PtdBinTreeNode;
var
Stack : TtdStack;
Node : PtdBinTreeNode;
StopNow : boolean;
begin
{предположим, что мы не добрались до выбранного узла}
Result := nil;
StopNow := false;
{создать стек}
Stack := TtdStack.Create(nil);
try
{затолкнуть корневой узел}
Stack.Push(FHead^.btChild[ctLeft]);
{продолжать процесс до тех пор, пока стек не будет пуст}
while not Stack.IsEmpty do
begin
{извлечь узел в начале очереди}
Node := Stack.Pop;
{выполнить с ним указанное действие; если в результате возвращаемое значение переменной StopNow равно true, вернуть этот узел}
aAction(Node^.btData, aExtraData, StopNow);
if StopNow then begin
Result := Node;
Stack.Clear;
end
{в противном случае продолжить цикл}
else begin
{затолкнуть правую дочернюю связь, если она не нулевая}
if (Node^.btChild[ctRight] <> nil) then
Stack.Push(Node^.btChild[ctRight]);
{затолкнуть левую дочернюю связь, если она не нулевая}
if (Node^.btChild[ctLeft]<> nil) then
Stack.Push(Node^.btChild[ctLeft]);
end;
end;
finally
{уничтожить стек}
Stack.Free;
end;
end;
Касательно кода, приведенного в листинге 8.5, следует сделать несколько замечаний. Во-первых, мы используем процедуру действия, которая несколько сложнее применявшейся ранее. Процедура типа TtdVisitProc предоставляет пользователю метода обхода большую степень управления процессом, а именно -возможность остановить обход. Т.е. пользователь класса бинарного дерева может выполнять действия как для каждой записи (посещая все узлы), так и для первой найденной записи (т.е. для поиска первого узла, удовлетворяющего заданному условию). Значение третьего параметра процедуры действия, aStopVisits, устанавливается равным false вызывающей процедурой, а если процедуре действия нужно остановить обход, это значение может быть установлено равным true (в этом случае метод обхода вернет элемент, который привел к возврату значения true процедурой действия).
Однако, важная особенность приведенного в листинге 8.5 кода состоит в том, что процедура считает дерево не пустым. Фактически эта процедура – внутренняя процедура класса бинарного дерева, возможного при определенных условиях, и она будет вызываться только для дерева, которое содержит, по меньшей мере, один узел.
Убедившись, насколько просто избавиться от рекурсии при обходе в ширину, можно было бы предположить, что это легко сделать и для остальных двух видов обхода. Однако, применяя это же подход к симметричному обходу и обходу в глубину, мы сталкиваемся с препятствием. Чтобы понять, о чем идет речь, рассмотрим исключение рекурсии для симметричного обхода тем же способом, который был применен для обхода в ширину. Теоретически в цикле нужно было бы затолкнуть в стек правый дочерний узел, затем сам узел, а затем левый дочерний узел. Далее, со временем, нужно было бы вытолкнуть узел из стека и выполнить его обработку. Но, вытолкнув узел из стека, как узнать, встречался ли он ранее? Если узел ранее встречался, его нужно посетить;
если нет, его вместе с дочерними узлами необходимо затолкнуть в стек, но в правильном порядке.
В действительности нужно сделать следующие действия. Вытолкнуть узел из стека. Если ранее узел не встречался, нужно затолкнуть в стек правый дочерний узел, пометить узел как "встречавшийся", затолкнуть его, а затем затолкнуть в стек левый дочерний узел. Если ранее узел встречался (помните, что он уже помечен?), следует просто его обработать. Но как пометить узел? В конце концов, узел – это указатель, и в действительности не хотелось бы с ним возиться. Я предлагаю следующее решение: после заталкивания в стек "встречавшегося" узла нужно затолкнуть узел nil. В этом случае выталкивание из стека нулевого узла свидетельствует о том, что следующий узел в стеке является тем, который должен быть обработан.
Нерекурсивный алгоритм симметричного обхода работает следующим образом. Затолкните в стек корневой узел и войдите в цикл, который должен выполняться до момента опустошения стека. Вытолкните верхний узел из стека. Если он является нулевым, вытолкните из стека следующий узел и посетите его. Если вытолкнутый узел не является нулевым, затолкните в стек правый дочерний узел (если он является ненулевым), затем сам узел, затем затолкните нулевой указатель и в заключение затолкните в стек левый дочерний узел (если он является ненулевым). Снова выполните цикл.
Как и в случае обхода в ширину, метод предполагает, что дерево является не пустым, и что в нем присутствует, по меньшей мере, один узел. В данном случае это еще более важно, поскольку метод может работать совершенно не правильно, если нулевой узел заталкивается в стек, который не связан с алгоритмом.
Листинг 8.6. Нерекурсивный симметричный обход
function TtdBinaryTree.btNoRecInOrder(aAction : TtdVisitProc;
aExtraData : pointer): PtdBinTreeNode;
var
Stack : TtdStack;
Node : PtdBinTreeNode;
StopNow : boolean;
begin
{предположим, что мы не добрались до выбранного узла}
Result := nil;
StopNow := false;
{создать стек}
Stack := TtdStack.Create(nil);
try
{затолкнуть корневой узел}
Stack.Push(FHead^.btChild[ctLeft]);
{продолжать процесс до тех пор, пока стек не опустеет}
while not Stack.IsEmpty do
begin
{извлечь узел в начале очереди}
Node := Stack.Pop;
{если он является нулевым, вытолкнуть из стека следующий узел и выполнить с ним указанное действие. Если в результате возвращается запрос на прекращение обхода, вернуть этот узел}
if (Node = nil) then begin
Node := Stack.Pop;
aAction(Node^.btData, aExtraData, StopNow);
if StopNow then begin
Result := Node;
Stack.Clear;
end;
end
{в противном случае дочерние узлы этого узла в стек еще не заталкивались}
else begin
{затолкнуть правый дочерний узел, если он не нулевой}
if (Node^.btChild[ctRight] <> nil) then
Stack.Push(Node^.btChild[ctRight]);
{затолкнуть узел, а за ним – нулевой указатель}
Stack.Push(Node);
Stack.Push(nil);
{затолкнуть левый дочерний узел, если он не нулевой}
if (Node^.BtChild[ctLeft] <> nil) then
Stack.Push(Node^.btChild[ctLeft]);
end;
end;
finally
{уничтожить стек}
Stack.Free;
end;
end;
Нерекурсивный алгоритм обхода в глубину работает аналогично. Необходимо затолкнуть в стек корневой узел и войти в цикл, который будет выполняться до момента опустошения стека. В цикле необходимо вытолкнуть из стека верхний узел. Если он является нулевым, нужно вытолкнуть из стека следующий узел и выполнить его обработку. Если узел не является нулевым, следует затолкнуть в стек сам узел, затем нулевой указатель, затем правый дочерний узел (если он является ненулевым), а затем левый дочерний узел (если он является ненулевым). Затем необходимо снова выполнить цикл.
Листинг 8.7. Нерекурсивный обход в глубину
function TtdBinaryTree.btNoRecPostOrder(aAction : TtdVisitProc;
aExtraData : pointer): PtdBinTreeNode;
var
Stack : TtdStack;
Node : PtdBinTreeNode;
StopNow : boolean;
begin
{предположим, что мы не добрались до выбранного узла}
Result := nil;
StopNow := false;
{создать стек}
Stack := TtdStack.Create(nil);
try
{затолкнуть корневой узел}
Stack.Push(FHead^.btChild[ctLeft]);
{продолжать процесс до тех пор, пока стек не опустеет}
while not Stack.IsEmpty do
begin
{извлечь узел в начале очереди}
Node := Stack.Pop;
{если он является нулевым, вытолкнуть из стека следующий узел и выполнить с ним указанное действие. Если в результате возвращается значение false (т.е. обход должен быть прекращен), вернуть этот узел}
if (Node = nil) then begin
Node := Stack.Pop;
aAction(Node^.btData, aExtraData, StopNow);
if StopNow then begin
Result := Node;
Stack.Clear;
end;
end
{в противном случае дочерние узлы этого узла в стек еще не заталкивались}
else begin
{затолкнуть узел, а за ним – нулевой указатель}
Stack.Push(Node);
Stack.Push(nil);
{затолкнуть правый дочерний узел, если он не нулевой}
if (Node^.btChild[ctRight] <> nil) then
Stack.Push(Node^.btChild[ctRight]);
{затолкнуть левый дочерний узел, если он не нулевой}
if (Node^.btChild[ctLeft] <> nil) then
Stack.Push(Node^.btChild[ctLeft]);
end;
end;
finally
{уничтожить стек}
Stack.Free;
end;
end;
Как и ранее, по тем же причинам, метод предполагает, что дерево является не пустым.
Обход по уровням
Мы еще не рассматривали обход по уровням, при котором вначале посещается корневой узел, затем слева направо посещаются два возможных узла на первом уровне, затем слева направо четыре возможных узла на втором уровне и т.д. Этот метод обхода кажется слишком сложным для кодирования, но в действительности он очень прост. Достаточно знать один прием. Он заключается в следующем применении очереди. Поместим корневой узел в очередь, и будем выполнять цикл до тех пор, пока очередь не опустеет. Удалим из очереди верхний узел. Посетим его. Если его левая дочерняя связь является ненулевой, поместим ее в очередь. Если правая дочерняя связь является ненулевой, поместим в очередь и ее. Если очередь не пуста, снова выполним цикл. Вот, собственно, и все.
Листинг 8.8. Обход по уровням
function TtdBinaryTree.btLevelOrder(aAction : TtdVisitProc;
aExtraData : pointer): PtdBinTreeNode;
var
Queue : TtdQueue;
Node : PtdBinTreeNode;
StopNow : boolean;
begin
{предположим, что мы не добрались до выбранного узла}
Result := nil;
StopNow := false;
{создать очередь}
Queue := TtdQueue.Create(nil);
try
{поместить корневой узел в очередь}
Queue.Enqueue(FHead^.btChild[ctLeft]);
{продолжать процесс до тех пор, пока очередь не опустеет}
while not Queue.IsEmpty do
begin
{извлечь узел в начале очереди}
Node := Queue.Dequeue;
{выполнить действия с ним. Если в результате возвращается запрос на прекращение обхода, вернуть этот узел}
aAction(Node^.btData, aExtraData, StopNow);
if StopNow then begin
Result :=Node;
Queue.Clear;
end
{в противном случае продолжить процесс}
else begin
{поместить в очередь левый дочерний узел, если он не нулевой}
if (Node^.btChild[ctLeft]<> nil) then
Queue.Enqueue(Node^.btChild[ctLeft]);
{поместить в очередь правый дочерний узел, если он не нулевой}
if (Node^.btChild[ctRight] <> nil) then
Queue.Enqueue(Node^.btChild[ctRight]);
end;
end;
finally
{уничтожить очередь}
Queue.Free;
end;
end;
Подобно методам нерекурсивного обхода, метод btLevelOrder должен вызываться только для дерева, которое является непустым.
Реализация класса бинарных деревьев
Как и в случае остальных уже рассмотренных структур данных, мы реализуем стандартное бинарное дерево в виде класса. Действительно, мы уже положили начало такому подходу, рассмотрев различные методы готового класса.
В идеале, как, например, это было сделано для связных списков, желательно освободить пользователя класса от необходимости разбираться в структуре узлов (это позволит нам впоследствии изменять их структуру, не причиняя неудобств пользователю класса). Но в случае использования обычных бинарных деревьев приходится предполагать наличие у пользователя определенных знаний о структуре узлов, которые позволяют ему вставить новый узел (пользователь должен сообщить классу дерева, какой узел является родительским, и каким дочерним узлом становится новый узел). Поэтому наша реализация будет "черным ящиком" не совсем в той степени, в какой хотелось бы.
Класс бинарного дерева будет поддерживать такие стандартные операции, как вставка и удаление. Кроме того, его метод Traverse будет поддерживать различные виды обхода. Одним из методов, который мог бы обеспечить определенные преимущества при решении задач, подобных синтаксическому анализу выражений, была бы операция объединения двух деревьев в новый корневой узел.
Листинг 8.9. Интерфейс класса бинарного дерева
type
TtdBinaryTree – class {класс бинарного дерева}
private
FCount : integer;
FDispose : TtdDisposeProc;
FHead : PtdBinTreeNode;
FName : TtdNameString;
protected
procedure btError(aErrorCode : integer;
const aMethodName : TtdNameString);
function btLevelOrder(aAction : TtdVisitProc;
aExtraData : pointer): PtdBinTreeNode;
function btNoRecInOrder(aAction : TtdVisitProc;
aExtraData : pointer): PtdBinTreeNode;
function btNoRecPostOrder(aAction : TtdVisitProc;
aExtraData : pointer): PtdBinTreeNode;
function btNoRecPreOrder(aAction : TtdVisitProc;
