Итеративный обход дерева в глубину с посещением до и после каждого узла

Question

Может ли кто-нибудь указать мне псевдокод для итеративного обхода дерева в глубину, где можно выполнять действия на каждом узле как до, так и после заказа?

То есть действие перед прицеливанием в дочерние узлы, затем действие после восхождения от дочерних элементов?

Кроме того, мое дерево не является двоичным - каждый узел имеет 0..n дочерних элементов.

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

Answer 1

Мой план - использовать два стека. Один для обхода до заказа, а другой для обхода после заказа. Теперь я запускаю стандартную итеративную DFS (обход в глубину), и как только я pop из стека «pre», я помещаю его в «post» стек. В конце у моего стека "post" будет дочерний узел вверху и root внизу.

treeSearch(Tree root) {
    Stack pre;
    Stack post;
    pre.add(root);
    while (pre.isNotEmpty()) {
        int x = pre.pop();
        // do pre-order visit here on x
        post.add(x);
        pre.addAll(getChildren(x));
    }
    while (post.isNotEmpty()) {
        int y = post.pop();
        // do post-order visit here on y
    }
}

root всегда будет проходить последним из стека post, так как он останется внизу.

Это простой код Java:

public void treeSearch(Tree tree) {
    Stack<Integer> preStack = new Stack<Integer>();
    Stack<Integer> postStack = new Stack<Integer>();
    preStack.add(tree.root);
    while (!preStack.isEmpty()) {
        int currentNode = preStack.pop();
        // do pre-order visit on current node
        postStack.add(currentNode);
        int[] children = tree.getNeighbours(currentNode);
        for (int child : children) {
            preStack.add(child);
        }
    }

    while (!postStack.isEmpty()) {
        int currentNode = postStack.pop();
        // do post-order visit on current node
    }
}

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

Answer 2

Я понимаю, что этому посту уже несколько лет, но ни один из ответов, похоже, не дает прямого ответа на вопрос, поэтому я решил, что напишу что-то несколько простое.

Это предполагает целочисленный индексированный граф; но вы, конечно, можете адаптировать его по мере необходимости. Ключом к итеративному выполнению DFS и сохранению операций предварительного заказа / пост-заказа является НЕ просто добавлять каждый дочерний элемент сразу, а вместо этого вести себя точно так же, как рекурсивный DFS, который добавляет только один дочерний элемент. узел к стеку за раз, и удаляя их из стека только после его завершения. Я выполняю это в своем примере, создав узел-обертку со списком смежности в виде стека. Просто пропустите проверку циклов, если вы хотите разрешить циклы (в любом случае они не проходят через посещенные узлы, поэтому все равно будут работать)

class Stack(object):
    def __init__(self, l=None):
        if l is None:
            self._l = []
        else:
            self._l = l
        return

    def pop(self):
        return self._l.pop()

    def peek(self):
        return self._l[-1]

    def push(self, value):
        self._l.append(value)
        return

    def __len__(self):
        return len(self._l)

class NodeWrapper(object):
    def __init__(self, graph, v):
        self.v = v
        self.children = Stack(graph[v])
        return

def iterative_postorder(G, s):
    onstack = [False] * len(G)
    edgeto = [None] * len(G)
    visited = [False] * len(G)

    st = Stack()
    st.push(NodeWrapper(G, s))

    while len(st) > 0:
        vnode = st.peek()
        v = vnode.v
        if not onstack[v]:
            print "Starting %d" % (v)
        visited[v] = True
        onstack[v] = True
        if len(vnode.children) > 0:
            e = vnode.children.pop()
            if onstack[e]:
                cycle = [e]
                e = v
                while e != cycle[0]:
                    cycle.append(e)
                    e = edgeto[e]
                raise StandardError("cycle detected: %s, graph not acyclic" % (cycle))
            if not visited[e]:
                edgeto[e] = v
                st.push(NodeWrapper(G, e))
        else:
            vnode = st.pop()
            onstack[vnode.v] = False
            print 'Completed %d' % (vnode.v)

