ANSI C: Walking tree

[theukrainian]

Наличие ссылки *parent

ааааа. я эту ссылку не заметил и начал разговоры разговаривать м-да.

[olg2002]

Посмотрел еще раз - все могу повторить то же самое. Главное - цикл бесконечный на 4-5-4-5-4-5-4-5-4-5-.... (ну, вижу я это без компьютера ), не считая также не вполне правильных промежуточных результатов. То есть, алгоритм не выдает конечного результата вообще. У нас в школе с этим было строго: нет результата - оценка -1...

Упорствуете в том, что не можете понять, как работает программа в 10 строк? Не пожалейте времени, напишите программу.

P.S. Анекдот. На выставке абстракциониста посетитель спрашивает, почему на его картинах ничего не понятно. "Понимаете, я ТАК вижу." - отвечает художник. "Зачем же ты рисуешь, если так плохо видишь?"

[SVK]

Не пожалейте времени, напишите программу.

Трассировка:

Code: Select all

cur---statement
. . . . . . . . . . . начало пропущено до момента cur=4 
4-----while ( cur ) { 
4-----process( cur ); 
4-----if ( cur->child ) { 
4-----cur = cur->child; 
5-----continue; 
5-----while ( cur ) { 
5-----process( cur ); 
5-----if ( cur->child ) { 
5-----}
5-----while ( cur ) { 
5-----if ( cur->next ) { 
5-----}
5-----cur = cur->parent;
4-----}
4-----while ( cur ) { 
4-----process( cur ); 
4-----if ( cur->child ) { 
4-----cur = cur->child; 
5-----continue; 
5-----while ( cur ) { 
5-----process( cur ); 
5-----if ( cur->child ) { 
5-----}
5-----while ( cur ) { 
5-----if ( cur->next ) { 
5-----}
5-----cur = cur->parent;
4-----}
. . . . . . и т.д., пока хватит сил....

Ну, не надо еще с анекдотами путаться...

[vc]

Посмотрел еще раз - все могу повторить то же самое. Главное - цикл бесконечный на 4-5-4-5-4-5-4-5-4-5-.... (ну, вижу я это без компьютера ...

I think you need a new eye-glass prescription. olg2002's solution should produce correct results for the binary tree pre-order traversal.

With a minor tweak, it will work for subtrees as well:

Code: Select all

Node *cur=root; 
while ( cur ) { 
    process( cur ); 
    if ( cur->child ) { 
        cur = cur->child; 
        continue; 
    } 
    while ( cur && cur != root ) { 
        if ( cur->next ) { 
            cur = cur->next; 
            break; 
        } 
        cur = cur->parent; 
    } 
    if (cur == root) break;
} 

VC

[olg2002]

[quote="SVK"][/quote]

Вы руками что ли эту трассировку писали? Как это вы из внутреннего цикла вдруг во внешний выскочили?
Ладно, не можете сами написать, попробуйте откомпилировать мою:

Code: Select all

#include <stdio.h>

typedef struct Node Node;

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

Node nd2, nd3, nd4, nd5, nd6, nd7, nd8, nd9, nd10, nd11, nd12, nd13;

Node nd1  = { NULL,  &nd2,  NULL,   1 };
Node nd2  = { &nd6,  &nd3,  &nd1,   2 };
Node nd3  = { &nd7,  &nd4,  &nd2,   3 };
Node nd4  = { &nd8,  &nd5,  &nd3,   4 };
Node nd5  = { NULL,  NULL,  &nd4,   5 };
Node nd6  = { &nd9,  NULL,  &nd1,   6 };
Node nd7  = { NULL,  NULL,  &nd2,   7 };
Node nd8  = { &nd10, NULL,  &nd3,   8 };
Node nd9  = { NULL,  NULL,  &nd1,   9 };
Node nd10 = { NULL,  &nd11, &nd3,  10 };
Node nd11 = { &nd13, &nd12, &nd10, 11 };
Node nd12 = { NULL,  NULL,  &nd11, 12 };
Node nd13 = { NULL,  NULL,  &nd10, 13 };
Node *root = &nd1;

void
process( Node *nd )
{
    printf("%d\n", nd->key );
}

int
main()
{  
    Node *cur=root;
    while ( cur ) {
        process( cur );
        if ( cur->child ) {
            cur = cur->child;
            continue;
        }
        while ( cur ) {
            if ( cur->next ) {
                cur = cur->next;
                break;
            }
            cur = cur->parent;
        }
    }
    return 0;
}

Сообщите о результатах.

[tengiz]

A. Fig Lee - а как обходить дерево в условии задачи не задано? Приведённый нерекурсивный алгоритм обходит эту структуру вполне определённым образом. Любой другой обход потребует дополнительной памяти либо в виде стека для рекурсии, либо в виде программного стека/очереди.

Если нужно делать программный стек, но не хочется хипа, то в таких задачах часто удобно использовать alloca. Дополнительной памяти обычно нужно под столько указателей, какова высота дерева. Т.е. заметно меньше, чем под дополнительный parent указатель в каждом узле.

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

Или если нужен итератор, умеющий переходить на следующий узел, причём таких итераторов для одного и того же дерева в программе нужно много.

P.S. A. Fig Lee - пожалуйста перестаньте хулиганить и исправьте название дискуссии, а то из-за пропущенного неопределённого артикля получается "Дерево на прогулке" вместо "Обхода дерева". В результате сбивает с толку и не привлекает должного внимания. Или наоборот, потенциально может привлечь любознательных ботаников, а не софтверных инженеров .

[vc]

Не пожалейте времени, напишите программу.

Трассировка:

Code: Select all

cur---statement
. . . . . . . . . . . начало пропущено до момента cur=4 
4-----while ( cur ) { 
4-----process( cur ); 
4-----if ( cur->child ) { 
4-----cur = cur->child; 
5-----continue; 
5-----while ( cur ) { 
5-----process( cur ); 
5-----if ( cur->child ) { 
5-----}
5-----while ( cur ) { 
5-----if ( cur->next ) { 
5-----}
5-----cur = cur->parent;
4-----}
4-----while ( cur ) { 
4-----process( cur ); 
4-----if ( cur->child ) { 
4-----cur = cur->child; 
5-----continue; 
5-----while ( cur ) { 
5-----process( cur ); 
5-----if ( cur->child ) { 
5-----}
5-----while ( cur ) { 
5-----if ( cur->next ) { 
5-----}
5-----cur = cur->parent;
4-----}
. . . . . . и т.д., пока хватит сил....

Ну, не надо еще с анекдотами путаться...

Here's the correct trace:

Code: Select all

...............................
cur=4 
4-----while ( cur ) { 
4-----process( cur ); 
4-----if ( cur->child ) { 
4-----cur = cur->child; 
5-----continue; 
5-----while ( cur ) { 
5-----process( cur ); 
5-----if ( cur->child ) { 
5-----} 
5-----while ( cur ) { 
5-----if ( cur->next ) { 
5-----} 
5-----cur = cur->parent; 
4-----} 
4-----while ( cur ) { 
4-----if ( cur->next ) {
8-----cur = cur->next;
8-----break;
8-----while ( cur ) 
8-----process(cur) 
...........  etc  ........

With an attitude like that, you'd better be 100% sure you are right ...

VC

[SVK]

With an attitude like that, you'd better be 100% sure you are right ...

Да. Заслуживаю общественное порицание, и оценку -2. Рассматривал код со сдвинутым концом цикла - сам виноват, каюсь.

[SVK]

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

Не только для такого случая. Некоторые виды обработки могут требовать просто "подъема" начиная с нижних уровней дерева к верхним. Для такого типа проходов указатели parent все равно нужны. А коли они уже есть в структуре (а по условию дано, что они все-таки есть), то грех не использовать их, а строить стек даже и при стандартном обходе дерева.

Не так разве?

[8K]

Самый красивый алгоритм вычисления факториала

А слабо написать compile-time факториал, чтобы его компилятор в момент компиляции считал, если N - константа? Правда, под нашим VC++ все равно не работает, т.к. реализация шаблонов кривая.

[tengiz]

Не только для такого случая. Некоторые виды обработки могут требовать просто "подъема" начиная с нижних уровней дерева к верхним. Для такого типа проходов указатели parent все равно нужны. А коли они уже есть в структуре (а по условию дано, что они все-таки есть), то грех не использовать их, а строить стек даже и при стандартном обходе дерева.

Не так разве?

Не уверен, что я точно понимаю, что Вы имеете в виду под подъёмом начиная с нижних уровней (с чего в этом случае начинается обход - со списка внешних узлов, т.е. самого нижнего уровня?). Но я, конечно, не буду спорить, что в жизни могут попасться самые причудливые задачи - здесь Вы абсолютно правы. Но то что я имел в виду всё-так сводится к стандартным базовым вариантам обхода дерева: pre-/in-/post-order начиная с корня дерева и различные их модификации, включая обход statefull итераторами.

[SVK]

что Вы имеете в виду под подъёмом начиная с нижних уровней (с чего в этом случае начинается обход - со списка внешних узлов, т.е. самого нижнего уровня?).

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

[olg2002]

Ну, с простым случаем, вижу, разобрались. Как насчет того же самого, но без parent ссылки? Приглашаю всех в "Головоломки".

[theukrainian]

Ну, с простым случаем, вижу, разобрались. Как насчет того же самого, но без parent ссылки? Приглашаю всех в "Головоломки".

теперь - стэк

[vc]

Tengiz,

A. Fig Lee - а как обходить дерево в условии задачи не задано? Приведённый нерекурсивный алгоритм обходит эту структуру вполне определённым образом. Любой другой обход потребует дополнительной памяти либо в виде стека для рекурсии, либо в виде программного стека/очереди.

.

The task is ambiguous as to what the Parent link really means:

1. The structure Node( Next, Child, Parent, Key) clearly represents an _ordered_ tree node but it's not clear what's considered to be the parent;

2. The usual interpretation would be :
(null,2,null, 1), (6,3,1,2), (7,4,2,3), (8,5,3,4), (null,null,4,5), (9,null, 2, 6),
(null,null,3,7),(10,null,4,8 ), ... etc.

Assuming the above interpretation is correct and remembering than any ordered tree is equivalent to a binary tree, all the DFS traversals (pre/post/in-order) can be expressed iteratively.

3. An alternative interpretation assumed by SVK was:
(null,2,null, 1), (6,3,1,2), (7,4,2,3), (8,5,3,4), (null,null,4,5), (9,null, 1, 6),
(null,null,2,7),(10,null,3,8 ), ... etc.

In this case, only the pre-order traversal can be iterative and the other traversals can be implemented trivially over the equivalent binary tree using the standard recursive approach or a manual stack (which is the same as recursion).

As to the interview ... I would not want to work for someone asking this kind of a silly question at an interview unless the pay was really good.

Regards.

VC