ANSI C: Walking tree

[A. Fig Lee]

Задали задачу:
ANSI C, no recursive calls, write function to walk tree.

struct {
Node *next;
Node *child;
Node *parent;
int key} Node;

Не вижу решения, если хип не пользовать.
Any ideas?

[Strannik223]

Задали задачу:
ANSI C, no recursive calls, write function to walk tree.

struct {
Node *next;
Node *child;
Node *parent;
int key} Node;

Не вижу решения, если хип не пользовать.
Any ideas?

Задача сводится к написанию стека. Если максимальная глубина дерава известна, то можно вместо стека использовать массив и int как указатель стека.

[A. Fig Lee]

Задали задачу:
ANSI C, no recursive calls, write function to walk tree.

struct {
Node *next;
Node *child;
Node *parent;
int key} Node;

Не вижу решения, если хип не пользовать.
Any ideas?

Задача сводится к написанию стека. Если максимальная глубина дерава известна, то можно вместо стека использовать массив и int как указатель стека.

Ничего неизвестно. И что знацит - написание стека? Ето С, не С++.

[Strannik223]

Ничего неизвестно. И что знацит - написание стека? Ето С, не С++.

Эээ а что стек это понятие не из области структур данных, а из C++?

Ну значит прийдется тебе и reallocate вызывать когда надо будет.
Как известно (?) рекурсии заменяются алгоритмами с циклом и стеком. Что то вроде (pseudocode)

Code: Select all

push(*myRoot);
while ((TreeNode tn = pop()) != null) {
  foreach(TreeNode child = getChildList(tn))
    push(child);
  printf(tn->name);
}

push() & pop() - домашнее задание.
В push проверять не исчерпалась ли память стека и делать reallocate() если да. Без динамической памяти не обойтись, или по-тупому, зарезервировать массив побольше

[A. Fig Lee]

Ничего неизвестно. И что знацит - написание стека? Ето С, не С++.

Эээ а что стек это понятие не из области структур данных, а из C++?

Ну значит прийдется тебе и reallocate вызывать когда надо будет.
Как известно (?) рекурсии заменяются алгоритмами с циклом и стеком. Что то вроде (pseudocode)

Code: Select all

push(*myRoot);
while ((TreeNode tn = pop()) != null) {
  foreach(TreeNode child = getChildList(tn))
    push(child);
  printf(tn->name);
}

push() & pop() - домашнее задание.
В push проверять не исчерпалась ли память стека и делать reallocate() если да. Без динамической памяти не обойтись, или по-тупому, зарезервировать массив побольше

Ну а next то где? Чайлд то не проблема - там парент есть, никаких пушей не надо.
Если я пошел на нехт, мне надо предыдущеий пойнт запоминать, потому что превиоус нету. А таких может быть арбитрари количество.

[Strannik223]

Тутачки он.
TreeNode tn = pop()

[A. Fig Lee]

Хммм...
Пушнули_рут->понули_рут->пуш_чайлд_1->пуш_чайлд_2->пуш_чайлд_3->поп_чаилд_3-> теперь ето рут, а где ж на нехт ветку переход?

Вот нарисовал диагграммку. не вижу как по такой схеме можно попасть на елемент 6 (ето некст для 2, 2 - чайлд 1-го).

[olg2002]

Одно из счастливых воспоминаний детства - реализация рекурсивных алгоритмов на Фортране: с циклами, стеками-массивами для аргументов, локалов и - главное - точек возврата. Если человек не понимал framework-а, программа была совершенно не читабельна, хотя и вполне структурирована.

В данной задаче, если бы мы решали ее с помощью рекурсивной функции, у нас было бы два рекурсивных вызова в ее теле: один для child, другой для next. В этом основная трудность: кроме стека аргументов, нам нужен еще стек точек возврата. Очень хорошая задача на понимание рекурсии!

[A. Fig Lee]

В данной задаче, если бы мы решали ее с помощью рекурсивной функции, у нас было бы два рекурсивных вызова в ее теле: один для child, другой для next. В этом основная трудность: кроме стека аргументов, нам нужен еще стек точек возврата. Очень хорошая задача на понимание рекурсии!

