Обход дерева предварительного заказа — итеративный и рекурсивный
Имея двоичное дерево, напишите итеративное и рекурсивное решение для обхода дерева с использованием обхода в прямом порядке в C++, Java и Python.
В отличие от связанных списков, одномерных массивов и других линейных структур данных, обход которых осуществляется в линейном порядке, по деревьям можно перемещаться несколькими способами. глубина первого порядка (предварительный заказ, в целях, а также постзаказ) или же ширина первого порядка (обход порядка уровней). Помимо этих основных обходов, возможны различные более сложные или гибридные схемы, такие как поиск с ограничением по глубине, например итеративный поиск в глубину с углублением. В этом посте подробно обсуждается обход дерева предварительного заказа.
Обход дерева включает в себя итерацию по всем узлам тем или иным образом. Поскольку дерево не является линейной структурой данных, может быть более одного возможного следующего узла от данного узла, поэтому некоторые узлы должны быть отложены, т. е. каким-то образом сохранены для последующего посещения. Обход может выполняться итеративно, когда отложенные узлы хранятся в stack, или это можно сделать с помощью рекурсия, где отложенные узлы неявно хранятся в стек вызовов.
Для обхода (непустого) бинарного дерева в предварительном порядке мы должны сделать эти три вещи для каждого узла. n начиная с корня дерева:
(N) Процесс n сам.
(L) Рекурсивно обходим его левое поддерево. Когда этот шаг будет завершен, мы вернемся к n опять таки.
(R) Рекурсивно обходим его правое поддерево. Когда этот шаг будет завершен, мы вернемся к n опять таки.
В обычном обходе в предварительном порядке посетите левое поддерево перед правым поддеревом. Если мы посещаем правое поддерево перед посещением левого поддерева, это называется обходом в обратном порядке.
Рекурсивная реализация
Как мы видим, только после обработки любого узла обрабатывается левое поддерево, а за ним правое поддерево. Эти операции могут быть определены рекурсивно для каждого узла. Рекурсивная реализация называется Поиск в глубину (DFS), так как дерево поиска максимально углубляется для каждого дочернего элемента, прежде чем перейти к следующему родственному элементу.
Ниже приведена программа на C++, Java и Python, которая демонстрирует это:
Источник
Обход бинарных деревьев: рекурсия, итерации и указатель на родителя
Основы о бинарных деревьях представлены, в том числе, здесь . Добавлю свои «5 копеек» и данным постом систематизирую материалы, связанные с обходом бинарных деревьев, а именно сравнений возможностей рекурсии и итераций, а также обсуждение возможностей использования указателя на родительский узел.
Итак… язык Java, класс узла имеет следующий вид:
Примечание: Указатель на родителя parent – как правило не имеет большого смысла, однако, как следует из заголовка и будет показано, может быть полезен в ряде случаев.
Обход деревьев – последовательная обработка (просмотр, изменение и т.п.) всех узлов дерева, при котором каждый узел обрабатывается строго один раз. При этом получается линейная расстановка узлов дерева.
В зависимости от траекторий выделяют два типа обхода:
— горизонтальный (в ширину); и
— вертикальный (в глубину).
Горизонтальный обход подразумевает обход дерева по уровням (level-ordered) – вначале обрабатываются все узлы текущего уровня, после чего осуществляется переход на нижний уровень.
При вертикальном обходе порядок обработки текущего узла и узлов его правого и левого поддеревьев варьирует и по этому признаку выделяют три варианта вертикального обхода:
— прямой (префиксный, pre-ordered): вершина – левое поддерево – правое поддерево;
— обратный (инфиксный, in-ordered): левое поддерево – вершина – правое поддерево; и
— концевой (постфиксный, post-ordered): левое поддерево – правое поддерево – вершина.
Сам обход во всех случаях в принципе один и тот же, различается порядок обработки. Для представления в каком порядке будет проходить обработка узлов дерева удобно следовать по «контуру обхода». При прямом обходе узел будет обработан в точке слева от узла, при обратном снизу от узла и при концевом, соответственно, справа от узла.
Другими словами «находясь» в некотором узле, нам нужно знать, нужно ли его обрабатывать и куда двигаться дальше.
Рекурсия
Все три варианта вертикального обхода элементарно реализуются рекурсивными функциями.
void recPreOrder() < treatment(); if (left!=null) left.recPreOrder(); if (right!=null) right.recPreOrder(); >void recInOrder() < if (left!=null) left.recInOrder(); treatment(); if (right!=null) right.recInOrder(); >void recPostOrder()
Рекурсия крайне удобна не только при обходе, но также при построении дерева, поиска в дереве, а также балансировки. Однако рекурсией нельзя осуществить горизонтальный обход дерева. В этом случае, а так же при обеспокоенности перегрузкой программного стека, следует применять итерационный подход.
Контейнеры
В случае использования итераций необходимо хранить сведенья о посещенных, но не обработанных узлах. Используются контейнеры типа стек (для вертикального обхода) и очередь (для горизонтального обхода).
Горизонтальный обход:
обрабатываем первый в очереди узел, при наличии дочерних узлов заносим их в конец очереди. Переходим к следующей итерации.
static void contLevelOrder(Node top) < Queuequeue=new LinkedList<> (); do< top.treatment(); if (top.left!=null) queue.add(top.left); if (top.right!=null) queue.add(top.right); if (!queue.isEmpty()) top=queue.poll(); >while (!queue.isEmpty()); > Вертикальный прямой обход:
обрабатываем текущий узел, при наличии правого поддерева добавляем его в стек для последующей обработки. Переходим к узлу левого поддерева. Если левого узла нет, переходим к верхнему узлу из стека.
static void contPreOrder(Node top) < Stackstack = new Stack<> (); while (top!=null || !stack.empty()) < if (!stack.empty())< top=stack.pop(); >while (top!=null) < top.treatment(); if (top.right!=null) stack.push(top.right); top=top.left; >> > Вертикальный обратный обход:
из текущего узла «спускаемся» до самого нижнего левого узла, добавляя в стек все посещенные узлы. Обрабатываем верхний узел из стека. Если в текущем узле имеется правое поддерево, начинаем следующую итерацию с правого узла. Если правого узла нет, пропускаем шаг со спуском и переходим к обработке следующего узла из стека.
static void contInOrder(Node top) < Stackstack = new Stack<> (); while (top!=null || !stack.empty()) < if (!stack.empty())< top=stack.pop(); top.treatment(); if (top.right!=null) top=top.right; else top=null; >while (top!=null) < stack.push(top); top=top.left; >> > Вертикальный концевой обход:
Здесь ситуация усложняется – в отличие от обратного обхода, помимо порядка спуска нужно знать обработано ли уже правое поддерево. Одним из вариантов решения является внесение в каждый экземпляр узла флага, который бы хранил соответствующую информацию (не рассматривается). Другим подходом является «кодирование» непосредственно в очередности стека — при спуске, если у очередного узла позже нужно будет обработать еще правое поддерево, в стек вносится последовательность «родитель, правый узел, родитель». Таким образом, при обработке узлов из стека мы сможем определить, нужно ли нам обрабатывать правое поддерево.
static void contPostOrder(Node top) < Stackstack = new Stack<> (); while (top!=null || !stack.empty())< if (!stack.empty())< top=stack.pop(); if (!stack.empty() && top.right==stack.lastElement())< top=stack.pop(); >else < top.treatment(); top=null; >> while (top!=null) < stack.push(top); if (top.right!=null)< stack.push(top.right); stack.push(top); >top=top.left; > > > Об указателе на родителя
Наличие в экземпляре класса указателя на родителя приносит определенные хлопоты при построении и балансировки деревьев. Однако, возможность из произвольного узла дерева «дойти» до любого из его узлов может придтись весьма кстати. Все, за чем нужно следить при «подъеме» на верхний уровень – пришли ли от правого потомка или от левого.
Так, с использованием родительских указателей будет выглядеть код вертикального концевого обхода.
static void parentPostOrder(Node top) < boolean fromright=false; Node shuttle=top, holder; while(true)< while (fromright)< shuttle.treatment(); if (shuttle==top) return; holder=shuttle; shuttle=shuttle.parent; fromright=shuttle.right==holder; if (!fromright && shuttle.right!=null) shuttle=shuttle.right; else fromright=true; >while (shuttle.left!=null) shuttle=shuttle.left; if (shuttle.right!=null) shuttle=shuttle.right; else fromright=true; > > Другой класс задач, которые позволяет решить родительский указатель, как уже было упомянуто — перемещение внутри дерева.
Так, что бы перейти на n-ый по счету узел от текущего узла, без «ориентации в дереве» пришлось бы обходить дерево с самого начала, до известного узла, а потом еще n-узлов. С использованием же родительского указателя при обратном обходе дерева перемещение на steps узлов от текущего узла (start) будет иметь следующий вид.
public static Node walkTheTree(Node start, int steps) < boolean fromright=true; Node shuttle=start, holder; if (shuttle.right!=null)< shuttle=shuttle.right; while (shuttle.left!=null) shuttle=shuttle.left; fromright=false; >int counter=0; do < while (true)< if (!fromright && ++counter==steps) return shuttle; if (!fromright && shuttle.right!=null)< shuttle=shuttle.right; break; >holder=shuttle; shuttle=shuttle.parent; fromright=(holder==shuttle.right); > while (shuttle.left!=null) shuttle=shuttle.left; >while (true); > Примечание: В общем случае также требуется предотвратить возможность попытки выхода за пределы дерева (подняться выше корневого узла).
Источник
3.7.2. Рекурсивные функции обхода бинарных деревьев
Первые три порядка обхода, которые приводятся в таблице 3.5, легко реализуются рекурсиным вызовом функции обхода для левого и правого поддеревьев в том порядке, которого требует алгоритм. Требуется только пояснить шаг «посетить корень». Поскольку обходы деревьев могут потребоваться для любой обработки значений, находящихся в узлах, то будем считать, что этот шаг обозначает именно ту обработку, которая нужна для конкретной задачи.
Функции имеют очень компактный код, который приведен в листинге 3.4, а для простоты предполагается, что вся обработка состоит только в выводе на экран значения, которое хранится в узле. Для того, чтобы сделать данные функции универсальными, можно добавить еще один параметр— внешнюю функцию Visit, в которой будет сосредоточена вся обработка узла.
Листинг 3.4. Реализация рекурсивных обходов бинарного дерева
// Дополнение к файлу bintree.cpp
void forward(bt t)//прямой порядок обхода
void reverse(bt t)// обратный порядок обхода
void central(bt t)// центрированный порядок обхода
Заметим, что обход в ширину не имеет простой рекурсивной реализации. Ниже мы приведем алгоритм обхода в ширину с использованием вспомогательной структуры данных — очереди.
3.7.3. Нерекурсивные функции обхода бинарных деревьев
Учитывая важность эффективной реализации обходов бинарных деревьев, рассмотрим нерекурсивный способ обходов, использующий цикл обхода по дереву. Вспомним, что рекурсивные функции используют внутренний (системный) стек программы, в который при каждом рекурсивном вызове помещается параметр (в данном случае указатель на узел) и адрес возврата. Следовательно, для реализации нерекурсивных алгоритмов логично использовать вспомогательный (внешний) стек, которая будет использоваться для тех же целей, что и системный стек программы в рекурсивных способах.
Введем вспомогательный стек s. При использовании языков высокого уровня мы не сможем в точности воспроизвести в нем содержимое системного стека, да это и не нужно. В литературе [8,10,14] приводятся различные алгоритмы нерекурсивного обхода, в которых вспомогательный стек используется только для хранения указателей на узлы дерева. Различные способы обхода различаются порядком, в котором эти указатели заталкиваются в стек и извлекаются из него.
Предположим, что уже имеется реализация шаблона стека с типом данных bt — указатель на узел бинарного дерева (для этого можно воспользоваться реализацией типа stack, которая была рассмотрена в предыдущей главе). Напомним базовые функции (методы) структуры stack:
push(p) – заталкиваем p в стек
pop() – извлекаем элемент с вершины стека
isnull() – проверяем стек на пустоту.
Наиболее прост в реализации алгоритм прямого обхода, который приводится в [14]. Напомним, что любая функция обхода получает в качестве параметра корень дерева. Поместим его в стек. Затем на каждом шаге итерации сначала извлекаем элемент с верхушки стека. При прямом обходе корень обрабатывается первым, после чего указатель на корень уже не нужен, а в стек помещается сначала указатель на правое поддерево, а затем на левое (пустые указатели в стек не помещаются). На следующем шаге итерации из стека извлекается и обрабатывается именно корень левого поддерева (он на вершине), после чего в стек заталкиваются указатели на его правое и левое поддеревья. Цикл повторяется до тех пор, пока стек не опустеет (это произойдет после извлечения крайнего правого листа). В листинге 3.5. приведена функция прямого обхода.
Листинг 3.5. Нерекурсивная реализация прямого обхода
void forwardstack(bt t) // нерекурсивный обход в прямом порядке
< stacks; // структура stack должна быть реализована!
Проанализируем выполнение данной функции, поскольку алгоритм достаточно универсален и его можно приспособить и для некоторых других видов обхода. Пусть функция применяется к дереву из семи узлов, которое изображено на рис.3.9. Тогда будет выполнено семь шагов цикла (итераций), а последовательность извлекаемых элементов и содержимое стека в начале каждого шага представлены в табл. 3.6. На каждом шаге итерации в стек добавляются поддеревья очередного узла (1,2 или 0 в зависимости от их количества) и извлекается ровно один узел с вершины.
Содержимое стека при прямом порядке обхода
Источник