Как нерекурсивно обойти дерево без стека?

agent007new

Что-то не гуглится решение. Нашел такой вот код:

 template<class T>

void walkNotRec(TNode<T>* tree) {

   if (tree) {

      TNode<T> temp;

      TNode<T>* ptemp = &temp;

      TNode<T>* p = ptemp, *c = tree, *w;

      while (c != ptemp) {

         cout << c->value;

         w = c->pleft;

         c->pleft = c->pright;

         if(c == p)

             c->pright = 0;

         else

             c->pright = p;         

         p = c;

         if (w) c = w;

         

      }

   }

} 

Но он неправильно работает. На дереве из трех узлов 2 корень, 1 и 3 листья выдает вот что: 211123332.
А в чем в нем косяк что-то не могу понять, т.к. не знаю даже идеи, как такой обход сделать

lubanj

нерекурсивно/без стека (что одно и тоже) никак, если в элементах нету ссылок на ихних предков

elenangel

реализуй свою очередь,
помести туда корень и далее
пока очередь не пуста
- берем ее элемент,
посещаем
помещаем в очередь элементы-потомки связанные с данным элементом.
переход к началу "пока".

lubanj

ну очередь наверное та же фигня будет. в смысле "задачка" подразумевает обход дерева вообще без использования памяти. в смысле О(1 а не О(d)
*существуют, если общее время решения, не О(N)

elenangel

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

lubanj

возможно! я же сказал - если в деревве есть ссылки вверх, а не только влево, вправо

ivanurgan

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

elenangel

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

bleyman

нерекурсивно/без стека (что одно и тоже) никак, если в элементах нету ссылок на ихних предков

У неё есть два известных мне существенно различных решения, О(1) по памяти, ссылок вверх нет. Одно есть в Кнуте, другое придумал , там всё как-то дико красиво автоматически получается, вот его достаточно потрассировать на бумажке чтобы восхититься!

apl13

возможно! я же сказал - если в деревве есть ссылки вверх, а не только влево, вправо

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

psihodog

я правильно понимаю, что там везде дерево само портится?

ppplva

Нет, оно в конце восстанавливается.

apl13

В принципе, если есть дополнительная информация вида "адреса TNode выровнены хотя бы по четным", то можно извратиться, только в определении TNode надо left и right объявить как void *.

Ivan8209

> Нет, оно в конце восстанавливается.
Его надо запирать даже на чтение.
---
"У нас ведь беда не в том, чтобы объединиться, а в том, кто главный."

rosali

> Его надо запирать даже на чтение.
не надо никого запирать, это же теория алгоритмов, а не программирование

Serab

Аппаратный стек — это еще не все // КО.