Листинг 8.10. Методы Create и Destroy класса бинарного дерева

constructor TtdBinaryTree.Create(aDisposeItem : TtdDisposeProc);

begin

inherited Create;

FDispose := aDisposeItem;

{проверить, доступен ли диспетчер узлов}

if (BTNodeManager = nil) then

BTNodeManager := TtdNodeManager.Create(sizeof(TtdBinTreeNode));

{выделить заглавный узел; со временем корневой узел дерева станет его левым дочерним узлом}

FHead := BTNodeManager.AllocNodeClear;

end;

destructor TtdBinaryTree.Destroy;

begin

Clear;

BTNodeManager.FreeNode(FHead);

inherited Destroy;

end;

Метод Create убеждается, что диспетчер узлов бинарного дерева активен, а затем выделяет фиктивный заглавный узел. Именно на месте левого дочернего узла этого узла находится корневой узел дерева. Метод Destroy убеждается, что дерево очищено (т.е. все узлы в дереве освобождены), а затем освобождает фиктивный заглавный узел.

Следующий метод, который мы рассмотрим - метод Clear. В данном случае требуется удалить все узлы дерева. Как упоминалось ранее, это выполняется за счет применения обхода всего дерева в глубину. В данном случае мы воспользовались нерекурсивным обходом, поскольку он выполняется быстрее.

Листинг 8.11. Очистка бинарного дерева

procedure TtdBinaryTree.Clear;

var

Stack : TtdStack;

Node : PtdBinTreeNode;

begin

if (FCount = 0) then

Exit;

{создать стек}

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;

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.) Упорядочение применяется ко всем узлам в дереве: для каждого узла ключ левого дочернего узла меньше или равен ключу узла, а этот ключ, в свою очередь, меньше или равен ключу правого дочернего узла. Если описанное упорядочение постоянно применяется во время вставки (как именно - будет показано чуть ниже), это также означает, что для каждого узла все ключи в левом дочернем дереве меньше или равны ключу узла, а все ключи в правом дочернем дереве больше или равны ключу узла.