Обход n-арного дерева без использования рекурсии

Question

Как я могу пройти по n -ному дереву без использования рекурсии?

Рекурсивный способ:

traverse(Node node)
{
    if(node == null)
        return;

    for(Node child : node.getChilds()) {
        traverse(child);
    }
}

Answer 1

То, что вы делаете, по сути является DFS дерева. Вы можете устранить рекурсию, используя стек:

traverse(Node node) {
    if (node==NULL)
        return;

    stack<Node> stk;
    stk.push(node);

    while (!stk.empty()) {
        Node top = stk.pop();
        for (Node child in top.getChildren()) {
            stk.push(child);
        }
        process(top);
    }
}

Если вы хотите, чтобы BFS использовала очередь:

traverse(Node node) {
    if (node==NULL)
        return;

    queue<Node> que;
    que.addRear(node);

    while (!que.empty()) {
        Node front = que.deleteFront();
        for (Node child in front.getChildren()) {
            que.addRear(child);
        }
        process(front);
    }
}

В случае, если вам нужен другой способ обхода, вам придется следовать тому же подходу, хотя и с другой структурой данных для хранения узла. Может быть приоритетная очередь (если вы хотите оценить функцию на каждом узле, а затем обработать узлы на основе этого значения).

Answer 2

Вы можете сделать это без рекурсии и без стека. Но вам нужно добавить два дополнительных указателя на узел:

1. Родительский узел. Так что вы можете вернуться к родителю, если вы закончили.

2. Текущий дочерний узел, чтобы вы знали, какой из них выбрать следующий.

   • Для каждого узла вы управляете всеми детьми.
   • Если с ребенком обращаются, вы проверяете, есть ли следующий ребенок, и обрабатываете его (обновляя текущий).
   • Если все дети обрабатываются, вернитесь к родителю.
   • Если узел НЕДЕЙСТВИТЕЛЕН, выйдите.

С псевдокодом это выглядит так:

traverse(Node node) {
  while (node) {
    if (node->current <= MAX_CHILD) {
      Node prev = node;
      if (node->child[node->current]) {
        node = node->child[node->current];
      }
      prev->current++;
    } else {
      // Do your thing with the node.
      node->current = 0; // Reset counter for next traversal.
      node = node->parent;
    }
  }
}

Answer 3

Язык не указан, поэтому в псевдопсевдокоде:

traverse(Node node)
{
  List<Node> nodes = [node];

  while (nodes.notEmpty) {
    Node n = nodes.shift();

    for (Node child in n.getChildren()) {
      nodes.add(child);
    }

    // do stuff with n, maybe
  }
}

Обратите внимание, что это обход в ширину, в отличие от обхода в глубину, приведенного в вопросе. Вы должны быть в состоянии выполнить обход в глубину, pop выбрав последний элемент из списка nodes вместо shift первого.