ANSI C: Walking tree

[SVK]

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

По-правильному,
parent для 2, 6 и 9 - есть 1
parent для 3 и 7 - есть 2
parent для 4, 8 и 10 - есть 3
parent для 5 - есть 4
parent для 11 и 13 - есть 10
parent для 12 - есть 11
(хотя конкретно тут parent для "промежуточных" next-ов роли не играет)

[A. Fig Lee]

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

Ето интересный вопрос. логически парент должен быть.... Ну если будет парент, тогда ето чайлд.. Хммм... Наверное, ето и имелось ввиду...
Хотя конечно могут быть и без парент. Живой пример - MIME аттачменты друг в дружку. Тогда не получится
Ок. Всем спасибо за внимание.

[A. Fig Lee]

Вообще лучше было бы назвать right i left. было бы четко и понятно.
иначе путаница выходит.

[SVK]

Ето интересный вопрос. логически парент должен быть.... Ну если будет парент, тогда ето чайлд.. Хммм... Наверное, ето и имелось ввиду...
Хотя конечно могут быть и без парент. Живой пример - MIME аттачменты друг в дружку. Тогда не получится
Ок. Всем спасибо за внимание.

Наличие ссылки parent - это здесь основа для нерекурсивных алгоритмов. Без этих дополнительных ссылок требуется рекурсия, либо всякие стеки-нестеки, и прочее фуфло.

[SVK]

Вообще лучше было бы назвать right i left. было бы четко и понятно.
иначе путаница выходит.

Нет, в этом контексте как раз right-left будет сбивать с толку. Как задано в задаче - это наиболее вразумительные обозначения.

[A. Fig Lee]

Ето интересный вопрос. логически парент должен быть.... Ну если будет парент, тогда ето чайлд.. Хммм... Наверное, ето и имелось ввиду...
Хотя конечно могут быть и без парент. Живой пример - MIME аттачменты друг в дружку. Тогда не получится
Ок. Всем спасибо за внимание.

Наличие ссылки parent - это здесь основа для нерекурсивных алгоритмов. Без этих дополнительных ссылок требуется рекурсия, либо всякие стеки-нестеки, и прочее фуфло.

Ето понятно, в том то и суть что previous нет. Ето смущало.
Должен ли быть парент у всех не NULL - по смыслу видать ето и имели ввиду.

[SVK]

Должен ли быть парент у всех не NULL - по смыслу видать ето и имели ввиду.

Это зависит от того, как еще используется такая структура.

Конкретно для walkTree ссылка parent нужна только там, где нет ссылки next - во всех остальных случаях она игнорируется. Но для других алгоритмов промежуточные parent тоже могут требоваться. В общем случае, для такой структуры, правильнее заполнять все parents одного уровня.

[olg2002]

Наличие ссылки parent - это здесь основа для нерекурсивных алгоритмов. Без этих дополнительных ссылок требуется рекурсия, либо всякие стеки-нестеки, и прочее фуфло.

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

[SVK]

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

Да. Я это осознал в те времена, когда из нашей школы уже убрали компьютер "Урал-1", а другого еще не было. И программированию нас в то время учили на абстрактном "Языке символических обозначений"

А оценки за контрольные по программированию были такие:
Первый - очень слабо: оценка 3
Второй - еще хуже: оценка 2
Третий - вообще все перепутано: оценка 1
Четвертый - даже не понял условия: оценка 0
Пятый - явно списал с соседа - одни обрывки: оценка -1
Шестой - даже не начал решать: оценка -2

[A. Fig Lee]

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

Да. Я это осознал в те времена, когда из нашей школы уже убрали компьютер "Урал-1", а другого еще не было. И программированию нас в то время учили на абстрактном "Языке символических обозначений"

Да... А я вот не осознал, что ее устанавливать будут...

[olg2002]

У меня самый простой обход такой получился:

Code: Select all

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;
    }
}

[theukrainian]

Нее. По картинке, которую нарисовал Фигли, работать не будет, по-моему. Ведь первая часть цикла уходит всегда на child, и только если нету children вы начинаете смотреть на siblings.

К предыдущим сообщениям: тут parents не NULL - просто tree задается интересно. На самом деле, если это дерево немного перевернуть, то получится что в приведенной картинке, parent 6 это 2.

На самом деле, такой walk решается со стэком. Короче, как Странник сказал ... или я совсем ничего не понял в колбасных обрезках.

[SVK]

У меня самый простой обход такой получился:

Code: Select all

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;
    }
}

1-2-3-4-5-4-5-4-5-4-5-4-5-4-5-4-5-4-5-4-5-4-5-4-.....

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

Оценка по моим школьным воспоминаниям будет: -1

[SVK]

На самом деле, такой walk решается со стэком. Короче, как Странник сказал ... или я совсем ничего не понял в колбасных обрезках.

Свет клином на стеке не сошелся, однако...

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

result = findSolution( inputData) ;
return result;

[A. Fig Lee]

Да, стек скорее всего не имелся ввиду. В общем как обычно - разгадать что хотели сказать

[theukrainian]

дык, в том то и дело что они, наверное, хотели чтобы кандидат написал стек.

[SVK]

дык, в том то и дело что они, наверное, хотели чтобы кандидат написал стек.

...и это бы на 100% показало, что кандидидат не понимает ситуации. Наличие ссылки *parent - это и есть уже готовый стек прямо встроенный в имеющуюся структуру данных. Если кандидат не может его разглядеть, и строит вместо этого дублирующую структуру, то "таких не берут в космонавты". В перспективе он много дублирующего может понастроить в реальных системах, где это далеко не так очевидно, как в простейшей задаче.

[olg2002]

1-2-3-4-5-4-5-4-5-4-5-4-5-4-5-4-5-4-5-4-5-4-5-4-.....

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

Оценка по моим школьным воспоминаниям будет: -1

Надо было хоть проверить, как этот алгоритм работает на компьютере, прежде чем такое написать. А так получилось глупо и высокомерно. Хуже нет, когда с таким сталкиваешься на интервью. Единственное путнее замечание про обход поддерева (правится элементарно, но красоту портить не хочется). Оценку ставить не буду.

[SVK]

Надо было хоть проверить, как этот алгоритм работает на компьютере, прежде чем такое написать. А так получилось глупо и высокомерно. Хуже нет, когда с таким сталкиваешься на интервью. Единственное путнее замечание про обход поддерева (правится элементарно, но красоту портить не хочется). Оценку ставить не буду.

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

[SVK]

правится элементарно, но красоту портить не хочется

По поводу красоты.

Самый красивый алгоритм вычисления факториала, к тому же приводимый в 95-99% учебников, - это рекурсивный вызов

Code: Select all

long fact(int n)
{
return (n > 1)? n * fact(n-1) : 1;
}

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

[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;
}

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