Фундаментальные алгоритмы и структуры данных в Delphi, Бакнелл Джулиан М.

Фундаментальные алгоритмы и структуры данных в Delphi

на обложку

Бакнелл Джулиан М.

Шрифт:

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

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

обойти это ограничение.

Листинг 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;

procedure InOrderTraverse(aRoot : PtdBinaryNode;