Java中的DFS迭代:

//DFS: Iterative
private Boolean DFSIterative(Node root, int target) {
    if (root == null)
        return false;
    Stack<Node> _stack = new Stack<Node>();
    _stack.push(root);
    while (_stack.size() > 0) {
        Node temp = _stack.peek();
        if (temp.data == target)
            return true;
        if (temp.left != null)
            _stack.push(temp.left);
        else if (temp.right != null)
            _stack.push(temp.right);
        else
            _stack.pop();
    }
    return false;
}

使用ES6生成器的非递归DFS

class Node {
  constructor(name, childNodes) {
    this.name = name;
    this.childNodes = childNodes;
    this.visited = false;
  }
}

function *dfs(s) {
  let stack = [];
  stack.push(s);
  stackLoop: while (stack.length) {
    let u = stack[stack.length - 1]; // peek
    if (!u.visited) {
      u.visited = true; // grey - visited
      yield u;
    }

    for (let v of u.childNodes) {
      if (!v.visited) {
        stack.push(v);
        continue stackLoop;
      }
    }

    stack.pop(); // black - all reachable descendants were processed 
  }    
}

它与典型的非递归DFS不同，可以很容易地检测给定节点的所有可达后代何时被处理，并维护列表/堆栈中的当前路径。

伪代码基于@biziclop的答案:

只使用基本结构:变量、数组、if、while和for 函数getNode(id)和getChildren(id) 假设已知节点数N

注意:我从1开始使用数组索引，而不是0。

广度优先

S = Array(N)
S[1] = 1; // root id
cur = 1;
last = 1
while cur <= last
    id = S[cur]
    node = getNode(id)
    children = getChildren(id)

    n = length(children)
    for i = 1..n
        S[ last+i ] = children[i]
    end
    last = last+n
    cur = cur+1

    visit(node)
end

深度优先

S = Array(N)
S[1] = 1; // root id
cur = 1;
while cur > 0
    id = S[cur]
    node = getNode(id)
    children = getChildren(id)

    n = length(children)
    for i = 1..n
        // assuming children are given left-to-right
        S[ cur+i-1 ] = children[ n-i+1 ] 

        // otherwise
        // S[ cur+i-1 ] = children[i] 
    end
    cur = cur+n-1

    visit(node)
end

只是想把我的python实现添加到长长的解决方案列表中。这种非递归算法具有发现和完成事件。

worklist = [root_node]
visited = set()
while worklist:
    node = worklist[-1]
    if node in visited:
        # Node is finished
        worklist.pop()
    else:
        # Node is discovered
        visited.add(node)
        for child in node.children:
            worklist.append(child)

基于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); } }

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中的所有节点。