让我们来一个例子，如果我们要遍历这样一棵树
/**
* Create a tree like this
* Root
* / | \
* A B C
* / \
* D F
* /
* E
*
* @return The tree
*/
static Node createTree() {
Node root = new BranchNode("Root");
Node a = new BranchNode("A");
Node b = new LeafNode("B");
Node c = new BranchNode("C");
Node d = new BranchNode("D");
Node e = new LeafNode("E");
Node f = new LeafNode("F");
a.addNode(d);
d.addNode(e);
c.addNode(f);
root.addNode(a);
root.addNode(b);
root.addNode(c);
return root;
}
从根节点Root开始遍历，第一个子节点，也就是Root自己的第一个直属子节点，是A。下一个呢？因为A是一个树枝节点，所以我们把它先压入堆栈。下一次从A开始，我们可以把从A开始的子节点遍历看成一次全新的遍历，所以A的第一个子节点是什么呢？D！很简单不是？然后是E。因为E没有子节点，所以我们返回找D的下一个子节点，但是D除了E是它的子节点之外，没有另外的子节点了。所以D也没有子节点了，又返回到A。A也没有多余的子节点了，所以这个时候轮到B……
所以，最终的顺序是Root -> A -> D -> E -> B -> C -> F。
回过头来看看hasNext()做了什么。还记得吗？我们把每一个遇到的树枝节点压入堆栈，当堆栈中不存在任何的树枝节点时，遍历就完成了。如果有，我们就取出一个，看它是不是还有子节点，如果有，那么我们就说还有下一个节点。如果没有了，那我们就取出堆栈中的下一个树枝节点，并以这个树枝节点为起点，看是否存在下一个节点。
试试这个迭代器威力如何：
static void depthFirstIterate(Node tree) {
doSomething(tree);
for (Iterator<Node> it = new DepthFirstIterator(tree.iterator()); it.hasNext();) {
doSomething(it.next());
}
}
如果doSomething(Node node)只是简单地打印这个节点，像这样：
static void doSomething(Node node) {
System.out.println(node);
}
那么你可以看到前面所述的顺序被打印出来 Root -> A -> D -> E -> B -> C -> F。当然，没有箭头，而且是分行显示的。
好的，这看起来确实不错，那么广度优先遍历呢？所谓广度优先，通俗来讲就是层层推进。首先遍历所有的第一级子节点，然后是第二层，第三层……结果就像是这样：Root -> A -> B -> C -> D -> F -> E
听起来更加简单，是不是？事实上做起来并不简单，除非你已经正确理解了上面深度优先遍历。
如果你理解了深度优先遍历，那么广度优先遍历和深度优先唯一不同的地方就是树枝节点的存取顺序。在深度优先遍历中，树枝节点使用堆栈，存取顺序是后进先出。先就是说，最后遇到（也就是后进）的树枝节点先拿出来用（就像插队一样，不得不承认这有点不公平）。那么，我们最先遇到的树枝节点是Root自己，然后是A，最后是D（不是E，因为E不是树枝节点）。根据后进先出的原则，我们先把D拿出来遍历，最终得到D的子节点是E。然后是A，最后才是Root，所以Root的第二个子节点B会在Root的第一个子节点遍历完成之后才能遍历到。
所以，只要我们将堆栈换成公平的强力支持者，先进先出的队列（Queue），问题就解决了：
因为Root最先进入队列，所以它的所有直属子节点会被先遍历，然后才轮到A，然后是C，然后是D。所以最终顺序会是这样：
Root -> A -> B -> C -> D -> F -> E
广度优先代码：
public class BreadthFirstIterator implements Iterator<Node> {
private Queue<Iterator<Node>> queue = new LinkedList<Iterator<Node>>();
public BreadthFirstIterator(Iterator<Node> it) {
queue.offer(it);
}
public boolean hasNext() {
if (queue.isEmpty()) {
return false;
} else {
Iterator<Node> it = queue.peek();
if (it.hasNext()) {
return true;
} else {
queue.poll();
return hasNext();
}
}
}
public Node next() {
if (hasNext()) {
Iterator<Node> it = queue.peek();
Node next = it.next();
if (next instanceof BranchNode) {
queue.offer(next.iterator());
}
return next;
} else {
return null;
}
}
public void remove() {
throw new UnsupportedOperationException("Can’t remove node, yet");
}
}
可以看到代码和深度优先遍历几乎完全一样，除了把堆栈（Stack）换成了队列（Queue）
上一页 [1] [2]
责任编辑：小草
