Материал: АиСД деревья

3.4. Обходы бинарных деревьев и леса

Многие алгоритмы работы с бинарными деревьями основаны на последовательной (в определенном порядке) обработке узлов дерева. В этом случае говорят об обходе (прохождении) бинарного дерева. Такой обход порождает определенный порядок перечисления узлов бинарного дерева. Выделяют несколько стандартных вариантов обхода. Будем именовать их в зависимости от того порядка, в котором при этом посещаются корень дерева и узлы левого и правого поддеревьев. Например, при КЛП-обходе сначала посещается корень, затем обходятся в КЛП-порядке последовательно левое и правое поддеревья. Приведем рекурсивные процедуры КЛП-, ЛКП- и ЛПК-обходов, прямо соответствующие их рекурсивным определениям (операция обработки узла обозначена как «посетить (узел)»):

Следует обратить внимание на то, что в литературе используется различная терминология при именовании видов обхода бинарного дерева. Перечислим наиболее популярные варианты терминологии (виды обходов перечислены во всех вариантах в одной и той же последовательности):

1) КЛП, ЛКП, ЛПК [14];

2) прямой, обратный, концевой [10];

3) прямой, симметричный, обратный [13];

4) сверху вниз, слева направо, снизу вверх [5], [6];

5) префиксный (PreOrder), инфиксный (InOrder), постфиксный

(PreOrder) [5], [6].

Иногда обход КЛП называют обходом в глубину. В некоторых случаях используется смешанная терминология [16]. Будем придерживаться далее вариантов терминологии 1 и 2. В варианте 2 названия обходам даны соответственно тому, что в КЛП-порядке корень посещается перед посещением узлов левого поддерева (прямой порядок), а в ЛКП-порядке корень посещается после обхода узлов левого поддерева (обратный порядок). В ЛПК-порядке корень посещается после обхода узлов левого и правого поддеревьев (концевой порядок). Такая терминология основана на важной роли левого поддерева в естественном соответствии бинарного дерева и леса (см. 3.3).

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

(a + b) * c  d / (e + f * g) .

На рис. 3.8 представлено соответствующее ему бинарное дерево.

Error: Reference source not found

Рис. 3.8. Бинарное дерево, представляющее

арифметическое выражение (a + b) * c – d / (e + f * g)

Тогда три варианта обхода этого дерева порождают три известные формы записи арифметического выражения:

1) КЛП  префиксную запись

 * + a b c / d + e * f g ;

2) ЛКП  инфиксную запись (без скобок, необходимых для задания последовательности выполнения операций)

a + b * c  d / e + f * g ;

3) ЛПК  постфиксную запись

a b + c * d e f g * + /  .

В качестве упражнения полезно дать интерпретацию и остальным вариантам названий обходов.

Нерекурсивные процедуры обхода бинарных деревьев

Учитывая важность эффективной реализации обходов бинарных деревьев, рассмотрим нерекурсивные процедуры обходов. Общий нерекурсивный алгоритм для всех трех порядков обхода использует стек S для хранения упорядоченных пар (p, n), где p  узел бинарного дерева, а n  номер операции, которую надо применить к p, когда пара (p, n) будет выбрана из стека. Операции «посетить корень», «пройти левое поддерево», «пройти правое поддерево» нумеруются числами 1, 2, 3 в зависимости от порядка их выполнения в данном варианте обхода. В алгоритме эти операции будут реализованы следующим образом:

Здесь и далее для краткости и наглядности использованы следующие обозначения операций со стеком: S  e вместо S := Push (e, S) и e  S вместо Pop2 (e, S).

Тогда общий алгоритм имеет вид:

procedure обход (b: BTree);

var S: Stack of (BTree, operation);

p: BTree; op: operation {=1..3};

begin

S := Create; S  (b, 1);

while not Null (S) do

begin (p, op)  S;

if op = 1 then begin S  (p, 2); операция 1 end

else if op = 2 then begin S  (p, 3); операция 2 end

else {op = 3} операция 3

end{while}

end{обход}

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

procedure обход_КЛП (b: BTree); {прямой}

var S: Stack of BTree; p: BTree;

begin

S:= Create; S  b;

while not Null (S) do

begin

p  S; посетить (p);

if not Null (Right (p)) then S  Right (p);

if not Null (Left (p)) then S  Left (p)

end{while}

end{обход_КЛП}

В случае ЛКП-обхода также возможно некоторое упрощение  в стеке сохраняются указания лишь на операции 1 или 2:

procedure обход_ЛКП (b: BTree); {обратный}

var S: Stack of (BTree, operation);

p: BTree; op: operation {=1..2};

begin S:= Create; S  (b , 1);

while not Null (S) do

begin (p, op)  S;

if op = 1 then

begin S  (p, 2); if not Null (Left (p)) then S  (Left (p), 1)

end

else {op=2}

begin

посетить (p); if not Null (Right (p)) then S  (Right (p), 1)

end

end{while}

end{обход_ЛКП}

Конкретизация общего алгоритма для ЛПК-обхода (здесь нет упрощений) имеет вид:

Обходы леса

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

Прямой порядок: 

а) посетить корень первого дерева;

б) пройти поддеревья первого дерева (в прямом порядке);

в) пройти оставшиеся деревья (в прямом порядке).

Обратный порядок: 

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

б) посетить корень первого дерева;

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

Концевой порядок: 

а) пройти поддеревья первого дерева (в концевом порядке);

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

в) посетить корень первого дерева.

Более формально обход леса в прямом порядке можно записать следующим образом:

procedure PreOrder (F: Forest); {прямой}

begin

if not Null (F) then

begin

посетить (Root (Head (F));

PreOrder (Listing (Head (F)));

PreOrder (Tail (F));

end

end{PreOrder}

Аналогично записываются процедуры обхода леса в обратном и концевом порядках.

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

3.5. Представления и реализации бинарных деревьев

Рассмотрим варианты представления и реализации структуры данных бинарного дерева. Пусть базовый тип узлов есть Elem.

Ссылочная реализация бинарного дерева в связанной памяти основана на представлении типа BT (Elem) рекурсивными типами BinT и Node:

type

BinT = ^Node; {представление бинарного дерева}

Node = record {узел: }

Info: Elem; { содержимое}

LSub: BinT; { левое поддерево}

RSub: BinT { правое поддерево}

end {Node}