Возврат значения с рекурсией в c ++ - PullRequest
Новая
       7

Возврат значения с рекурсией в c ++

0 голосов
/ 21 октября 2011

У меня было интервью, и я не мог ответить на этот вопрос.У вас есть двоичное дерево, и вы помещаете все узлы в массив, используя in_order, и вы возвращаете значение для размера массива.Мне сказали, что я не могу использовать вспомогательную функцию и добавить int i = 0 для счетчика массива.

Я должен был использовать заголовок рекурсивной функции. 

      In_order(Struct_Node * node, int *array){

      }

Поскольку это былоIn_order я написал. 

      if(node){
      In_order(node->left, array);

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

      in_order(node->right,array); 
      }

На самом деле я не писал то, что написал между двумя операторами In_order, но чтоЯ написал неправильно.

Ответы [ 3 ]

7 голосов
/ 21 октября 2011

Угадывая все недостающие детали, я думаю, вы бы сделали что-то вроде: 

int In_order(Struct_Node * node, int *array){

   int count = 0;
   if (node->left) {
     count += In_order(node->left, array);
   }
   array[count++] = node->data; // whatever it is you're storing
   if (node->right) {
     count += In_order(node->right, array+count);
   }
   return count;
}

Ключевым моментом является то, что вы передаете обновленный указатель на рекурсивный вызов RHS, и ваше возвращаемое значение равно 1 + LHS return + RHS return

Если вы не можете использовать int в качестве счетчика (что на самом деле глупо, потому что это самый ясный способ выразить это), вы можете сделать: 

int In_order(Struct_Node * node, const int *array){
   int *tptr = array;

   if (node->left) {
     tptr += In_order(node->left, array);
   }
   *tptr++ = node->data; // whatever it is you're storing
   if (node->right) {
     tptr += In_order(node->right, tptr);
   }

   return tptr-array;
}

Если вы хотите немного "сойти с ума" и избегать каких-либо локальных переменных, кроме аргументов функции, вы можете изменить тип возвращаемого значения на указатель на текущий рабочий конец массива (который фактически является размером массива также) и делаем: 

int *In_order(const Struct_Node * const node, int * const result) {
  return !node ? result :
          In_order(node->right, &(*In_order(node->left, result) = node->value)+1);
}

Хотя, честно говоря, это ужасный код (я даже не уверен на 100%, что он хорошо определен!), И я действительно надеюсь, что они не искали такого решения! *

0 голосов
/ 21 октября 2011

Для обхода inorder:

  1. Выполнить обход inorder левого поддерева (если оно есть).
  2. Посетить текущий узел.
  3. Doобход по порядку правого поддерева (если оно есть).

В вашем случае "визит" означает добавление текущего узла в список и увеличение счетчика.

Что касается размещения элементов в массиве, лично я бы использовал вектор (и затем преобразовывал / копировал в массив в конце, если это абсолютно необходимо).Вы можете создать ее в функции «start», которая затем вызывает рекурсивную функцию, или создать ее в вызывающей программе.В любом случае, вы передаете ссылку на него в каждом вызове.В конце у вас есть и массив значений узлов, и количество.В противном случае вам придется пройти через дерево один раз, чтобы сосчитать элементы, и второй раз, чтобы собрать их.(Или вы можете передать ссылку или указатель на указатель, так что вы можете перераспределять по мере необходимости, но это становится уродливым. В любом случае, я бы не стал доверять вызывающей стороне знать, какой массив вам дать - это ваша работазнать / изобразить размер вашего дерева.: P)

0 голосов
/ 21 октября 2011

In-order - метод обхода дерева; Вы перемещаете узлы по порядку (отсюда и название) слева направо.

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

После вызова in_order(node->right,array) вы возвращаете свое значение (описание вашей проблемы неясно, что именно вы должны возвращать).

...