Книга: Фундаментальные алгоритмы и структуры данных в 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 должен вызываться только для дерева, которое является непустым.

Оглавление книги