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

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

aExtraData : pointer): PtdBinTreeNode;

function btRecIn0rder(aNode : PtdBinTreeNode; aAction : TtdVisitProc;

aExtraData : pointer): PtdBinTreeNode;

function btRecPostOrder(aNode : PtdBinTreeNode; aAction : TtdVisitProc;

aExtraData : pointer): PtdBinTreeNode;

function btRecPreOrder(aNode : PtdBinTreeNode; aAction : TtdVisitProc;

aExtraData : pointer): PtdBinTreeNode;

public

constructor Create(aDisposeItem : TtdDisposeProc);

destructor Destroy; override;

procedure Clear;

procedure Delete(aNode : PtdBinTreeNode);

function InsertAt(aParentNode : PtdBinTreeNode;

aChildType : TtdChildType; aItem : pointer): PtdBinTreeNode;

function Root : PtdBinTreeNode;

function Traverse(aMode : TtdTraversalMode; aAction : TtdVisitProc;

aExtraData : pointer; aUseRecursion : boolean): PtdBinTreeNode;

property Count : integer read FCount;

property Name : TtdNameString read FName write FName;

end;

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

Листинг 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 убеждается, что дерево очищено (т.е. все узлы в дереве освобождены), а затем освобождает фиктивный заглавный узел.