tree.png

1. 二叉樹結(jié)構(gòu)定義

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

2. 數(shù)據(jù)初始化

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. 深度優(yōu)先遍歷

3.1 算法

dfs.png

深度優(yōu)先遍歷鳖枕，是指對每一個(gè)可能的分支路徑深入到不能再深入為止，而且每個(gè)節(jié)點(diǎn)只能訪問一次宾符。

二叉樹的深度優(yōu)先遍歷分為：先序遍歷，中序遍歷和后續(xù)遍歷

先序遍歷：先訪問根魏烫，在訪問左子樹肝箱，最后訪問右子樹考润，總結(jié)就是“根左右”；
中序遍歷：先訪問左子樹糊治，再訪問根，最后訪問右子樹绎谦，總結(jié)就是“左根右”；
后序遍歷：先訪問左子樹窃肠，再訪問右子樹刷允，最后訪問根，總結(jié)就是“左右根”树灶。

以下展示先序遍歷，利用了Java的Stack棧先進(jìn)后出的特性：

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先進(jìn)后出泊窘，所以先右后左
        if (node.right != null) {
            stack.push(node.right);
        }
        if (node.left != null) {
            stack.push(node.left);
        }
    }
    System.out.println();

}

3.2 執(zhí)行結(jié)果

1 2 4 5 8 3 6 7 9

4. 廣度優(yōu)先遍歷

4.1 算法

bfs.png

廣度優(yōu)先遍歷像寒，是指從上至下逐層訪問，又稱層次遍歷诺祸。每一層從左至右訪問，該層結(jié)束后進(jìn)入下一層訪問蚌卤，直至沒有節(jié)點(diǎn)為止。

以下展示廣度優(yōu)先遍歷，利用了Java的Queue隊(duì)列先進(jìn)先出的特性：

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先進(jìn)先出构订，所以先左后右
        if (node.left != null) {
            queue.add(node.left);
        }
        if (node.right != null) {
            queue.add(node.right);
        }
    }
    System.out.println();
}

4.1 執(zhí)行結(jié)果

1 2 3 4 5 6 7 8 9