|
Название: Алгоритм обхода дерева Отправлено: Apostol от Июнь 17, 2009, 15:29 Не могу никак найти нерекурсивный алгоритм восходящего (снизу-вверх) обхода дерева... Пересмотрел кучу книг, в них только алгоритмы для нисходящего обхода. Может кто знает как его реализовать или где посмотреть как он реализуется? Как я понял, для обхода нужно использовать стек, но как им воспользоваться для данного случая ума не приложу. Нужен именно нерекурсивный (невложенный) алгоритм обхода...
Название: Re: Алгоритм обхода дерева Отправлено: spectre71 от Июнь 17, 2009, 15:40 А по какому принципу ты хочешь сделать обход снизу-вверх?
Название: Re: Алгоритм обхода дерева Отправлено: Авварон от Июнь 17, 2009, 15:55 видимо известны все листовые вершины, к примеру в виде списка.тогда. обработать текущую пока у текущей вершины есть парент, текущая стала парентом, а прошлую текущую в список обработанных. Таким образом нужно проверять не обработали ли уже эту вершину. Когда парента нет (достигли корня) или текущая уже обработана, то переходим к следующей из входного списка вершин. Но что-то как-то бредово звучит сама задача.
В случае нерекурсивного обхода сверху вниз вводим стек. Пихаем корень с стек. Пока стек не пуст: делаем pop, обрабатываем, push в стек все подвершины. По идее должно работать, придумано на коленке Название: Re: Алгоритм обхода дерева Отправлено: spectre71 от Июнь 17, 2009, 15:59 Проще пройтись по узлам сверху-вниз занося их в список. После этого обрабатывать элементы списка от конца к началу.
Название: Re: Алгоритм обхода дерева Отправлено: Apostol от Июнь 17, 2009, 16:18 В случае нерекурсивного обхода сверху вниз вводим стек. Пихаем корень с стек. Пока стек не пуст: делаем pop, обрабатываем, push в стек все подвершины. По идее должно работать, придумано на коленке Я что-то такое и предполагал, щас сижу этот алгоритм до конца прорабатываю.сам узел дерева дан в такой форме: struct Tree { int data; Tree *left; Tree *right; }; left и right - левый и правый ветви (дерево бинарное) Идея такова. Два цикла. Первый имеет приоритет на левую ветвь дерева, идет сверху вниз. При этом все пройденные узлы загоняются в стек. Второй включается в работу как только достигли листа дерева. Второй идет снизу вверх, узлы берем из стека и т.д. до тех пор пока не получим пустой стек. Последнее значение, хранящееся в стеке, и будет корнем дерева. Название: Re: Алгоритм обхода дерева Отправлено: spectre71 от Июнь 17, 2009, 16:39 Не надо усложнять. "Авварон" тебе написал оптимальный нерекурсивный алгоритм обхода сверху вниз.
1) Береш Root запихиваешь в стек(List1) 2) Далее запускается цикл пока стек(List1) не пуст 3) - Делаем pop, получаем узел - Заносим узел во второй список(List2) - Заносим для узла его дочерние элементы в стек 4) После окончания цикла берем (List2) проходим от конца к началу. Если надо обойти дерево снизу вверх по уровням, то в List2 заносим пару {узел, уровень}, а потом сортируем по уровню как надо. Название: Re: Алгоритм обхода дерева Отправлено: Авварон от Июнь 17, 2009, 17:25 так list2 то не нужен, парсить можно в процессе обхода...
Код: list <Node>stack; Название: Re: Алгоритм обхода дерева Отправлено: spectre71 от Июнь 17, 2009, 18:20 так list2 то не нужен, парсить можно в процессе обхода... Ему нужен восходящий обход! Название: Re: Алгоритм обхода дерева Отправлено: Авварон от Июнь 17, 2009, 18:33 я запутался) из поста 4 вроде следует обратное:)
Название: Re: Алгоритм обхода дерева Отправлено: Apostol от Июнь 17, 2009, 18:45 Тэксс. Свой одностековый алгоримт я реализовал, гуд работает (хоть и замудренный он получился), щас бум пробовать 2х стековый spectre71 ;)
Название: Re: Алгоритм обхода дерева Отправлено: Авварон от Июнь 17, 2009, 19:44 аааа, то есть дан root дерева, но обойти надо снизу вверх слева направо?
Название: Re: Алгоритм обхода дерева Отправлено: Apostol от Июнь 17, 2009, 20:06 аааа, то есть дан root дерева, но обойти надо снизу вверх слева направо? Так точно)Название: Re: Алгоритм обхода дерева Отправлено: Apostol от Июнь 18, 2009, 10:38 Всем спасибо за ответы, задача решена, тема закрыта :)
|