Tree的深度优先及广度优先节点遍历 DFS and BFS on Tree

DFS(Depth-First Search)和BFS(Breadth-First Search)是两种用于访问图(graph)中节点最普遍的两种方法。在我的日常编程中，使用的graph的绝大部分都是树(tree). Tree是一种connected acyclic graph - 连通(即从一个节点一定有路径到其他任何节点)的无循环图. 本文所述内容仅限于tree, 不适用于graph.

 

DFS 深度优先

假设右边的树代表一个公司的组织架构，每个node是一个部门。若要计算部门c的总收入，我们必须先知道e和f的，而要知道e的总收入我们必须先知道g和h，这就是典型的深度优先。深度优先通过递归来实现，代码如下：

 

 

 

visitDFS(a); // visit from the root 

// performs DFS from the given node
public void visitDFS(Node nodeStart) {
  // (1) Entering node - pre-order walk 
  for(Node child : nodeStart.children) {
    visitDFS(child); // recursive call 
  }
  // (2) Leaving node - post-order walk 
  System.out.println("DFS: " + nodeStart.nodeName);
}

在代码中，我做了两个标记(1)和(2). 在(1)处，当前节点的所有下属节点尚未被访问，而在(2)处，其所有下属节点均被处理完毕。若要计算部门收入，很明显是在(2)处。上面代码打印结果是：d b g h e f c a

BFS 广度优先

假设我们要打印各部门收入报表给CEO，因为每个部门收入数据较多，CEO倾向先看各大部门(只有对某部门数据有疑惑时，才看小部门), 这样情况下是先打印大部门，再打印小部门，低等级部门后打印，这就是广度优先的情况。graph的BFS算法较繁琐，但tree的BFS就非常简单了：

 

visitBFS(a); // visit from the root 
  
// performs BFS from the given node
public void visitBFS(Node nodeStart) {
  List<NODE> pendingExplore = new ArrayList<NODE>(); // list of nodes pending exploration 
  pendingExplore.add(nodeStart);
  while(pendingExplore.size() > 0) {
    Node currentNode = pendingExplore.remove(0);
    System.out.println("BFS: " + currentNode.nodeName);
    pendingExplore.addAll(currentNode.children); // (3) 
  }
}

上面代码打印结果: a b c d e f g h. 有时同级部门之间还有顺序，譬如重要产品部门比技术支持部门往往排序靠前，要实现这个非常简单，在(3)处，将子节点添加到pendingExplore之前进行sort即可。

 

附：测试程序的完整代码：

 

public class TestTree {
    public Node a;

    @SuppressWarnings("unused")
    public TestTree() {
        // Construct the tree.

        a = new Node("a");
        Node b = a.createChildNode("b");
        Node c = a.createChildNode("c");
        Node d = b.createChildNode("d");
        Node e = c.createChildNode("e");
        Node f = c.createChildNode("f");
        Node g = e.createChildNode("g");
        Node h = e.createChildNode("h");
    }

    public void testDFS() {
        System.out.println("Testing DFS");
        visitDFS(a); // visit from the root

    }

    // performs DFS from the given node

    public void visitDFS(Node nodeStart) {
        // Entering node - pre-order walk

        for (Node child : nodeStart.children) {
            visitDFS(child); // recursive call

        }
        // Leaving node - post-order walk

        System.out.println("DFS: " + nodeStart.nodeName);
    }

    public void testBFS() {
        System.out.println("Testing BFS");
        visitBFS(a); // visit from the root

    }

    // performs BFS from the given node

    public void visitBFS(Node nodeStart) {
        List<Node> pendingExplore = new ArrayList<Node>(); // list of nodes

        // pending

        // exploration

        pendingExplore.add(nodeStart);
        while (pendingExplore.size() > 0) {
            Node currentNode = pendingExplore.remove(0);
            System.out.println("BFS: " + currentNode.nodeName);
            pendingExplore.addAll(currentNode.children);
        }
    }

    // Application entry point

    public static void main(String[] args) {
        TestTree testTree = new TestTree();
        testTree.testBFS();
        testTree.testDFS();
    }

    // Node class

    public static class Node {
        public Node parent;
        public List<Node> children = new ArrayList<Node>();

        public String nodeName;

        public Node(String nodeName) {
            this.nodeName = nodeName;
        }

        public Node createChildNode(String childNodeName) {
            Node child = new Node(childNodeName);
            child.parent = this;
            children.add(child);
            return child;
        }
    }
}