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

Понятие обхода. Виды обходов

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

Понятие обхода вводится для любых деревьев, однако удобнее начать с обхода бинарных деревьев.

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

Таблица 3.4.

Рекурсивное прохождение бинарного дерева.

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

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

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

Иногда используется еще один способ обхода - в горизонтальном порядке (в ширину). При таком способе узлы бинарного дерева проходятся слева направо, уровень за уровнем, от корня вниз (поколение за поколением от старших к младшим).

    Таблица 3.5.

Прохождение узлов дерева при различных порядках обхода

Например, построенное ранее бинарное дерево, изображеннное на рис. 3.10,а (для удобства мы его перерисуем снова) можно обойти различными способами так, как показано в табл.3.5

Пример обходов — дерево-формула

Арифметические и логические выражения могут быть представлены при помощи дерева, которое получило название дерева-формулы. Возьмём в качестве примера выражение (2+4)*7-3/5. Тогда получим следующее бинарное дерево, изображенное на рис. 3.13.

Рис.3.13. Пример дерева-формулы

Листья дерева-формулы — всегда операнды (переменные или значения), а все внутренние узлы соответствуют операциям.

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

Каждое поддерево дерева-формулы соответствует некоторой части исходного выражения, причем операцию, которая находится в корне этого дерева, можно выполнить только после вычисления значений поддеревьев. Например, для дерева, которое изображено на рис.3.12, операция умножения (корень левого поддерева) может быть выполнена только после того, как будет выполнена операция сложения (2+4). Операция, которая находится в корне дерева выражения, должна быть выполнена последней. В данном примере сначала вычисляется (2+4)*7, затем 3/5, а последней выполняется операция вычитания. Обратим внимание, что такой порядок вычисления соответствует обратному (ЛПК) порядку обхода дерева.

Дерево-формула — классический пример для иллюстрации различных способов обхода деревьев. Одна из распространенных терминологий для названий обходов — префиксный (PreOrder, прямой порядок), постфиксный (PostOrder, обратный порядок) и инфиксный (InOrder, центрированный порядок). Эти названия связаны с различными формами представления дерева-формулы. Применяя различные методы обхода к дереву на рис.3.13, получим разные способы записи выражения:

- * + 2 4 7 / 3 5 префиксная форма

2 4 + 7 * 3 5 / -        постфиксная форма

2 + 4 * 7 – 3 / 5        инфиксная форма

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

Проанализируем три формы записи выражения, полученные при различных обходах дерева-формулы. Центрированный порядок полностью соответствует обычной записи арифметического выражения, если из нее убрать скобки. По такой записи невозможно правильно вычислить значение выражения, не зная, как были расставлены скобки. Зато два других способа можно использовать для вычисления значения выражения непосредственно, т. к. в этом случае порядок вычислений определяется однозначно.

Из приведенного примера видно, что при префиксной форме знак операции непосредственно предшествует своим операндам, при постфиксной форме он располагается сразу после операндов. В префиксной форме порядок выполнения операций следует читать справа налево (знак последней операции — крайний слева символ), в постфиксной — слева направо. Эти две формы иначе называются бесскобочными формами записи выражения.

Наиболее удобной в реализации является постфиксная форма, которая получила название обратной польской записи (ОПЗ), поскольку ее использование для представления выражений впервые предложил польский математик Я.Лукашевич. Она часто используется как промежуточная форма представления выражений по следующим причинам:

1. вычисление выражения по ОПЗ можно выполнить итеративно за один проход;

2. существует простой итеративный алгоритм, предложенный Дейкстрой, для перехода от арифметического выражения, записанного в обычной форме со скобками, к постфиксной форме. С ним можно познакомиться, например, в[10].

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