Обход бинарных деревьев: рекурсия, итерации и указатель на родителя
Основы о бинарных деревьях представлены, в том числе, здесь . Добавлю свои «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); > Примечание: В общем случае также требуется предотвратить возможность попытки выхода за пределы дерева (подняться выше корневого узла).
Источник
Семейство алгоритмов обхода дерева Вахнина, с дополнительной памятью, не зависящей от размера дерева
Определение левостороннего обхода в прямом порядке: обрабатываем родителя, левое поддерево, правое поддерево (применяем рекурсивно).
В структуре дерева применяются ссылки на левое и правое поддерево. У конечных сыновей эти ссылки — пустые. Их можно использовать для прошивки дерева, позволяющею обойти дерево левосторонним способом. После обхода дерево можно и нужно расшить, для приведения в изначальное состояние. Для обозначения ссылок прошивки дерева есть два способа: 1. Ссылка на заведенный специально элемент — маркер. 2. Обе ссылки прошивки указывают на один и тот же элемент, который обходится следующим. В описание алгоритма будем использовать способ с элементом-маркером.
Определение «по возможности влево ( вправо)»: идем до развилки, на развилке выбираем левого ( правого ) сына. Продолжаем с начала определения. Элемент, не имеющий сыновей — искомый.
Описание прошивки дерева: Помним, при предыдущих действиях, «корень предыдущего правого поддерева» ( в самом начале «корень предыдущего правого поддерева» — пусто, что и будет являться признаком конца обхода ). Идем до развилки «по возможности влево», если пришли к конечному элементу, берем «корень предыдущего правого поддерева» и продолжаем с начала описания прошивки дерева ( «корень предыдущего правого поддерева» делаем пустым ). На развилке идем «по возможности вправо» до конечного элемента. У этого оконечного элемента обе ссылки на сыновей — пусты ( этот элемент обходится последним в поддереве, при левостороннем обходе в прямом порядке ). Левую делаем указующую на «корень предыдущего правого поддерева», а правую делаем указующую на элемент-маркер. Правого сына у развилки запоминаем как текущий «корень предыдущего правого поддерева». Переходим к левому сыну и продолжаем с начала описания прошивки дерева.
Описание обработки дерева с расшивкой: обрабатываем текущий узел. Если у узла больше нет сыновей — конец обхода, все дерево обработано. Если сын один — переходим к обработке и продолжаем с начала описания. Если сына два и правая ссылка ссылается на элемент-маркер, переходим к обработке левого поддерева, делаем обе ссылки пустыми и продолжаем с начала описания. Если сына два и правая ссылка не ссылается на элемент-маркер, переходим к обработке левого поддерева и продолжаем с начала описания.
Как легко видно, при применении данных описаний прошивки и обхода с расшивкой, все элементы дерева будут обработаны в порядке левостороннего обхода и, в конце, дерево вернется в первоначальную структуру. Что интересно, прошивку, обработку и расшивку можно совместить в одном алгоритме, описанном ниже.
Описание обработки дерева: обрабатываем текущий узел. Если у узла нет больше сыновей — конец обхода, все дерево обработано. Если сын один — переходим к обработке и продолжаем с начала описания. Если сына два и правая ссылка ссылается на элемент-маркер, переходим к обработке левого поддерева, делаем обе ссылки пустыми и продолжаем с начала описания. Если сына два и правая ссылка не ссылается на элемент-маркер, делаем ссылки последнего в обходе поддерева узла ( его можно найти, если пройти по «возможности вправо» ), ссылающимися на: правую на элемент-маркер, левую на «корень предыдущего поддерева». Запоминаем правого сына как «корень предыдущего правого поддерева». Переходим к обработке левого поддерева и продолжаем с начала описания.
Существуют вариации описанного алгоритма для симметричного обхода и обратного.
P.S. Данный алгоритм читается, в рамках курса «Теория алгоритмов» на Математико-Механическом факультете Санкт-Петербургского Государственного факультета. Как представитель автора, претендую на инвайт. Полномочия могу подтвердить.
P.P.S. Данный пост претендует на хаб Big Data, потому что описанный алгоритм может быть использован при экстренной сборке мусора.
Источник