Поиск дерева и вывод пути к этому узлу в C ++

Question

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

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

Как бы я мог найти идентификатор и вывести путь к этому идентификатору? У меня есть способ узнать, есть ли идентификатор в дереве, но вывод правильного пути - это другая история. Я пытался использовать поток строк, но он, кажется, не работает должным образом (я получаю пути, которые включают идентификаторы, не приводящие к идентификатору, который я хочу) ПРИМЕЧАНИЕ: предположим, что идентификаторы могут появляться в дереве только один раз

Должно ли это быть сделано с помощью рекурсии? Или это можно сделать с помощью циклов?

Answer 1

Я считаю, что следующий код дает вам представление о том, что вы должны делать (рекурсия):

bool find(const string& i_id, const ATree* i_tree, string& o_path) {
  if(!i_tree) return false;
  if (i_id == i_tree->id) {
    o_path = i_tree->id;
    return true;
  }
  string path;
  for (size_t i = 0; i < i_tree->numof_children; ++i) {
    if (find(id, i_tree->children[i], path)) {
      o_path = i_tree->id + '/' + path;
      return true;
    }
  }
  return false;
}

Answer 2

Грубая схема алгоритма:

std::vector< const ATree* >
getPath(const ATree* tree, const std::string& id)
{
        std::vector< const ATree* > path;

        if (tree->id == id) {
                path.push_back(tree);
        } else {
                for (int i=0; i < tree->numof_children; i++) {
                        std::vector< const ATree* > tmp=
                                getPath(tree->children[i], id);
                        if (tmp.size() > 0) {
                            path.push_back(tree);
                            path.insert(path.end(), tmp.begin(), tmp.end());
                                break;
                        }
                }
        }

        return path;
}

Answer 3

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

Если вы сохраните их в структуре std::stack, вам будет легко просто вытолкнуть их, когда вы вернетесь после достижения листьев.и не найдя нужных id.

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