Нахождение и вывод пути к уникальному узлу в C ++?

Question

Скажем, у нас есть следующая структура:

struct Tree {
  string id;
  int numof_children;
  Tree *children[5];
};

... где каждый идентификатор уникален (может появиться только один раз в дереве), как мне найти путь к идентификатору в дереве этого типа и вывести его?

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

Ограничения: нельзя использовать типы данных векторов / списков / стеков. Только рекурсия. Рекомендации: Функция look (ATree * t, string & id) должна иметь возвращаемый тип строки.

Существует ли общая структура рекурсии, которой я могу следовать?

Answer 1

Рекурсию может быть сложно объяснить, но я постараюсь объяснить, как она применяется в этой ситуации. Поскольку вы можете рекурсивно проверять, существует ли каждый узел, вы захотите вернуть идентификатор в качестве возвращаемой строки. Это уведомляет рекурсивный стек, что совпадение было найдено. Затем вы добавляете идентификатор текущего узла в строку и возвращаете его в стек. Это в свою очередь уведомляет стек, что найдено совпадение и т. Д. Вот мое решение, в которое я добавил несколько комментариев, чтобы лучше проиллюстрировать эту точку.

// If found return [string] [of] [ids], else empty string
string look(const Tree * t, const string & id) {
   // If current node matchs return id
   if(t->id == id) {
      return "[" + id + "]";
   }

   // Loop over each child, recursively calling look
   for(int i=0; i<t->numof_children; i++) {
      string s = look(t->children[i], id);
      // If found add to string and return
      if(!s.empty()) {
         return "[" + t->id + "] " + s;
         // alternatively: return s + " [" + t->id + "]"; will genreate string in reverse
      }
   }

   // Not found, return empty string
   return string();
}

Большинство рекурсивных функций следуют похожему шаблону. Если вы все еще немного потерялись, я бы порекомендовал запустить его через отладчик, чтобы вы могли точно видеть, что происходит.