Алгоритм обхода дерева

[Apostol]

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

[spectre71]

А по какому принципу ты хочешь сделать обход снизу-вверх?

[Авварон]

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

[spectre71]

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

[Apostol]

В случае нерекурсивного обхода сверху вниз вводим стек. Пихаем корень с стек. Пока стек не пуст: делаем pop, обрабатываем, push в стек все подвершины. По идее должно работать, придумано на коленке

Я что-то такое и предполагал, щас сижу этот алгоритм до конца прорабатываю.
сам узел дерева дан в такой форме:
struct Tree
{
   int data;
   Tree *left;
   Tree *right;
};
left и right - левый и правый ветви (дерево бинарное)
Идея такова. Два цикла. Первый имеет приоритет на левую ветвь дерева, идет сверху вниз. При этом все пройденные узлы загоняются в стек. Второй включается в работу как только достигли листа дерева. Второй идет снизу вверх, узлы берем из стека и т.д. до тех пор пока не получим пустой стек. Последнее значение, хранящееся в стеке, и будет корнем дерева.

[spectre71]

Не надо усложнять. "Авварон" тебе написал оптимальный нерекурсивный алгоритм обхода сверху вниз.
1) Береш Root запихиваешь в стек(List1)
2) Далее запускается цикл пока стек(List1) не пуст
3) - Делаем pop, получаем узел
    - Заносим узел во второй список(List2)
    - Заносим для узла его дочерние элементы в стек
4) После окончания цикла берем (List2) проходим от конца к началу.

Если надо обойти дерево снизу вверх по уровням, то в List2 заносим пару {узел, уровень}, а потом сортируем по уровню как надо.

[Авварон]

так list2 то не нужен, парсить можно в процессе обхода...

Код:

list <Node>stack;
stack.pushFront(root);
while(!stack.IsEmpty())
{
    Node current = stack.popFront();
    parseNode(current);
    foreach(Node child, current.children)
    {
        stack.pushFront(child);
    }
}

вот так вот как-то

[spectre71]

так list2 то не нужен, парсить можно в процессе обхода...

Ему нужен восходящий обход!

[Авварон]

я запутался) из поста 4 вроде следует обратное:)

[Apostol]

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

[Авварон]

аааа, то есть дан root дерева, но обойти надо снизу вверх слева направо?

[Apostol]

аааа, то есть дан root дерева, но обойти надо снизу вверх слева направо?

Так точно)

[Apostol]

Всем спасибо за ответы, задача решена, тема закрыта