你可以使用一个堆栈来保存尚未访问的节点:

stack.push(root)
while !stack.isEmpty() do
    node = stack.pop()
    for each node.childNodes do
        stack.push(stack)
    endfor
    // …
endwhile

PreOrderTraversal is same as DFS in binary tree. You can do the same recursion 
taking care of Stack as below.

    public void IterativePreOrder(Tree root)
            {
                if (root == null)
                    return;
                Stack s<Tree> = new Stack<Tree>();
                s.Push(root);
                while (s.Count != 0)
                {
                    Tree b = s.Pop();
                    Console.Write(b.Data + " ");
                    if (b.Right != null)
                        s.Push(b.Right);
                    if (b.Left != null)
                        s.Push(b.Left);

                }
            }

一般的逻辑是，将一个节点(从根开始)推入Stack, Pop()它和Print()值。然后，如果它有子节点(左和右)，将它们推入堆栈-先推右，这样你就会先访问左子节点(在访问节点本身之后)。当stack为空()时，您将访问Pre-Order中的所有节点。

Stack<Node> stack = new Stack<>();
stack.add(root);
while (!stack.isEmpty()) {
    Node node = stack.pop();
    System.out.print(node.getData() + " ");

    Node right = node.getRight();
    if (right != null) {
        stack.push(right);
    }

    Node left = node.getLeft();
    if (left != null) {
        stack.push(left);
    }
}

http://www.youtube.com/watch?v=zLZhSSXAwxI

刚刚看了这个视频，并提出了实施方案。这对我来说似乎很容易理解。请评论一下。

visited_node={root}
stack.push(root)
while(!stack.empty){
  unvisited_node = get_unvisited_adj_nodes(stack.top());
  If (unvisited_node!=null){
     stack.push(unvisited_node);  
     visited_node+=unvisited_node;
  }
  else
     stack.pop()
}

基于biziclops的ES6实现很棒的答案:

root = { text: "root", children: [{ text: "c1", children: [{ text: "c11" }, { text: "c12" }] }, { text: "c2", children: [{ text: "c21" }, { text: "c22" }] }, ] } console.log("DFS:") DFS(root, node => node.children, node => console.log(node.text)); console.log("BFS:") BFS(root, node => node.children, node => console.log(node.text)); function BFS(root, getChildren, visit) { let nodesToVisit = [root]; while (nodesToVisit.length > 0) { const currentNode = nodesToVisit.shift(); nodesToVisit = [ ...nodesToVisit, ...(getChildren(currentNode) || []), ]; visit(currentNode); } } function DFS(root, getChildren, visit) { let nodesToVisit = [root]; while (nodesToVisit.length > 0) { const currentNode = nodesToVisit.shift(); nodesToVisit = [ ...(getChildren(currentNode) || []), ...nodesToVisit, ]; visit(currentNode); } }

这是一个java程序的链接，显示DFS同时遵循递归和非递归方法，还计算发现和完成时间，但没有边对齐。

    public void DFSIterative() {
    Reset();
    Stack<Vertex> s = new Stack<>();
    for (Vertex v : vertices.values()) {
        if (!v.visited) {
            v.d = ++time;
            v.visited = true;
            s.push(v);
            while (!s.isEmpty()) {
                Vertex u = s.peek();
                s.pop();
                boolean bFinished = true;
                for (Vertex w : u.adj) {
                    if (!w.visited) {
                        w.visited = true;
                        w.d = ++time;
                        w.p = u;
                        s.push(w);
                        bFinished = false;
                        break;
                    }
                }
                if (bFinished) {
                    u.f = ++time;
                    if (u.p != null)
                        s.push(u.p);
                }
            }
        }
    }
}

这里是完整的源代码。