二叉樹的深度優先遍歷和廣度優先遍歷

** 深度優先搜索:深度優先搜索是一種在開發爬蟲早期使用較多的方法。它的目的是要達到被搜索結構的葉結點(即那些不包含任何超鏈的HTML文件) 。在一個HTML文件中,當一個超鏈被選擇後,被鏈接的HTML文件將執行深度優先搜索,即在搜索其餘的超鏈結果之前必須先完整地搜索單獨的一條鏈。深度優先搜索沿著HTML文件上的超鏈走到不能再深入為止,然後返回到某一個HTML文件,再繼續選擇該HTML文件中的其他超鏈。當不再有其他超鏈可選擇時,說明搜索已經結束。**

**寬度優先搜索:寬度優先搜索演算法(又稱廣度優先搜索)是最簡便的圖的搜索演算法之一,這一演算法也是很多重要的圖的演算法的原型。Dijkstra單源最短路徑演算法和Prim最小生成樹演算法都採用了和寬度優先搜索類似的思想。其別名又叫BFS,屬於一種盲目搜尋法,目的是系統地展開並檢查圖中的所有節點,以找尋結果。換句話說,它並不考慮結果的可能位置,徹底地搜索整張圖,直到找到結果為止。**   

兩者分別結合棧、隊列實現

一、生成二叉樹

二、編寫一個Node類

package com.lzp.util.tree;

/**
 * @Author LZP
 * @Date 2021/2/22 12:53
 * @Version 1.0
 */
public class Node {

    /**
     * 左孩子
     */
    public Node left;

    /**
     * 右孩子
     */
    public Node right;

    /**
     * 當前節點的值
     */
    public char data;

    public Node(Node left, Node right, char data) {
        this.left = left;
        this.right = right;
        this.data = data;
    }
}

三、編寫一個BTreeUtil工具類

package com.lzp.util.tree;

import java.util.Queue;
import java.util.Stack;
import java.util.concurrent.ArrayBlockingQueue;

/**
 * @Author LZP
 * @Date 2021/2/22 8:34
 * @Version 1.0
 *
 * 二叉樹
 */
public class BTreeUtil {

    /**
     * 創建二叉樹
     * @param arr 用於存儲待創建二叉樹中所有值的字元數組
     * @return 返回根節點
     */
    public static Node createBinaryTree(char[] arr) {
        Node root = null;
        for (int i = 0; i < arr.length; i++) {
            Node newNode = null;
            if (root == null) {
                root = new Node(null, null, arr[i]);
                continue;
            }
            if (!contains(root, arr[i])) {
                newNode = new Node(null, null, arr[i]);
                insertBinaryTreeNode(root, newNode);
            }
        }

        return root;
    }

    /**
     * 判斷二叉樹中是否包含指定字元
     * @param root 根節點
     * @param c 待判斷字元
     * @return
     */
    public static boolean contains(Node root, char c) {
        Queue<Node> queue = new ArrayBlockingQueue<Node>(10);
        queue.offer(root);
        while (!queue.isEmpty()) {
            Node node = queue.poll();
            if (node != null) {
                if (node.data == c) {
                    return true;
                }
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
        }
        return false;
    }

    /**
     * 通過BFS方式向二叉樹中插入節點
     * @param root 根節點
     * @param c 待插入節點的值
     */
    public static boolean insertBinaryTreeNode(Node root, char c) {
        if (!contains(root, c)) {
            Node newNode = new Node(null, null, c);
            return insertBinaryTreeNode(root, newNode);
        }

        return false;
    }

    /**
     * 通過BFS方式向二叉樹中插入節點
     * @param root 根節點
     * @param node 待插入節點
     */
    public static boolean insertBinaryTreeNode(Node root, Node node) {
        Queue<Node> queue = new ArrayBlockingQueue<Node>(10);
        queue.offer(root);
        while (!queue.isEmpty()) {
            Node temp = queue.poll();
            if (temp != null) {
                if (temp.left == null) {
                    temp.left = node;
                    // 記住,這裡是插入節點,一旦插入成功就直接返回,不用再循環
                    return true;
                } else {
                    if (temp.right == null) {
                        temp.right = node;
                        // 記住,這裡是插入節點,一旦插入成功就直接返回,不用再循環
                        return true;
                    } else {
                        // 將左右孩子都入隊
                        queue.offer(temp.left);
                        queue.offer(temp.right);
                    }
                }
            }
        }
        return false;
    }

    /**
     * 深度優先遍歷
     * 遞歸實現
     * @param root 根節點
     */
    public static void dfsDivision(Node root) {
        if (root == null) {
            return;
        }
        System.out.print(root.data + "\t");
        dfsDivision(root.left);
        dfsDivision(root.right);
    }

    /**
     * 深度優先遍歷
     * 迭代實現
     * @param root
     */
    public static void dfsIterator(Node root) {
        Stack<Node> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            root = stack.pop();
            if (root != null) {
                System.out.print(root.data + "\t");
                // 先將右孩子入棧,這裡是跟廣度優先遍歷中的隊列入隊剛好相反
                if (root.right != null) {
                    stack.push(root.right);
                }
                if (root.left != null) {
                    stack.push(root.left);
                }
            }
        }
    }

    /**
     * 廣度優先遍歷:廣度優先遍歷,也可以稱為層次優先遍歷,從上到下,先把每一層遍歷完之後再遍歷一下一層
     * @param root 根節點
     */
    public static void bfs(Node root) {
        Queue<Node> queue = new ArrayBlockingQueue<Node>(10);
        queue.offer(root);
        while (!queue.isEmpty()) {
            Node node = queue.poll();
            if (node != null) {
                System.out.print(node.data + "\t");
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
        }
    }
}

四、測試類

public class Test {
    public static void main(String[] args) {
        char[] cArr = new char[]{
                'B',
                'F',
                'A',
                'C',
                'E',
                'G',
                'D'};
        Node root = BTreeUtil.createBinaryTree(cArr);

        System.out.println("深度優先遍歷");
        BTreeUtil.dfsIterator(root);

        System.out.println();
        System.out.println("廣度優先遍歷");
        BTreeUtil.bfs(root);

    }
}

五、運行結果