Так отож! С рекурсией-то проблем нет - ето был предыдущий вопрос.
Интересно кстати, как Странник представляет себе реализацию стека без хипа.
Мне кроме сложных манипулаций с varg идеи не лезут...

[SVK]

А при чем тут стек-нестек? Коли дана структура со ссылками - значит ее кто-то как-то построил в таком виде, и надо просто ее обойти, не пользуясь рекурсией и любыми не-ANSI прибамбасами. Разве не это требуется?

По-моему, так (если я чего-то не перепутал):

Code: Select all

struct { 
   Node *next; 
   Node *child; 
   Node *parent; 
   int key;
} Node; 

bool walkTree( Node *top )
{
   Node *current = top;
   bool goUp = false;

   while(current && (!goUp || current != top) )
   {
      if ( !goUp ) 
         handleNode(current);

      if (!goUp && current->child) {
         current = current->child;
         goUp = false;
      } else if (current->next) {
         current = current->next;
         goUp = false;
      } else {
         current = current->parent;
         goUp = true;
      }
   }
   return (current == top);
}

[A. Fig Lee]

А при чем тут стек-нестек? Коли дана структура со ссылками - значит ее кто-то как-то построил в таком виде, и надо просто ее обойти, не пользуясь рекурсией и любыми не-ANSI прибамбасами. Разве не это требуется?

По-моему, так (если я чего-то не перепутал):

Code: Select all

struct { 
   Node *next; 
   Node *child; 
   Node *parent; 
   int key;
} Node; 

bool walkTree( Node *top )
{
   Node *current = top;
   bool goUp = false;

   while(current && (!goUp || current != top) )
   {
      if ( !goUp ) 
         handleNode(current);

      if (!goUp && current->child) {
         current = current->child;
         goUp = false;
      } else if (current->next) {
         current = current->next;
         goUp = false;
      } else {
         current = current->parent;
         goUp = true;
      }
   }
   return (current == top);
}

Специально три нарисовал, чтоб легче разбиратся.
После 1->2->3->4->5->4->8->10 обратно к ветке 3->7 Вы уже не вернетесь - нет операции обраной некст. А надо бы попапмуть до 3.

[Strannik223]

push(root).
In stack: 1.

loop1
pop() // stack empty
foreach(TreeNode child = getChildList(tn)) // 2,6,9
print: 1

loop2
pop() // 6,9
child() // 3,6,9
print : 2

loop3
pop() //6,9
child() // 4,6,9
print: 3

loop4
pop() //6,9
child() //5,6,9
print: 4

loop5
pop() // 6,9
child() // none: 6,9
print: 5

loop6
pop() // 9
child() // 7, 9
print: 6

loop7:
pop(): // 9
child() : // 8,9
print 7

loop8
pop() // 9
child() // none: 9
print 8

loop9
pop() //empty
child()// none
print 9

end.

...

Достаточно?
Я не понял чей чилд 10-ка.

[SVK]

Специально три нарисовал, чтоб легче разбиратся.
После 1->2->3->4->5->4->8->10 обратно к ветке 3->7 Вы уже не вернетесь - нет операции обраной некст. А надо бы попапмуть до 3.

На картинке нет ссылок - непонятно, кто кому сын?

Если дорисовать ссылки, то обход дерева должен быть правильным. Я так думаю

[Strannik223]

А при чем тут стек-нестек? Коли дана структура со ссылками - значит ее кто-то как-то построил в таком виде, и надо просто ее обойти, не пользуясь рекурсией и любыми не-ANSI прибамбасами. Разве не это требуется?

По-моему, так (если я чего-то не перепутал):

Code: Select all

struct { 
   Node *next; 
   Node *child; 
   Node *parent; 
   int key;
} Node; 

bool walkTree( Node *top )
{
   Node *current = top;
   bool goUp = false;

   while(current && (!goUp || current != top) )
   {
      if ( !goUp ) 
         handleNode(current);

      if (!goUp && current->child) {
         current = current->child;
         goUp = false;
      } else if (current->next) {
         current = current->next;
         goUp = false;
      } else {
         current = current->parent;
         goUp = true;
      }
   }
   return (current == top);
}

