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

while not Stack.IsEmpty do

begin

{извлечь узел в начале очереди}

Node := Stack.Pop;

{если он является нулевым, вытолкнуть из стека следующий узел и освободить его}

if (Node = nil) then begin

Node := Stack.Pop;

if Assigned(FDispose) then

FDispose(Node^.btData);

BTNodeManager.FreeNode(Node);

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;

{внести изменения, отражающие то, что дерево пусто}

FCount := 0;

FHead^.btChild[ctLeft] nil;

end;

Если сравнить этот код с кодом общего метода нерекурсивного обхода, приведенным в листинге 8.7, то несложно заметить, что они во многом совпадают. Единственное реальное различие состоит в том, что в коде отсутствует какая-либо процедура действия - мы уже знаем, что будет делаться с каждым узлом.

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

Листинг 8.12. Обход в классе бинарного дерева

function TtdBinaryTree.btRecInOrder(aNode : PtdBinTreeNode;

aAction : TtdVisitProc; aExtraData : pointer): PtdBinTreeNode;

var

StopNow : boolean;

begin

Result := nil;

if (aNode^.btChild[ctLeft] <> nil) then begin

Result := btRecInOrder(aNode^.btChild[ctLeft],

aAction, aExtraData);

if (Result <> nil) then

Exit;

end;

StopNow := false;

aAction(aNode^.btData, aExtraData, StopNow);

if StopNow then begin

Result := aNode;

Exit;

end;

if < aNode^.btChild[ ctRight ] <> nil) then begin

Result := btRecInOrder(aNode^.btChild[ctRight], aAction, aExtraData);

end;

end;

function TtdBinaryTree.btRecPostOrder(aNode : PtdBinTreeNode;

aAction : TtdVisitProc; aExtraData : pointer): PtdBinTreeNode;

var

StopNow : boolean;

begin

Result := nil;

if (aNode^.btChild[ctLeft] <> nil) then begin

Result :=btRecPostOrder(aNode^.btChild[ctLeft], aAction, aExtraData);

if (Result <> nil) then

Exit;

end;

if (aNode^.btChild[ctRight] <> nil) then begin

Result := btRecPostOrder(aNode^.btChild[ctRight],

aAction, aExtraData);

if (Result <> nil) then

Exit;

end;

StopNow := false;

aAction(aNode^.btData, aExtraData, StopNow);

if StopNow then

Result :=aNode;

end;

function TtdBinaryTree.btRecPreOrder(aNode : PtdBinTreeNode;

aAction : TtdVisitProc; aExtraData : pointer): PtdBinTreeNode;

var

StopNow : boolean;

begin

Result := nil;

StopNow := false;

aAction(aNode^.btData, aExtraData, StopNow);

if StopNow then begin

Result :=aNode;

Exit;

end;

if (aNode^.btChild[ctLeft] <> nil) then begin

Result := btRecPreOrder(aNode^.btChild[ctLeft], aAction, aExtraData);

if (Result <> nil) then

Exit;

end;

if (aNode^.btChild[ctRight]<> nil) then begin

Result := btRecPreOrder(aNode^.btChild[ctRight], aAction, aExtraData);

end;

end;

function TtdBinaryTree.Traverse(aMode : TtdTraversalMode;

aAction : TtdVisitProc;

aExtraData : pointer;

aUseRecursion : boolean): PtdBinTreeNode;

var

RootNode : PtdBinTreeNode;

begin

Result := nil;

RootNode := FHead^.btChild[ctLeft];

if (RootNode <> nil) then begin

case aMode of

tmPreOrder :

if aUseRecursion then

Result := btRecPreOrder(RootNode, aAction, aExtraData) else

Result := btNoRecPreOrder(aAction, aExtraData);

tmlnOrder :

if aUseRecursion then

Result :=btRecInOrder(RootNode, aAction, aExtraData) else

Result := btNoRecInOrder(aAction, aExtraData);

tmPostOrder :

if aUseRecursion then

Result := btRecPostOrder(RootNode, aAction, aExtraData) else

Result := btNoRecPostOrder(aAction, aExtraData);

tmLevelOrder : Result :=btLevelOrder(aAction, aExtraData);

end;

end;

end;

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

Исходный код класса TtdBinaryTree можно найти на Web-сайте издательства, в разделе материалов. После выгрузки материалов отыщите среди них файл TDBinTre.pas.

Хотя бинарные деревья являются структурами данных, которые представляют интерес и сами по себе, на практике в основном используют бинарные деревья, содержащие элементы в сортированном виде. Такие бинарные деревья называют деревьями бинарного поиска (binary search tree).

В дереве бинарного поиска каждый узел имеет ключ. (В деревьях бинарного поиска, которые будут построены в этой главе, считается, что ключ является частью элемента, вставляемого в дерево. Для сравнения двух элементов, а, следовательно, и их ключей, мы будем использовать подпрограмму TtdConrpare.) Упорядочение применяется ко всем узлам в дереве: для каждого узла ключ левого дочернего узла меньше или равен ключу узла, а этот ключ, в свою очередь, меньше или равен ключу правого дочернего узла. Если описанное упорядочение постоянно применяется во время вставки (как именно - будет показано чуть ниже), это также означает, что для каждого узла все ключи в левом дочернем дереве меньше или равны ключу узла, а все ключи в правом дочернем дереве больше или равны ключу узла.

Какие основные операции претерпевают изменения в случае использования дерева бинарного поиска вместо обычного бинарного дерева? Что ж, все алгоритмы обхода работают так же, как и ранее (фактически, при симметричном обходе все узлы в дереве бинарного поиска посещаются в порядке ключей - отсюда и английское название этого метода "in-order"). Однако операции вставки и удаления должны быть изменены, поскольку они могут нарушить порядок ключей в дереве бинарного поиска. Поиск элемента может быть выполнен значительно быстрее.

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

Следует отметить одну особенность этого алгоритма в случае наличия в дереве нескольких элементов с равными ключами: не существует никаких гарантий, что мы найдем какой-то конкретный элемент с соответствующим ключом. Им может оказаться первый элемент, последний или любой промежуточный. Фактически, в основном по тем же причинам, что и при использовании списка с пропусками, желательно гарантировать, чтобы все элементы в дереве бинарного поиска имели уникальные, различающиеся между собой ключи. Присутствие дублированных ключей не допускается. На практике это правило не создает особых трудностей: если можно различить два элемента, должно быть не трудно обеспечить их различение и в дереве бинарного поиска. Обычно это достигается за счет использования младших ключей (например, фамилия служит в качестве главного ключа, а имя - в качестве контрольного значения, когда фамилии совпадают). Таким образом, деревья бинарного поиска, рассмотренные в этой главе, будут подчиняться правилу недопустимости дублированных ключей. В результате определение дерева бинарного поиска будет формулироваться следующим образом: это дерево, в котором ключ левого дочернего узла строго меньше ключа данного узла, который, в свою очередь, строго меньше ключа правого дочернего узла.