пройти x количество узлов по порядку

Я знаю, что это, вероятно, простой вопрос, но я давно не занимался программированием на C. Я пытаюсь выполнить неупорядоченный обход по x узлам, где x - это некоторое число, которое я передаю функции. Моя функция inorder вызывает себя рекурсивно, и я не могу понять, как остановить обход после посещения x узлов. Вот моя функция обхода порядка:

void inorder(node h)
 {

     if (h != NULL)
     {
        inorder(h->l);

        printf(" %d\n",h->item);

        inorder(h->r);
     }
      return;

 }

Любое руководство приветствуется.


c traversal binary-tree
person bardockyo    schedule 10.04.2013    source источник
comment
Заставьте функцию inorder возвращать число, указывающее количество оставшихся узлов, затем передайте это число в качестве параметра функции inorder.   -  person nhahtdh    schedule 10.04.2013

Ответы (2)


arrow_upward
0
arrow_downward

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

int inorder(node h, int x)
 {

     if (h != NULL && x > 0)
     {
        x = inorder(h->l, x);

        if (x > 0) {
           printf(" %d\n",h->item);
           x--;
        }
        if (h->r && x > 0)
           x = inorder(h->r, x);
     }
      return x;

 }

[EDIT: этот код был исправлен @nhahtdh после некоторого обсуждения определения посещенных узлов и уменьшения значения x. Рабочий тестовый код можно увидеть здесь.

person nommyravian    schedule 10.04.2013
comment
x - это элемент, который он хочет посетить, а не глубина посещения по порядку, я думаю - person MYMNeo; 10.04.2013
comment
Я думаю, что он хочет посетить x узлов, если я не ошибаюсь в вопросе. - person nommyravian; 10.04.2013
comment
Мне кажется, вы слишком сильно уменьшаете. Вы должны уменьшать только один раз, но кажется, что вы уменьшаете x дважды за вызов функции (игнорируя рекурсивный вызов). - person nhahtdh; 10.04.2013
comment
Я пытаюсь уменьшить каждый раз, когда я посещаю узел, поэтому при каждом вызове функции мы фактически посещаем левый или правый узел. нет? Теперь я думаю, что узел может быть нулевым, что может быть неправильным уменьшением. - person nommyravian; 10.04.2013
comment
@nommyravian: вы должны уменьшать значение только один раз после того, как вы printf, и вам также нужно проверить, следует ли вам печатать элемент, поскольку x может достичь 0 после посещения левого поддерева. - person nhahtdh; 10.04.2013
comment
я думаю, что x должен быть количеством посещенных узлов, а не количеством напечатанных узлов. Таким образом, каждый узел должен быть помечен как посещенный, когда мы делаем вызов функции с левым или правым дочерним элементом. Я только что проверил то, что вы говорите, и он печатает больше узлов, чем x. - person nommyravian; 10.04.2013
comment
@nommyravian: я не знаю, что OP означает количество посещенных узлов - я принимаю это как количество узлов, которые следует распечатать. Можете ли вы вставить свой тестовый код в ideone? - person nhahtdh; 10.04.2013
comment
это здесь. Я провел некоторое тестирование в старом коде, поэтому нашел время, чтобы вытащить что-то полезное для ideone. тестовый код - person nommyravian; 10.04.2013
comment
давайте продолжим обсуждение в чате - person nhahtdh; 10.04.2013

arrow_upward
1
arrow_downward

Предполагая, что «количество посещений» — это количество узлов, которые вы хотите распечатать из обхода по порядку. Одно из решений состоит в том, чтобы заставить функцию inorder возвращать количество узлов, оставшихся для печати, и сверяться с ним при обходе дерева.

int inorder(node h, int x)
{
    // I mimic your current code. The code is indeed shorter, but it will
    // do extra recursion, compared to the other approach of checking
    // for the subtree and value of x before the recursive call.
    if (h != NULL && x > 0)
    {
        x = inorder(h->l, x);

        if (x > 0) {
            printf(" %d\n",h->item);
            x--;
        }

        x = inorder(h->r, x);
    }

    return x;
}

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

void inorder(node h, int *x)
{
    // I mimic your current code. The code is indeed shorter, but it will
    // do extra recursion, compared to the other approach of checking
    // for the subtree and value of x before the recursive call.
    if (h == NULL && *x > 0)
    {
        inorder(h->l, x);

        if (*x > 0) {
            printf(" %d\n",h->item);
            (*x)--;
        }

        inorder(h->r, x);
    }
}
person nhahtdh    schedule 10.04.2013