深度优先遍历算法（DFS）

深度优先遍历算法（Depth-First-Search），是一种用于遍历或搜索树或图的算法。这个算法会尽可能深地搜索树的分支。当节点v所在的边都一杯探寻过，搜索将回溯到发现节点v的那条边的节点。选择其中一个座位源节点并重复以上过程，整个进程反复进行，直到所有节点都被访问位置。

前序、中序、后序遍历都属于深度优先遍历算法

前序遍历

F, B, A, D, C, E, G, I, H.

前序遍历

中序遍历

A, B, C, D, E, F, G, H, I.

中序遍历

后续遍历

A, C, E, D, B, H, I, G, F.

后续遍历

广度优先遍历（BFS）

广度优先遍历（Breadth-First Search），又名宽度优先搜索，或者横向优先搜索，是一种图形搜索演算法。简单的说，BFS是从根节点开始，沿着树的宽度遍历树的节点，如果所有节点均被访问，则算法终止。

F, B, G, A, D, I, C, E, H.

广度遍历

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
public class TreeSearch {

    public Node initTree() {
        BinaryTree<Integer> binaryTree = new BinaryTree<Integer>();
        binaryTree.put(3);
        binaryTree.put(5);
        binaryTree.put(1);
        binaryTree.put(2);
        binaryTree.put(10);
        binaryTree.put(0);
        binaryTree.put(4);

        Node root = binaryTree.getRoot();

        BTreePrinter.printNode(root);

        return root;
    }

    /**
     * 深度优先 - 递归
     */
    public void DFS() {
        Node root = initTree();
        DFS(root);
    }


    public void DFS(Node x) {
        if (x == null) return;
        System.out.print(x.value + " ");
        DFS(x.left);
        DFS(x.right);
    }

    public void BFS() {
        Queue<Comparable> res = new LinkedList<>();
        Queue<Node> q = new LinkedList<>();

        Node root = initTree();

        // 入队
        q.offer(root);
        while (!q.isEmpty()) {
            // 出队
            Node e = q.poll();
            if (e == null) {
                return;
            }

            if (e.left != null) {
                q.offer(e.left);
            }

            if (e.right != null) {
                q.offer(e.right);
            }

//            res.offer(e.value);
            System.out.print(e.value + " ");
        }
//        System.out.println(res);
    }

    public static void main(String[] args) {

        TreeSearch treeSearch = new TreeSearch();
        treeSearch.BFS();
        System.out.println();

        treeSearch.DFS();
    }
}

结果如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
   3       
  / \   
 /   \  
 1   5   
/ \ / \ 
0 2 4 10 
                
3 1 5 0 2 4 10 
   3       
  / \   
 /   \  
 1   5   
/ \ / \ 
0 2 4 10 
                
3 1 0 2 5 4 10