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

使用堆栈来跟踪节点

Stack<Node> s;

s.prepend(tree.head);

while(!s.empty) {
    Node n = s.poll_front // gets first node

    // do something with q?

    for each child of n: s.prepend(child)

}

完整的示例工作代码，没有堆栈:

import java.util.*;

class Graph {
private List<List<Integer>> adj;

Graph(int numOfVertices) {
    this.adj = new ArrayList<>();
    for (int i = 0; i < numOfVertices; ++i)
        adj.add(i, new ArrayList<>());
}

void addEdge(int v, int w) {
    adj.get(v).add(w); // Add w to v's list.
}

void DFS(int v) {
    int nodesToVisitIndex = 0;
    List<Integer> nodesToVisit = new ArrayList<>();
    nodesToVisit.add(v);
    while (nodesToVisitIndex < nodesToVisit.size()) {
        Integer nextChild= nodesToVisit.get(nodesToVisitIndex++);// get the node and mark it as visited node by inc the index over the element.
        for (Integer s : adj.get(nextChild)) {
            if (!nodesToVisit.contains(s)) {
                nodesToVisit.add(nodesToVisitIndex, s);// add the node to the HEAD of the unvisited nodes list.
            }
        }
        System.out.println(nextChild);
    }
}

void BFS(int v) {
    int nodesToVisitIndex = 0;
    List<Integer> nodesToVisit = new ArrayList<>();
    nodesToVisit.add(v);
    while (nodesToVisitIndex < nodesToVisit.size()) {
        Integer nextChild= nodesToVisit.get(nodesToVisitIndex++);// get the node and mark it as visited node by inc the index over the element.
        for (Integer s : adj.get(nextChild)) {
            if (!nodesToVisit.contains(s)) {
                nodesToVisit.add(s);// add the node to the END of the unvisited node list.
            }
        }
        System.out.println(nextChild);
    }
}

public static void main(String args[]) {
    Graph g = new Graph(5);

    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 2);
    g.addEdge(2, 0);
    g.addEdge(2, 3);
    g.addEdge(3, 3);
    g.addEdge(3, 1);
    g.addEdge(3, 4);

    System.out.println("Breadth First Traversal- starting from vertex 2:");
    g.BFS(2);
    System.out.println("Depth First Traversal- starting from vertex 2:");
    g.DFS(2);
}}

输出: 宽度优先遍历-从顶点2开始: 2 0 3. 1 4 深度优先遍历-从顶点2开始: 2 3. 4 1 0

DFS:

list nodes_to_visit = {root};
while( nodes_to_visit isn't empty ) {
  currentnode = nodes_to_visit.take_first();
  nodes_to_visit.prepend( currentnode.children );
  //do something
}

BFS:

list nodes_to_visit = {root};
while( nodes_to_visit isn't empty ) {
  currentnode = nodes_to_visit.take_first();
  nodes_to_visit.append( currentnode.children );
  //do something
}

两者的对称相当酷。

更新:如前所述，take_first()删除并返回列表中的第一个元素。

使用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不同，可以很容易地检测给定节点的所有可达后代何时被处理，并维护列表/堆栈中的当前路径。

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