Фундаментальные алгоритмы и структуры данных в Delphi - Джулиан Бакнелл
Шрифт:
Интервал:
Закладка:
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 убеждается, что дерево очищено (т.е. все узлы в дереве освобождены), а затем освобождает фиктивный заглавный узел.
Следующий метод, который мы рассмотрим - метод 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.) Упорядочение применяется ко всем узлам в дереве: для каждого узла ключ левого дочернего узла меньше или равен ключу узла, а этот ключ, в свою очередь, меньше или равен ключу правого дочернего узла. Если описанное упорядочение постоянно применяется во время вставки (как именно - будет показано чуть ниже), это также означает, что для каждого узла все ключи в левом дочернем дереве меньше или равны ключу узла, а все ключи в правом дочернем дереве больше или равны ключу узла.
