二分搜索樹(shù)

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

定義
二叉搜索樹(shù)是以一顆二叉樹(shù)組織，每個(gè)節(jié)點(diǎn)就是一個(gè)對(duì)象吼虎，包括key犬钢，衛(wèi)星數(shù)據(jù)。除此之外還包括一些維護(hù)樹(shù)結(jié)構(gòu)所需要的信息：left思灰、light玷犹、parent，分別指向左孩子洒疚、右孩子歹颓、父節(jié)點(diǎn)。其中如果孩子節(jié)點(diǎn)或者父節(jié)點(diǎn)不存在時(shí)油湖，用null表示巍扛。根節(jié)點(diǎn)時(shí)樹(shù)中唯一一個(gè)父節(jié)點(diǎn)為null的節(jié)點(diǎn)。

一乏德、二叉樹(shù)性質(zhì)簡(jiǎn)介

1.如果節(jié)點(diǎn)的左孩子不為空撤奸，則左孩子樹(shù)上所有的節(jié)點(diǎn)的值均小于它的根節(jié)點(diǎn)的值吠昭。
2.如果節(jié)點(diǎn)的右孩子不為空，則右孩子樹(shù)上所有的節(jié)點(diǎn)的值均大于它的根節(jié)點(diǎn)的值胧瓜。
3.任意節(jié)點(diǎn)的左右孩子也分別為二叉搜索樹(shù)（只要滿足二叉搜索樹(shù)的基本結(jié)構(gòu)都屬于二叉搜索樹(shù)矢棚。）如下圖！８幻妓！

二分搜索樹(shù)

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

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

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

首先需要明確二分搜索樹(shù)的結(jié)構(gòu)特點(diǎn)肉津，二分搜索樹(shù)需要維護(hù)一個(gè)Node對(duì)象

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

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

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

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

維護(hù)整個(gè)樹(shù)的元素大小：
private int size;
提供根節(jié)點(diǎn)：
private Node root;
一個(gè)簡(jiǎn)單的二分搜索樹(shù)基本初始化完成舱沧。

二妹沙、添加功能

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

  public void add(E e) {

        root = NewAdd(root, e);
    }

    private Node NewAdd(Node node, E e) {
        // 判斷當(dāng)前二分樹(shù)是否為空
        if (node == null) {
            // 維護(hù)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;
    }

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

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

二分搜索樹(shù)的深度遍歷

說(shuō)明：
二分搜索樹(shù)的遍歷分為三大類：先序遍歷（preorder tree walk）、中序遍歷（inorder tree walk）帽氓、后序遍歷（postorder tree walk）

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

前序遞歸遍歷

二分搜索樹(shù)前序遍歷.gif

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

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

中序遞歸遍歷

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

    /**
     * 二分搜索樹(shù) 遞歸中序遍歷
     */
    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);
    }

后序遞歸遍歷

    /**
     * 二分搜索樹(shù) 遞歸后序遍歷
     */
    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);
    }

二分搜索樹(shù)非遞歸遍歷

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