А когда перешли вверх, то что, колбасим весь уровень с начала?
Это вечный цикл, или я что то проглядел?

[A. Fig Lee]

Strannik, не так.
все что направо - ето некст тех елементов, которые слева.
Которые внизы - чайлды тех елементов, кто над ними.
То есть добавить -> между квадратами для некст и стрелка вниз для чайлдов (только вниз, не вправо, ни влево). ну лень рисовать было.

[SVK]

А когда перешли вверх, то что, колбасим весь уровень с начала?
Это вечный цикл, или я что то проглядел?

Когда перешли вверх (goUp), то идем вправо, если можно. Если нельзя вправо, то идем дальше вверх - не далее чем начальный *top.

Не будет бесконечного цикла.

[Strannik223]

В данной задаче, если бы мы решали ее с помощью рекурсивной функции, у нас было бы два рекурсивных вызова в ее теле: один для child, другой для next. В этом основная трудность: кроме стека аргументов, нам нужен еще стек точек возврата. Очень хорошая задача на понимание рекурсии!

Так отож! С рекурсией-то проблем нет - ето был предыдущий вопрос.
Интересно кстати, как Странник представляет себе реализацию стека без хипа.
Мне кроме сложных манипулаций с varg идеи не лезут...

А что, надо еще и без хипа?

[SVK]

Strannik, не так.
все что направо - ето некст тех елементов, которые слева.
Которые внизы - чайлды тех елементов, кто над ними.
То есть добавить -> между квадратами для некст и стрелка вниз для чайлдов (только вниз, не вправо, ни влево). ну лень рисовать было.

Например: 7 - это child от 6, или next от 3???

[A. Fig Lee]

Да, картинка плохая. Вот лучше. Красные стрелки - К нексту, зеленые - К чайлдам (от родителей).

[SVK]

Да, картинка плохая. Вот лучше. Красные стрелки - К нексту, зеленые - К чайлдам (от родителей).

Я понял, что сбивало с толку - отсутствие стрелок parent. Без них нужна рекурсия, а с правильными parents - будет работать, как я написал

[A. Fig Lee]

А что, надо еще и без хипа?

Дак а с хипом то - какая разница, можно просто realloc().
Вообще если хипом, задачу можно решить, но изврат какой-то получается..

[Strannik223]

А когда перешли вверх, то что, колбасим весь уровень с начала?
Это вечный цикл, или я что то проглядел?

Когда перешли вверх (goUp), то идем вправо, если можно. Если нельзя вправо, то идем дальше вверх - не далее чем начальный *top.

Не будет бесконечного цикла. :umnik1:

Да, теперь понял, должно работать.

[A. Fig Lee]

Да, картинка плохая. Вот лучше. Красные стрелки - К нексту, зеленые - К чайлдам (от родителей).

Я понял, что сбивало с толку - отсутствие стрелок parent. Без них нужна рекурсия, а с правильными parents - будет работать, как я написал

ne budet. Once you got right, you may no go back left.

после 4-го попадет на 8-й и никогда не выберется до 3->7

[SVK]

Да, картинка плохая. Вот лучше. Красные стрелки - К нексту, зеленые - К чайлдам (от родителей).

Я понял, что сбивало с толку - отсутствие стрелок parent. Без них нужна рекурсия, а с правильными parents - будет работать, как я написал

ne budet. Once you got right, you may no go back left.

Чем спорить на словах, я предлагаю дорисовать правильные parents и убедиться, что будет работать

[Strannik223]

Да, картинка плохая. Вот лучше. Красные стрелки - К нексту, зеленые - К чайлдам (от родителей).

Я понял, что сбивало с толку - отсутствие стрелок parent. Без них нужна рекурсия, а с правильными parents - будет работать, как я написал :gen1:

ne budet. Once you got right, you may no go back left.

после 4-го попадет на 8-й и никогда не выберется до 3->7

Не понял, у 6,7,8 parent == NULL ?!!!