Центрированный порядок обхода (ЛКП)

Алгоритм центрированного обхода несколько сложнее, поскольку в этом случае корень каждого поддерева нельзя обрабатывать сразу, поэтому придется поместить его в стек и двигаться дальше по левой ветви, помещая в стек все узлы до первого листа [7]. Нерекурсивная функция ЛКП обхода может выглядеть так:

void centralstack(bt t) // в центрированном порядке (ЛКП)

{ stack<bt> s; bt p=t;

do // помещаем в стек узел и переходим к левому сыну

{ if (p) { s.push(p); p=left(p);}

else // дошли до левого листа, будем извлекать узлы

{if (!s.isnull())p=s.pop(); else return;

visit(p); // любая обработка узла p

p=right(p); //правое поддерево проходим после корня

}

}

while (true);

В табл. 3.7 представлено содержимое стека перед каждым извлечением очередного элемента.

Таблица 3.7

Содержимое стека при центрированном порядке обхода

	№ итерации	Извлекаемый узел	Содержимое стека
	4	D	dba
	5	b	ba
	8	G	gea
	9	E	ea
	10	A	a
	12	C	c
	14	F	f

В данном алгоритме обход дерева из семи узлов выполняется за 14 итераций, поскольку на каждой итерации в стек заносится или из него извлекается один узел (итерации, на которых в стек заносится узел, в таблице не показаны).

Обратный порядок обхода (ЛПК)

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

1. Вместо обработки узла (корня поддерева) будем помещать его в еще один, дополнительный стек (назовем его стеком вывода sout). Тогда на заключительном этапе алгоритма элементы дополнительного стека будут обработаны в порядке, обратном тому, в котором они поступили в стек.

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

Функция обратного обхода может иметь вид:

void reversestack(bt t) // обход в обратном порядке (ЛПК)

// используем дополнительный стек sout

{ stack<bt> s,sout;

s.push(t); bt p;

while (!s.isnull())

{p=s.pop();

sout.push(p);//вместо обработки узла помещаем его в стек

 if(left(p)) s.push(left(p));

if(right(p)) s.push(right(p));

}

while (!sout.isnull())// извлекаем узлы из стека

{p=sout.pop(); visit(p);}//любая обработка

}

Обход в ширину

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

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

2. Вторая модификация такая же, как и для обратного обхода — сначала помещаем в очередь левого сына, а после него правого. Это тоже понятно, поскольку узлы обходятся слева направо.

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

Напомним основные операции:

enqueue,dequeue – помещение элемента в очередь и удаление из нее;

isnull – проверка на пустоту.

void widthstack(bt t) // обход в ширину

{ queue<bt> q; // шаблон queue должен быть реализован!

q.enqueue(t); bt p;

while (!q.isnull())

{ p=q.dequeue();

  cout << root(p)<<" ";

  if(left(p)) q.enqueue (left(p));

  if(right(p)) q.enqueue (right(p));

}

}

Все приведенные в данном разделе функции обхода в конце работы оставляют вспомогательные структуры пустыми, т. е. не требуют никакой дополнительной «уборки» памяти.

Обходы леса

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

· корень первого дерева

· лес поддеревьев первого дерева

· оставшиеся деревья.

На основе этого представления сформулируем правила обхода.

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

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

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

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

Центрированный порядок:

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

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

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

 Обратный (концевой) порядок:

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

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

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

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

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

Прошитые деревья

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

Хорошим способом сократить расходы памяти при обходе являются так называемые прошитые деревья (используем термин из [8]). Идея их очень проста — вместо пустых ссылок хранить обратные ссылки на узлы-предки, тогда в процессе обхода всю (или почти всю) необходимую информацию для перемещения между узлами можно будет получать из самих узлов. Правда при этом в каждом узле придется иметь дополнительное поле-признак, который позволит отличить указателей на сыновей от указателей на родителей. В принципе для такого признака достаточно иметь всего лишь один бит, и иногда такой бит даже находится в структуре самого дерева. Например, если известно, что в узлах хранятся только положительные значения, можно задействовать для этих целей знаковый разряд.

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

Имеются различные способы реализации прошитых деревьев. Наиболее понятным и простым в реализации представляется следующий случай.

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

Данная идея поясняется с помощью рис.3.11. На рис.3.11,а изображено упорядоченное дерево произвольного вида. Путем изменения связей это дерево преобразуется к бинарному (рис.3.11, б). В полученном бинарном дереве узлы a,d,g и h не имеют правых сыновей, поэтому они могут использоваться для хранения обратных ссылок (они показаны пунктиром). Мы умышленно не стали разворачивать рисунок так, чтобы бинарное дерево приобрело привычный вид, чтобы хорошо была заметна аналогия с циклическими линейными списками, которые используют ту же самую идею, что и прошитые деревья.

Рис.3.12. Прошитое дерево

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

a b c e f g d h

На рис.3.12,б хорошо видно, что хранимых в дереве обратных ссылок вполне достаточно, чтобы выполнить прямой обход, не используя никакой дополнительной памяти. Структура для представления узлов дерева может иметь, например, такой вид

template <class T>

struct node

{ T data; //данные, которые содержатся в узле

node *son, *brother;// указатели на левого сына и правого брата

bool youngest; // признак самого младшего брата

}

Алгоритм прямого обхода прост [11] и понятен из рис. 3.12, б.

1. Если у узла имеется сын, то переходим к сыну.

2. Если нет сына, но имеется брат, то переходим к брату.

3. Если нет ни сына, ни брата, то находим брата у ближайшего предка, у которого он есть.

4. Если таких предков нет, то обход закончен.