簡(jiǎn)單的流程動(dòng)態(tài)圖：

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

    /**
     * 使用棧 實(shí)現(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)先進(jìn)后出的特性逝撬，需要向?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)實(shí)現(xiàn)二分搜索樹(shù)中序遍歷

中序遍歷相較于前序遍歷會(huì)比較的復(fù)雜（前序遍歷應(yīng)用的比較廣泛浴骂，這里視時(shí)間的充裕程度選擇閱讀）
首先分析
在使用棧結(jié)果實(shí)現(xiàn)中序遍歷的時(shí)候，需要重點(diǎn)考慮節(jié)點(diǎn)是否存在左孩子節(jié)點(diǎn)宪潮。當(dāng)節(jié)點(diǎn)有左孩子節(jié)點(diǎn)時(shí)溯警，需要將該節(jié)點(diǎn)優(yōu)先入棧，如果該節(jié)點(diǎn)沒(méi)有左孩子節(jié)點(diǎn)狡相，此時(shí)應(yīng)該訪問(wèn)該節(jié)點(diǎn)梯轻。再考慮有葉子節(jié)點(diǎn)。
操作步驟
步驟一：如果節(jié)點(diǎn)有左葉子節(jié)點(diǎn)尽棕，將該節(jié)點(diǎn)入棧喳挑，如果節(jié)點(diǎn)沒(méi)有左葉子節(jié)點(diǎn)，訪問(wèn)當(dāng)前節(jié)點(diǎn)萄金。
步驟二：如果節(jié)點(diǎn)有右葉子節(jié)點(diǎn)蟀悦，重復(fù)步驟一媚朦，如果節(jié)點(diǎn)沒(méi)有有葉子節(jié)點(diǎn)（該節(jié)點(diǎn)下所有的子節(jié)點(diǎn)訪問(wèn)完畢）回退氧敢，讓棧頂元素出棧，并且訪問(wèn)棧頂元素的右葉子元素询张，然后重復(fù)步驟一孙乖。
步驟二：當(dāng)棧為空時(shí)，說(shuō)明遍歷結(jié)束
代碼如下：

 /**
     * 棧 實(shí)現(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é)點(diǎn)如果有左葉子節(jié)點(diǎn)份氧，該節(jié)點(diǎn)入棧唯袄，
         *      如果該節(jié)點(diǎn)沒(méi)有左葉子節(jié)點(diǎn)，訪問(wèn)該節(jié)點(diǎn)
         *  步驟2：如果節(jié)點(diǎn)有右葉子節(jié)點(diǎn)蜗帜，重復(fù)步驟1
         *      如果節(jié)點(diǎn)沒(méi)有右葉子節(jié)點(diǎn)（說(shuō)明訪問(wèn)完畢）回退恋拷，讓棧頂元素出棧，并且訪問(wèn)棧頂元素的右葉子樹(shù)厅缺，重復(fù)步驟1
         *  步驟3：當(dāng)棧為空時(shí)蔬顾，遍歷結(jié)束
         */
        Node cur = node;
        // 判斷 當(dāng)前節(jié)點(diǎn) 是否為空宴偿，并且 棧是否遍歷完結(jié)
        while (cur != null || !nodeStack.empty()) {
            // 將當(dāng)前節(jié)點(diǎn)下所有的左葉子節(jié)點(diǎn)壓入棧頂
            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)實(shí)現(xiàn)二分搜索樹(shù)后序遍歷

    /**
     * 棧 實(shí)現(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é)點(diǎn)的所有右孩子節(jié)點(diǎn)訪問(wèn)完畢后诀豁，該節(jié)點(diǎn)才可以出棧
             */
            // 先遍歷所有的左孩子節(jié)點(diǎn)
            while (cur != null) {
                nodeStack.push(cur);
                cur = cur.left;
            }
            cur = nodeStack.peek();
            if (cur.right == null) {
                // 當(dāng)前節(jié)點(diǎn) 為左節(jié)點(diǎn)的最后一個(gè)節(jié)點(diǎn)窄刘，添加到結(jié)果集中，并且將當(dāng)前cur 設(shè)置為棧頂值舷胜。
                result.add(cur.e);
                // 該節(jié)點(diǎn) 出棧
                nodeStack.pop();
                //判斷此時(shí)的棧頂?shù)挠液⒆邮欠衽c當(dāng)前的cur 相等娩践，相等 則說(shuō)明 該棧頂元素下面的所有元素遍歷完畢，需要出棧
                while (!nodeStack.empty() && nodeStack.peek().right.equals(cur)) {
                    cur = nodeStack.peek();
                    result.add(nodeStack.pop().e);
                }
                //將 此時(shí)棧頂?shù)挠液⒆?賦值給cur
                cur = nodeStack.empty() ? null : nodeStack.peek().right;
            } else {
                // 該節(jié)點(diǎn)沒(méi)有左葉子樹(shù)烹骨，但是有右葉子樹(shù),并將右葉子節(jié)點(diǎn)復(fù)制給cur
                cur = cur.right;
            }

        }
        return result;
    }

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

二分搜索樹(shù)的廣度遍歷（層序遍歷）

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

    /**
     * 廣度優(yōu)先遍歷（層序遍歷） 使用隊(duì)列
     *
     * @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í)記錄未妹。如有不對(duì)的地方還望指出和諒解。謝謝
祝各位工作順利空入！