二分搜索樹

前言：
在計算機科學(xué)中，二分搜索樹（Binary Search Tree）
（有時稱為有序或者排序的二叉樹）是一種能存儲特定數(shù)據(jù)類型的容器，二叉搜索樹 允許快速查找、添加或者刪除某一個節(jié)點，并且它是動態(tài)的集合。
二叉搜索樹按照關(guān)鍵字順序地保存節(jié)點，因此查找和其他操作可以使用二叉搜索原理：當(dāng)在樹（或者尋找插入新節(jié)點的地方）中查找節(jié)點時，它從根節(jié)點遍歷到葉子節(jié)點，與每個節(jié)點的關(guān)鍵字進行比較，然后基于比較的結(jié)果，決定繼續(xù)在左子樹還是在右子樹中進行搜索比較。這樣一來，每次比較理論上都活篩選掉一半的元素，這樣使得每次查找，插入或者刪除一個節(jié)點所花費的時間與樹的節(jié)點個數(shù)的對數(shù)成（樹的高度）正比，比線性表的性能要好很多。

定義
二叉搜索樹是以一顆二叉樹組織，每個節(jié)點就是一個對象，包括key，衛(wèi)星數(shù)據(jù)。除此之外還包括一些維護樹結(jié)構(gòu)所需要的信息：left、light、parent，分別指向左孩子、右孩子、父節(jié)點。其中如果孩子節(jié)點或者父節(jié)點不存在時，用null表示。根節(jié)點時樹中唯一一個父節(jié)點為null的節(jié)點。

一、二叉樹性質(zhì)簡介

1.如果節(jié)點的左孩子不為空，則左孩子樹上所有的節(jié)點的值均小于它的根節(jié)點的值。
2.如果節(jié)點的右孩子不為空，則右孩子樹上所有的節(jié)點的值均大于它的根節(jié)點的值。
3.任意節(jié)點的左右孩子也分別為二叉搜索樹（只要滿足二叉搜索樹的基本結(jié)構(gòu)都屬于二叉搜索樹。）如下圖?。?！

二分搜索樹

這里是本人寫的一個不支持重復(fù)數(shù)據(jù)的簡單的二叉搜索樹的源碼！
https://gitee.com/ligangyun/data_structure/tree/master/BinarySearchTree

構(gòu)建二分搜索樹

一、初始化二分搜索樹對象（本實現(xiàn)樹對象不滿足包含重復(fù)數(shù)據(jù)）

首先需要明確二分搜索樹的結(jié)構(gòu)特點，二分搜索樹需要維護一個Node對象

    private class Node {
        E e;
        Node left, right;

        /**
         * 提供構(gòu)造方法
         *
         * @param e 真實元素
         */
        Node(E e) {
            this.e = e;
            left = null;
            right = null;
        }
    }

提供構(gòu)造函數(shù)

  /**
     * 提供無參構(gòu)造
     */
    public BST() {
        root = null;
        size = 0;
    }

維護整個樹的元素大?。?br> private int size;
提供根節(jié)點：
private Node root;
一個簡單的二分搜索樹基本初始化完成。

二、添加功能

首先在網(wǎng)二分樹中添加元素時，需要計算出該元素添加的位置，所以需要使用到遞歸算法，計算出添加的元素具體的添加位置。

  public void add(E e) {

        root = NewAdd(root, e);
    }

    private Node NewAdd(Node node, E e) {
        // 判斷當(dāng)前二分樹是否為空
        if (node == null) {
            // 維護size 的大小
            size++;
            return new Node(e);
        }
        if (e.compareTo(node.e) < 0) {
            node.left = NewAdd(node.left, e);
        } else if (e.compareTo(node.e) > 0) {
            node.right = NewAdd(node.right, e);
        }
        return node;
    }

這里的元素對比是在二分樹泛型中繼承java comparable 類 實現(xiàn)的

其他一些列操作 包含 刪除 查找等操作都是居于遞歸實現(xiàn)的！本人提供的源碼均詳細實現(xiàn)。

二分搜索樹的深度遍歷

說明：
二分搜索樹的遍歷分為三大類：先序遍歷（preorder tree walk）、中序遍歷（inorder tree walk）、后序遍歷（postorder tree walk）