Answer 3

class Node:
  def __init__( self, value ):
    self.value    = value
    self.children = []

def preprocess( node ):
  print( node.value )

def postprocess( node ):
  print( node.value )

def preorder( root ):
  # Always a flat, homogeneous list of Node instances.
  queue = [ root ]
  while len( queue ) > 0:
    a_node = queue.pop( 0 )
    preprocess( a_node )
    queue = a_node.children + queue

def postorder( root ):
  # Always a flat, homogeneous list of Node instances:
  queue   = [ root ]
  visited = set()
  while len( queue ) > 0:
    a_node = queue.pop( 0 )
    if a_node not in visited:
      visited.add( a_node )
      queue = a_node.children + [ a_node ] + queue
    else:
      # this is either a leaf or a parent whose children have all been processed
      postprocess( a_node )

Answer 4

простая реализация Python с двумя разными посетителями

class Print_visitor(object):
    def __init__(self):
        pass
    def pre_visit(self, node):
        print "pre: ", node.value
    def post_visit(self, node):
        print "post:", node.value

class Prettyprint_visitor(object):
    def __init__(self):
        self.level=0
    def pre_visit(self, node):
        print "{}<{}>".format("    "*self.level, node.value)
        self.level += 1
    def post_visit(self, node):
        self.level -= 1
        print "{}</{}>".format("    "*self.level, node.value)

class Node(object):
    def __init__(self, value):
        self.value = value
        self.children = []
    def traverse(self, visitor):
        visitor.pre_visit(self)
        for child in self.children:
            child.traverse(visitor)
        visitor.post_visit(self)

if __name__ == '__main__':
    #test
    tree = Node("root")
    tree.children = [Node("c1"), Node("c2"), Node("c3")]
    tree.children[0].children = [Node("c11"), Node("c12"), Node("c13")]
    tree.children[1].children = [Node("c21"), Node("c22"), Node("c23")]
    tree.children[2].children = [Node("c31"), Node("c32"), Node("c33")]
    tree.traverse(Print_visitor())
    tree.traverse(Prettyprint_visitor())

Answer 5

Надеюсь, вы найдете это полезным.

http://www.vvlasov.com/2013/07/post-order-iterative-dfs-traversal.html

Код:

public void dfsPostOrderIterative(AdjGraph graph, AdjGraph.Node vertex, Callback callback) {
    Stack<Level> toVisit = new Stack<Level>();
    toVisit.push(new Level(Collections.singletonList(vertex)));

    while (!toVisit.isEmpty()) {
        Level level = toVisit.peek();

        if (level.index >= level.nodes.size()) {
            toVisit.pop();
            continue;
        }

        AdjGraph.Node node = level.nodes.get(level.index);

        if (!node.isVisited()) {
            if (node.isChildrenExplored()) {
                node.markVisited();
                callback.nodeVisited(graph, node);
                level.index++;
            } else {
                List<AdjGraph.Node> edges = graph.edges(node);
                List<AdjGraph.Node> outgoing = Lists.newArrayList(Collections2.filter(edges, new Predicate<AdjGraph.Node>() {
                    @Override
                    public boolean apply(AdjGraph.Node input) {
                        return !input.isChildrenExplored();
                    }
                }));

                if (outgoing.size() > 0)
                    toVisit.add(new Level(outgoing));
                node.markChildrenExplored();
            }
        } else {
            level.index++;
        }
    }
}

Answer 6

Я думаю, что у меня есть именно то, что мне нужно, вставив preProcess в функцию postorder, предоставляемую El Mariachi:

def postorder( root ):
 # Always a flat, homogeneous list of Node instances:
 queue   = [ root ]
 visited = set()
 while len( queue ) > 0:
   a_node = queue.pop( 0 )
   if a_node not in visited:
     preprocess( a_node )                  # <<<<<<<< Inserted
     visited.add( a_node )
     queue = a_node.children + [ a_node ] + queue
   else:
     # this is either a leaf or a parent whose children have all been processed
     postprocess( a_node )