Обход по уровням

Обход по уровням

Мы еще не рассматривали обход по уровням, при котором вначале посещается корневой узел, затем слева направо посещаются два возможных узла на первом уровне, затем слева направо четыре возможных узла на втором уровне и т.д. Этот метод обхода кажется слишком сложным для кодирования, но в действительности он очень прост. Достаточно знать один прием. Он заключается в следующем применении очереди. Поместим корневой узел в очередь, и будем выполнять цикл до тех пор, пока очередь не опустеет. Удалим из очереди верхний узел. Посетим его. Если его левая дочерняя связь является ненулевой, поместим ее в очередь. Если правая дочерняя связь является ненулевой, поместим в очередь и ее. Если очередь не пуста, снова выполним цикл. Вот, собственно, и все.

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

Поделитесь на страничке

Следующая глава >

Похожие главы из других книг:

17.5.2. Обход системных зависимостей

Из книги автора

17.5.2. Обход системных зависимостей После выбора языка и библиотек поддержки следующим вопросом переносимости обычно является расположение ключевых системных файлов и каталогов: почтовых спулов, каталогов журнальных файлов и т.д. Прообразом данного типа проблем


17.5.2. Обход системных зависимостей

Из книги автора

17.5.2. Обход системных зависимостей После выбора языка и библиотек поддержки следующим вопросом переносимости обычно является расположение ключевых системных файлов и каталогов: почтовых спулов, каталогов журнальных файлов и т.д. Прообразом данного типа проблем


6.2.3. Обход диапазона

Из книги автора

6.2.3. Обход диапазона Обычно диапазон можно обойти. Для этого класс, которому принадлежат границы диапазона, должен предоставлять осмысленный метод succ (следующий).(3..6).each {|x| puts x } # Печатаются четыре строки                          # (скобки обязательны).Пока все хорошо. И


8.1.18. Обход массива

Из книги автора

8.1.18. Обход массива Как и следовало ожидать, в классе Array есть стандартный итератор each. Но имеются и другие полезные итераторы.Метод reverse_each обходит массив в обратном порядке. Результат такой же, как если бы мы вызвали сначала метод reverse, а потом each, но работает быстрее.words =


8.2.5. Обход хэша

Из книги автора

8.2.5. Обход хэша В классе Hash имеется стандартный итератор each, а кроме него итераторы each_key, each_pair и each_value (each_pair — синоним each).{"а"=>3, "b"=>2}.each do |key, val| print val, " из ", key, "; " # 3 из a; 2 из b;endОстальные два итератора передают в блок только ключ или только значение:{"а"=>3,"b"=>2}.each_key do


10.1.30. Обход каталога

Из книги автора

10.1.30. Обход каталога Метод класса foreach — это итератор, который последовательно передает в блок каждый элемент каталога. Точно так же ведет себя метод экземпляра each.Dir.foreach("/tmp") { |entry| puts entry }dir = Dir.new("/tmp")dir.each { |entry| puts entry }Оба фрагмента печатают одно и то же (имена всех файлов и


11.3.11. Обход пространства объектов

Из книги автора

11.3.11. Обход пространства объектов Система исполнения Ruby должна отслеживать все известные объекты (хотя бы для того, чтобы убрать мусор, когда на объект больше нет ссылок). Информацию о них можно получить с помощью метода ObjectSpace.each_object.ObjectSpace.each_object do |obj| printf "%20s: %s ", obj.class,


Обход чертежа

Из книги автора

Обход чертежа Команда 3DWALK интерактивно меняет вид трехмерного чертежа, при этом кажется, что наблюдатель обходит модель. Команда вызывается из падающего меню View ? Walk and Fly ? Walk или щелчком на пиктограмме Walk плавающей панели инструментов Walk and Fly или 3D Navigation.Обход всей


Обход в ширину, симметричный обход и обход в глубину

Из книги автора

Обход в ширину, симметричный обход и обход в глубину Прежде чем приступить к описанию остальных трех алгоритмов обхода, которые взаимосвязаны, приведем несколько иное определение бинарного дерева. Бинарное дерево состоит из корневого узла, содержащего указатели на


Обход чертежа

Из книги автора

Обход чертежа Команда 3DWALK интерактивно меняет вид трехмерного чертежа, при этом кажется, что наблюдатель обходит модель. Команда вызывается из падающего меню View ? Walk and Fly ? Walk или щелчком на пиктограмме Walk на плавающей панели инструментов Walk and Fly или 3D Navigation.Обход всей


Обход чертежа

Из книги автора

Обход чертежа Команда 3DWALK интерактивно меняет вид трехмерного чертежа, при этом кажется, что наблюдатель обходит модель. Команда вызывается из падающего меню View ? Walk and Fly ? Walk или щелчком на пиктограмме Walk на плавающей панели инструментов Walk and Fly или 3D Navigation.Обход всей


28.4. Переходим к уровням выполнения

Из книги автора

28.4. Переходим к уровням выполнения Одной из последних задач процесса init, которая реализуется перед тем, как система "полностью запустится", является выполнение всех сценариев для уровня выполнения, заданного по умолчанию. Файл, осуществляющий эту задачу, называется либо