使用遞歸的方式訪問節(jié)點每個節(jié)點都會被訪問三次
1.首先訪問當(dāng)前節(jié)點。
2.再訪問該節(jié)點的左孩子，再會回到該節(jié)點，訪問該節(jié)點的右孩子
3.最終右孩子訪問結(jié)束后，還是返回到該節(jié)點，標(biāo)志著該節(jié)點即下面的所有子節(jié)點都訪問完畢！

前序遞歸遍歷

二分搜索樹前序遍歷.gif

   /**
     * 二分搜索樹 遞歸前序遍歷
     */
    public void preOrder() {
        preOrder(root);
    }

    private void preOrder(Node node) {
        if (node == null) {
            return;
        }
        System.out.println(node.e);
        // 遞歸遍歷 左右孩子節(jié)點,這里一定要注意左孩子在前面
        preOrder(node.left);
        preOrder(node.right);
    }

中序遞歸遍歷

原理與前序遍歷基本相同，只是在節(jié)點第二次出現(xiàn)時，獲取節(jié)點信息。

    /**
     * 二分搜索樹 遞歸中序遍歷
     */
    public void inOrder() {
        inOrder(root);
    }

    private void inOrder(Node node) {
        if (node == null) {
            return;
        }
        inOrder(node.left);
        System.out.println(node.e);
        inOrder(node.right);
    }

后序遞歸遍歷

    /**
     * 二分搜索樹 遞歸后序遍歷
     */
    public void postOrder() {
        postOrder(root);
    }

    private void postOrder(Node node) {
        if (node == null) {
            return;
        }
        postOrder(node.left);
        postOrder(node.right);
        System.out.println(node.e);
    }

二分搜索樹非遞歸遍歷

使用棧線性結(jié)構(gòu)實現(xiàn)二分搜索樹前序遍歷

簡單的流程動態(tài)圖：

使用棧實現(xiàn)二分搜索樹前序遍歷.gif

    /**
     * 使用棧 實現(xiàn)前序遍歷
     */
    public void preOrderByStack() {
        preOrderByStack(root);
    }

    private void preOrderByStack(Node node) {
        if (node == null) {
            return;
        }
        Stack<Node> stack = new Stack<>();
        stack.push(node);
        // 有序棧結(jié)構(gòu)先進后出的特性，需要向?qū)⒂液⒆酉扔谧蠛⒆訅喝霔５?        while (!stack.isEmpty()) {
            Node pop = stack.pop();
            System.out.println(pop.e);
            if (pop.right != null) {
                stack.push(pop.right);
            }
            if (pop.left != null) {
                stack.push(pop.left);
            }
        }
    }

使用棧線性結(jié)構(gòu)實現(xiàn)二分搜索樹中序遍歷

中序遍歷相較于前序遍歷會比較的復(fù)雜（前序遍歷應(yīng)用的比較廣泛，這里視時間的充裕程度選擇閱讀）
首先分析
在使用棧結(jié)果實現(xiàn)中序遍歷的時候，需要重點考慮節(jié)點是否存在左孩子節(jié)點。當(dāng)節(jié)點有左孩子節(jié)點時，需要將該節(jié)點優(yōu)先入棧，如果該節(jié)點沒有左孩子節(jié)點，此時應(yīng)該訪問該節(jié)點。再考慮有葉子節(jié)點。
操作步驟
步驟一：如果節(jié)點有左葉子節(jié)點，將該節(jié)點入棧，如果節(jié)點沒有左葉子節(jié)點，訪問當(dāng)前節(jié)點。
步驟二：如果節(jié)點有右葉子節(jié)點，重復(fù)步驟一，如果節(jié)點沒有有葉子節(jié)點（該節(jié)點下所有的子節(jié)點訪問完畢）回退，讓棧頂元素出棧，并且訪問棧頂元素的右葉子元素，然后重復(fù)步驟一。
步驟二：當(dāng)棧為空時，說明遍歷結(jié)束
代碼如下：

 /**
     * 棧 實現(xiàn) 中序遍歷
     */
    public ArrayList<E> inOrderByStack() {
        return inOrderByStack(root);
    }

    private ArrayList<E> inOrderByStack(Node node) {
        ArrayList<E> result = new ArrayList<>();
        if (node == null) {
            return result;
        }
        Stack<Node> nodeStack = new Stack<>();
        /**
         * 分析：
         *  步驟1：節(jié)點如果有左葉子節(jié)點，該節(jié)點入棧，
         *      如果該節(jié)點沒有左葉子節(jié)點，訪問該節(jié)點
         *  步驟2：如果節(jié)點有右葉子節(jié)點，重復(fù)步驟1
         *      如果節(jié)點沒有右葉子節(jié)點（說明訪問完畢）回退，讓棧頂元素出棧，并且訪問棧頂元素的右葉子樹，重復(fù)步驟1
         *  步驟3：當(dāng)棧為空時，遍歷結(jié)束
         */
        Node cur = node;
        // 判斷 當(dāng)前節(jié)點 是否為空，并且 棧是否遍歷完結(jié)
        while (cur != null || !nodeStack.empty()) {
            // 將當(dāng)前節(jié)點下所有的左葉子節(jié)點壓入棧頂
            while (cur != null) {
                nodeStack.push(cur);
                cur = cur.left;// 定義當(dāng)前變量
            }
            // 獲取棧頂元素
            cur = nodeStack.peek();
            result.add(cur.e);
            // 彈出棧頂
            nodeStack.pop();
            cur = cur.right;
        }
        return result;
    }

