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