DFS дерево без памяти

Question

Я пытаюсь написать функцию для обхода дерева с первым поиском по глубине.

Мой текущий алгоритм выглядит примерно так:

If children
 go to first child

If no children
 go to next sibling

If no siblings
 go to parent

Проблема, с которой я сталкиваюсь, заключается вчто я не могу пометить узлы на дереве как посещенные, поэтому, когда я перехожу к родителю, цикл просто сбрасывается, и он снова переходит к дочернему элементу, застревая в цикле.Кто-нибудь имеет какие-либо идеи относительно того, как я мог бы решить эту проблему?

(это в Java с помощью плагина ANTLR)

РЕДАКТИРОВАТЬ:

Следуя одному из предложений, я написал это:

public void traverseTree(Tree tree){

    if (tree.getChildCount() > 0){
        tree = tree.getChild(0);
        traverseTree(tree);
        System.out.println(tree.toString());
    }
    if (tree.getParent().getChild(tree.getChildIndex() + 1) != null){
        tree = tree.getParent().getChild(tree.getChildIndex() + 1);
        traverseTree(tree);
        System.out.println(tree.toString());
    }
    if (!tree.getParent().toString().contains("ROOT_NODE")){
        tree = tree.getParent();
        traverseTree(tree);
        System.out.println(tree.toString());
    }
}

Корневой узел - это имя корневого узла, но я получаю ошибку переполнения стека.У кого-нибудь есть идеи, почему?

Спасибо.

Answer 1

Я бы использовал рекурсию в этом случае.

class Node {
   public List<Node> getChildren() { .... }

   public void traverse(Visitor<Node> visitor) {
      // If children
      // go to first child - by traversing the children first.
       for(Node kid: getChildren())
           kid.traverse(visitor);
           // If no children
           //  go to next sibling, - by continuing the loop.

       visitor.visit(this);
       // If no siblings
       // go to parent - by returning and letting the parent be processed
   }
}


interface Vistor<N> {
   public void visit(N n);
}

Answer 2

Если «нет памяти» можно интерпретировать как O (1) памяти, то изменение может помочь:

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

Answer 3

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

Answer 4

Используя отображение hash_table, каждая вершина для логического значения указывает, посещен ли он или нет