使用棧線性結(jié)構(gòu)實現(xiàn)二分搜索樹后序遍歷

    /**
     * 棧 實現(xiàn)后序遍歷
     *
     * @return
     */
    public ArrayList<E> postOrderByStack() {
        return postOrderByStack(root);
    }

    private ArrayList<E> postOrderByStack(Node node) {
        ArrayList<E> result = new ArrayList<>();
        Stack<Node> nodeStack = new Stack<>();
        Node cur = node;
        while (cur != null || !nodeStack.empty()) {
            /**
             * 分析：
             *  后序遍歷 在中序遍歷的基礎(chǔ)上，需要注意的是：節(jié)點的所有右孩子節(jié)點訪問完畢后，該節(jié)點才可以出棧
             */
            // 先遍歷所有的左孩子節(jié)點
            while (cur != null) {
                nodeStack.push(cur);
                cur = cur.left;
            }
            cur = nodeStack.peek();
            if (cur.right == null) {
                // 當(dāng)前節(jié)點 為左節(jié)點的最后一個節(jié)點，添加到結(jié)果集中，并且將當(dāng)前cur 設(shè)置為棧頂值。
                result.add(cur.e);
                // 該節(jié)點 出棧
                nodeStack.pop();
                //判斷此時的棧頂?shù)挠液⒆邮欠衽c當(dāng)前的cur 相等，相等 則說明 該棧頂元素下面的所有元素遍歷完畢，需要出棧
                while (!nodeStack.empty() && nodeStack.peek().right.equals(cur)) {
                    cur = nodeStack.peek();
                    result.add(nodeStack.pop().e);
                }
                //將 此時棧頂?shù)挠液⒆?賦值給cur
                cur = nodeStack.empty() ? null : nodeStack.peek().right;
            } else {
                // 該節(jié)點沒有左葉子樹，但是有右葉子樹,并將右葉子節(jié)點復(fù)制給cur
                cur = cur.right;
            }

        }
        return result;
    }

以上所有遍歷都可以劃分為 二分搜索樹的深度優(yōu)先遍歷：對每一個可能的分支路徑深入到不能再深入為止

二分搜索樹的廣度遍歷（層序遍歷）

廣度遍歷：從上往下對每一層依次訪問，在每一層中，從左往右（也可以從右往左）訪問結(jié)點，訪問完一層就進入下一層，直到?jīng)]有結(jié)點可以訪問為止。廣度優(yōu)先遍歷的非遞歸的通用做法是采用隊列。
利用隊列實現(xiàn)層序遍歷

    /**
     * 廣度優(yōu)先遍歷（層序遍歷） 使用隊列
     *
     * @return
     */
    public ArrayList<E> sequenceOrder() {
        return sequenceOrder(root);
    }

    private ArrayList<E> sequenceOrder(Node node) {
        ArrayList<E> result = new ArrayList<>();
        if (node == null)
            return result;
        Queue<Node> nodeQueue = new LinkedList<>();
        nodeQueue.add(node);
        while (!nodeQueue.isEmpty()) {
            Node cur = nodeQueue.remove();
            result.add(cur.e);
            if (cur.left != null)
                nodeQueue.add(cur.left);
            if (cur.right != null) {
                nodeQueue.add(cur.right);
            }
        }
        return result;
    }

此文經(jīng)作為作者學(xué)習(xí)記錄。如有不對的地方還望指出和諒解。謝謝
祝各位工作順利！