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