Нерекурсивный алгоритм обхода бинарного дерева

Содержание

Нерекурсивный обход бинарного дерева без стека
1 ответ 1
Нерекурсивные процедуры обхода бинарных деревьев
Русские Блоги
Нерекурсивный алгоритм обхода бинарного дерева (со стеком и очередью)

Нерекурсивный обход бинарного дерева без стека

Единственное, что смог найти по теме — обход Морриса, но данный алгоритм временно преобразует дерево в «прошитое» дерево, поэтому не подходит.

@VladD: Это не диссертация, я хочу разобраться с упражнением из книги Кормена. По условию константа ограничена глобально.

1 ответ 1

static void Walk(Node node) < Node lastNode = null; while (node != null) < if (lastNode == node.Parent) < if (node.Left != null) < lastNode = node; node = node.Left; continue; >else lastNode = null; > if (lastNode == node.Left) < Output(node); if (node.Right != null) < lastNode = node; node = node.Right; continue; >else lastNode = null; > if (lastNode == node.Right) < lastNode = node; node = node.Parent; >> >

Но, строго говоря, в BST ссылки на родителя нет, и обойти его без модификации дерева и с лимитом на память нельзя.

@DarkGenius очень легко. Алгоритим в процессе обхода дерева из N нод может находится в N различных состояниях. т.к. дерево модифицировать нельзя, то для описания состояния требуется дополнительной памяти log2(N) бит. Приведенный выше алгоритм не попадает под требования — он не заработает на количестве нод > 2^32 — т.к. он хранит состояние как int32.

@DarkGenius ну а если расход памяти log2(N) бит приемлем (читерство!), то достаточно просто написать функцию, которая будет идти по дереву, считать ноды (нерекурсивно), и выводить N-ю ноду. И вызвать ее с параметром от 1 до N. Т.е. теоретически лимит будет нарушаться, но на практике — нет (потому что такое дерево просто не влезет в память).

Эээ. Ну то, что указатель 32-битный, это читерство немного. Дерево с к-вом узлов > 2^32 нельзя даже представить в указанном виде, не то что обойти, т. к. на каждый узел должен быть указатель.

Источник

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

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

посетить корень – посетить (p);

пройти левое поддерево  if not Null (Left (p)) then S  (Left (p), 1);

пройти правое поддерево  if not Null (Right (p)) then S  (Right (p), 1).

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

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

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

var S: Stack of (BTree, operation);

p: BTree; op: operation ;

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

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

procedure обход_КЛП (b: BTree);

var S: Stack of BTree; p: BTree;

S:= Create; S  b;

while not Null (S) do

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

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

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

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

procedure обход_ЛКП (b: BTree);

var S: Stack of (BTree, operation);

p: BTree; op: operation ;

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)

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

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

procedure обход_ЛПК (b: BTree);

var S: Stack of (BTree, operation);

p: BTree; op: operation ;

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

while not Null (S) do

if op = 1 then

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

else if op = 2 then

S  (p, 3); if not Null (Right (p)) then S  (Right (p), 1)

end else op=3 > посетить (p)

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

procedure обход_горизонтальный (b: BTree);

var Q: queue of BTree;

while not Null (Q) do

if not Null (Left (p)) then Q  Left (p);

if not Null (Right (p)) then Q  Right (p)

Источник

Русские Блоги

Нерекурсивный алгоритм обхода бинарного дерева (со стеком и очередью)

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

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

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

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

#include"stack.h" template void BinaryTree::PreOrder(void (*visit)(BinTreeNode *p)) < stack S; BinTreeNode * p = root; // инициализация S.Push(NULL); while(p != NULL) < visit (p); // Посещаем узел if (p->rightChild! = NULL) S.Push (p-> rightChild); // Зарезервировать указатель левого поддерева в стеке if (p-> leftChild! = NULL) p = p-> leftChild; // В левое дочернее дерево else S.Pop (p); // Левое поддерево пусто > >

2. Обход порядка слоев

Обход порядка слоев начинается с корневого узла двоичного дерева и посещает каждый узел в дереве иерархически сверху вниз, слева направо.

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

#include"queue.h" template void BinaryTree::LevelOrder(void(*visit)(BinTreeNode *p)) < Queue Q; BinTreeNode *p = root; Q.EnQueue(p); while (! Q.IsEmpty ()) // Очередь не пуста < Q.DeQueue (p); // Выход из узла visit (p); // Посетить if (p->leftChild! = NULL) Q.EnQueue (p-> leftChild); // Левый дочерний элемент входит в команду if (p-> rightChild! = NULL) Q.EnQueue (p-> rightChild); // правый дочерний элемент входит в команду > >

3. Использование нерекурсивного алгоритма обхода по порядку стека.

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

Как показано на рисунке, в поддереве первым осуществляется доступ к первому узлу в среднем порядке. Он расположен в узле, который начинается от корня и идет по цепочке leftChild до нижнего левого угла. Указатель leftChild этого узла равен NULL. Получив доступ к его данным, пройдитесь по правому поддереву узла. Это правое поддерево снова является двоичным деревом, и описанный выше процесс повторяется до тех пор, пока поддерево не будет пройдено.

Если правое поддерево узла пройдено или правое поддерево пусто, это означает, что бинарное дерево с корнем в этом узле было пройдено. В это время выйдите из верхнего узла из стека и посетите его, а затем перейдите вправо Дерево пройдено.

#include"stack.h" template void BinaryTree::InOrder(void (*visit)(BinTreeNode *P)) < stack S; BinTreeNode * p = root; // p - указатель обхода do < while (p! = NULL) // Указатель обхода не достиг нижнего левого узла, не пуст < S.Push (p); // Поддерево по пути помещается в стек p = p->leftChild; // Перемещаем указатель на левый дочерний узел > if (! S.IsEmpty ()) // Выход, когда стек не пуст < S.Pop (p); // Разложить visit (p); // Посещаем корневой узел p = p->rightChild; // Перемещаем указатель к правому дочернему узлу > >while(p != NULL || ! S.Empty()); >

Условие завершения алгоритма: стек пуст, и указатель обхода также пуст. Стек становится пустым, когда корневой узел посещается на полпути, но на этот раз указатель обхода указывает на правый дочерний узел корня. Если указатель не пустой, это означает, что правое поддерево не пусто, а правое поддерево корня необходимо пройти.

4. Используйте пост-порядок стека для обхода нерекурсивных алгоритмов.

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

template struct stkNode

В алгоритме сначала используйте стек для временного хранения адреса корневого узла, а затем перейдите к левому поддереву. В это время тег корневого узла = L. Когда узел в левом поддереве посещается и возвращается из левого поддерева, go Пройдите по правому поддереву корня, в это время измените тег корневого узла = R и получите доступ только к значению корневого узла в верхней части стека при выходе из правого поддерева.

#include"stack.h" template void BinaryTree::PostOrder(void(*visit)(BinTreeNode*p))< Stack S; stkNode w; BinTreeNode * p = root; // p - указатель обхода do < while(p != NULL)< w.ptr = p; w.tag = L; S.Push(w); p = p->leftChild; // Спустимся к нижнему левому узлу > int continue1 = 1; // Продолжаем до метки цикла, используемой для R while(continue1 && !S.Empty()) < S.Pop (w); // Стек не пустой, выходим из стека p = w.ptr; switch (w.tag) rightChild; // Спускаемся из правого дочернего дерева break; case R: visit (p); // Вернемся из правого поддерева и посетим корневой узел break; > > while (! S.Empty ()); // Есть еще узлы, которые не прошли, продолжаем цикл cout

Источник