Динамические структуры данных. Алексеев А.Ю - 54 стр.

UptoLike

ВУЗ: 

КамчатГТУ | Петропавловск-Камчатский

Составители: 

Рубрика: 

procedure обход_горизонтальный ( b: BTree );
var Q: queue of BTree;
p: BTree;
begin
Q := Create;
Q ← b;
while not Null ( Q ) do
begin
p ← Q;
посетить ( p );
if not Null ( Left ( p ) ) then Q
←
Left ( p );
if not Null ( Right ( p ) ) then Q
←
Right ( p )
end{while}
end{обход_горизонтальный}
Обходы леса
Следуя естественному (каноническому) соответствию между бинарными
деревьями и лесами, можно на основе КЛП-, ЛКП- и ЛПК-обходов бинарного
дерева получить три соответствующие порядка прохождения леса (и, следова-
тельно, произвольного дерева).
Прямой порядок:
а) посетить корень первого дерева;
б) пройти поддеревья первого дерева (в прямом порядке);
в) пройти оставшиеся деревья (в прямом порядке).
Обратный порядок:
а) пройти поддеревья первого дерева (в обратном порядке);
б) посетить корень первого дерева;
в) пройти оставшиеся деревья (в обратном порядке).
Концевой порядок:
а) пройти поддеревья первого дерева (в концевом порядке);
б) пройти оставшиеся деревья (в концевом порядке);
б) посетить корень первого дерева.
При необходимости применить какой-либо из этих обходов к лесу (дереву)
можно сначала построить бинарное дерево, представляющее этот лес, а затем
применить соответствующий обход бинарного дерева.
54
    procedure обход_горизонтальный ( b: BTree );
      var Q: queue of BTree;
           p: BTree;
    begin
       Q := Create;
       Q ← b;
       while not Null ( Q ) do
       begin
          p ← Q;
          посетить ( p );
          if not Null ( Left ( p ) ) then Q ← Left ( p );
          if not Null ( Right ( p ) ) then Q ← Right ( p )
       end{while}
    end{обход_горизонтальный}


                                  Обходы леса

   Следуя естественному (каноническому) соответствию между бинарными
деревьями и лесами, можно на основе КЛП-, ЛКП- и ЛПК-обходов бинарного
дерева получить три соответствующие порядка прохождения леса (и, следова-
тельно, произвольного дерева).

   Прямой порядок:
   а) посетить корень первого дерева;
   б) пройти поддеревья первого дерева (в прямом порядке);
   в) пройти оставшиеся деревья (в прямом порядке).

   Обратный порядок:
   а) пройти поддеревья первого дерева (в обратном порядке);
   б) посетить корень первого дерева;
   в) пройти оставшиеся деревья (в обратном порядке).

   Концевой порядок:
   а) пройти поддеревья первого дерева (в концевом порядке);
   б) пройти оставшиеся деревья (в концевом порядке);
   б) посетить корень первого дерева.
   При необходимости применить какой-либо из этих обходов к лесу (дереву)
можно сначала построить бинарное дерево, представляющее этот лес, а затем
применить соответствующий обход бинарного дерева.




                                        54

Страницы