二叉树之深度优先和广度优先遍历（Java）

tree.png

1. 二叉树结构定义

public static class Tree {
    int data;
    Tree left;
    Tree right;
    public Tree(int data) {
        this.data = data;
    }
}

2. 数据初始化

public static Tree initTree() {
    Tree node1 = new Tree(1);
    Tree node2 = new Tree(2);
    Tree node3 = new Tree(3);
    Tree node4 = new Tree(4);
    Tree node5 = new Tree(5);
    Tree node6 = new Tree(6);
    Tree node7 = new Tree(7);
    Tree node8 = new Tree(8);
    Tree node9 = new Tree(9);

    node1.left = node2;
    node1.right = node3;
    node2.left = node4;
    node2.right = node5;
    node3.left = node6;
    node3.right = node7;
    node5.right = node8;
    node7.left = node9;
    return node1;
}

3. 深度优先遍历

3.1 算法

dfs.png

深度优先遍历，是指对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次。

二叉树的深度优先遍历分为：先序遍历，中序遍历和后续遍历

先序遍历：先访问根，在访问左子树，最后访问右子树，总结就是“根左右”；
中序遍历：先访问左子树，再访问根，最后访问右子树，总结就是“左根右”；
后序遍历：先访问左子树，再访问右子树，最后访问根，总结就是“左右根”。

以下展示先序遍历，利用了Java的Stack栈先进后出的特性：

public static void deepFirstSearch(Tree tree) {
    Stack<Tree> stack = new Stack<>();
    stack.push(tree);

    while (!stack.isEmpty()) {
        Tree node = stack.pop();
        System.out.print(node.data + " ");

        // stack先进后出，所以先右后左
        if (node.right != null) {
            stack.push(node.right);
        }
        if (node.left != null) {
            stack.push(node.left);
        }
    }
    System.out.println();

}

3.2 执行结果

1 2 4 5 8 3 6 7 9

4. 广度优先遍历

4.1 算法

bfs.png

广度优先遍历，是指从上至下逐层访问，又称层次遍历。每一层从左至右访问，该层结束后进入下一层访问，直至没有节点为止。

以下展示广度优先遍历，利用了Java的Queue队列先进先出的特性：

public static void broadFirstSearch(Tree tree) {
    Queue<Tree> queue = new LinkedList<>();
    queue.add(tree);

    while (!queue.isEmpty()) {
        Tree node = queue.poll();
        System.out.print(node.data + " ");

        // queue先进先出，所以先左后右
        if (node.left != null) {
            queue.add(node.left);
        }
        if (node.right != null) {
            queue.add(node.right);
        }
    }
    System.out.println();
}

4.1 执行结果

1 2 3 4 5 6 7 8 9