樹結構簡介
二分搜索樹的基礎知識
- 二叉樹的基本概念
- 二分搜索樹的基本概念
- 二分搜索樹的基本結構代碼實作
二分搜索樹的常見基本操作實作
- 添加操作
  - 添加操作初步實作
  - 添加操作改進
- 查詢操作
- 遍歷操作
  - 前序遍歷
  - 中序遍歷
  - 后序遍歷
  - 前、中、后序遍歷的非遞回實作
    - 前序遍歷的非遞回實作
    - 中序遍歷的非遞回實作
    - 后序遍歷的非遞回實作
  - 層序遍歷
- 洗掉操作
  - 洗掉最大元素和最小元素
  - 洗掉任意元素

樹結構簡介

在線性資料結構中，資料都是排成一排存放的；而樹結構則是非線性的，存盤在其中的資料是按分支關系組織起來的結構，就像自然界中的樹那樣，如下圖所示：
從圖可以看出樹結構是有一種層次感的，每一個點可以有多個分支，這種組織結構是非常有優勢的，簡單來說樹結構本身是一種天然的組織結構，
對于這種組織結構，日常生活中是非常常見的，比如電腦磁盤中的檔案夾、公司中的人員組織結構、家族的族譜等等，如以下幾圖所示：
除了組織資料，使用樹結構存盤資料時，在某些情況下，處理資料是十分高效的，而我們就可以針對各種特殊情況去設計出各情況適合的高效率的樹結構，
- 舉個例子：比如對于查找一個資料，在線性結構中如果不知道具體位置的話需要在一堆資料里一個一個地去尋找；而對于樹結構，因為樹結構分支的形式，各個資料可以存在不同的分支中，在查找時就可以依據這些分支快速地找到想要的資料，
- 比如，磁盤中不同的檔案夾存放不同的檔案，我們在查找一個檔案時，就可以根據檔案夾名稱去找到想要的檔案，
以上就是樹結構的一些特點的簡單介紹，接下來就開始分析一下樹結構中的二分搜索樹的基礎知識以及實作出這個資料結構的一些常用操作，

二分搜索樹的基礎知識

二叉樹的基本概念

在了解二分搜索樹之前，需要先了解二叉樹的基本概念，因為二分搜索樹是基于二叉樹的，實際上，二叉樹是樹結構中最常見的樹結構，也是樹結構中最為基礎的結構，
對于二叉樹，和鏈表一樣，也是一種動態的資料結構，用戶不需要擔心容量的問題，設計者也不需要手動地設計動態伸縮容量的方法，
同時，二叉樹也是由一個一個節點組成的，而對于其中的每一個節點，除了存盤資料之外，還需要有兩個子節點，分別指向這個節點的左節點和右節點（也稱為左孩子和右孩子），
此外，二叉樹還具有以下特性:
1. 二叉樹具有唯一根節點，
2. 二叉樹每個節點最多有兩個孩子，
3. 二叉樹中沒有孩子的節點稱為葉子節點，
4. 二叉樹每個節點最多只有一個父親節點，
5. 二叉樹具有天然的遞回結構:
  1. 每個節點的左子樹也是二叉樹，（每個節點的左節點是左子樹的根節點）
  2. 每個節點的右子樹也是二叉樹，（每個節點的右節點是右子樹的根節點）
6. 二叉樹不一定是滿的:
  1. 一個節點也是二叉樹，（左右孩子為空）
  2. NULL（空）也是二叉樹，
以上特性歸納為圖片表示如下:
二叉樹的幾種常見形態
1. 空二叉樹
2. 只有一個節點的二叉樹
3. 只有左節點的二叉樹
4. 只有右節點的二叉樹
5. 完全二叉樹
6. 滿二叉樹

二分搜索樹的基本概念

在了解了以上二叉樹的基本概念之后，那么對于二分搜索樹就不需要再了解以上概念了，因為二分搜索樹就是一棵二叉樹，只不過它有屬于它自己的一些特性，
對于二分搜索樹，它具有以下特性:
1. 二分搜索樹的每個節點的值大于其左子樹的所有節點的值，
2. 二分搜索樹的每個節點的值小于其右子樹的所有節點的值，
3. 二分搜索樹的每一棵子樹也是二分搜索樹，
4. 二分搜索樹存盤的元素必須有可比較性，
二分搜索樹圖示

二分搜索樹的基本結構代碼實作

綜上以上基本概念，可設計二分搜索樹的基本結構的代碼如下:

/**
 * 二分搜索樹資料結構實作類
 * 支持具有可比較性的泛型
 *
 * @author 踏雪彡尋梅
 * @date 2020/3/2 - 23:05
 */
public class BST<E extends Comparable<E>> {
    /**
     * 二分搜索樹的節點
     */
    private class Node {
        /**
         * 存盤在節點中的元素
         */
        public E element;

        /**
         * 左節點（左孩子）
         */
        public Node left;

        /**
         * 右節點（右孩子）
         */
        public Node right;

        /**
         * 節點類建構式
         * 構造一個沒有左右孩子的節點
         * @param element 存盤在節點中的元素
         */
        public Node(E element) {
            this.element = element;
            this.left = null;
            this.right = null;
        }
    }

    /**
     * 二分搜索樹的根節點
     */
    private Node root;

    /**
     * 二分搜索樹當前節點個數
     */
    private int size;

    /**
     * 二分搜索樹類建構式
     * 構造一個空的二分搜索樹
     */
    public BST() {
        this.root = null;
        this.size = 0;
    }

    /**
     * 獲取二分搜索樹當前節點個數
     * @return 回傳當前二分搜索樹中節點個數
     */
    public int size() {
        return size;
    }

    /**
     * 判斷當前二分搜索樹是否為空樹
     * @return 回傳 true,表示當前二分搜索樹為空樹;回傳 false,表示當前二分搜索樹不為空樹
     */
    public boolean isEmpty() {
        // 判斷 size 是否為 0 即可
        return size == 0;
    }
}

二分搜索樹的常見基本操作實作

添加操作

添加操作初步實作

對于二分搜索樹的添加操作，可分為以下兩種情況（為了更加簡潔明了，此處使用動圖表示）:
1. 空樹時添加一個新元素:
2. 樹中已有元素時添加新元素:
以上就是添加元素的程序，其中需要注意的是在這里的二分搜索樹的實作中，不包含重復元素，如果添加的元素已有了直接回傳忽略，
如果需要包含重復元素，只需要定義為：左子樹小于等于父節點，右子樹大于等于父節點，
對于其代碼實作，可以使用非遞回方式也可以使用遞回方式，對于非遞回方式，實作步驟其實和鏈表比較相像；但是在樹結構中，遞回實作是比非遞回方式簡單的，所以在這里使用遞回的方式來實作，
不過使用遞回方式也是有一定的局限性的，比如在添加元素的最壞的情況下，二分搜索樹會形成一個鏈表（只添加左節點或右節點），這種情況下一直添加元素，由于不斷地遞回，遞回高度越來越高，記憶體將會被撐爆，這一點也是需要了解的，
從以上圖示中，可歸納為以下步驟（遞回實作）:
1. 添加元素前，先判斷當前二分搜索樹是否為空，如果為空將元素添加到根節點中；如果不為空，從根節點開始，遞回將元素添加到樹中，
2. 遞回終止條件:
  1. 添加的元素在樹中已有，直接忽略掉回傳即可，（不包含重復元素）
  2. 如果添加的元素添加到某個節點的左節點中且當前這個節點的左節點為空，則將元素添加到當前這個節點的左節點中并回傳回去，
  3. 如果添加的元素添加到某個節點的右節點中且當前這個節點的右節點為空，則將元素添加到當前這個節點的右節點中并回傳回去，
3. 如果不滿足以上終止條件，進行遞回添加元素:
  1. 如果添加的元素比當前節點的元素小，添加到當前節點的左子樹中，
  2. 如果添加的元素比當前節點的元素大，添加到當前節點的右子樹中，

以上步驟實作為代碼形式如下:

/**
 * 向二分搜索樹中添加新的元素 element
 * @param element 添加的新元素
 */
public void add(E element) {
    // 判斷二分搜索樹是否為空
    if (root == null) {
        // 二分搜索樹為空,將新元素添加到根節點中
        root = new Node(element);
        size++;
    } else {
        // 二分搜索樹不為空,從根節點開始遞回地添加新元素
        add(root, element);
    }
}

/**
 * 向根節點為 node 的二分搜索樹中添加元素 element
 * 遞回函式
 * @param node 添加元素的二分搜索樹的根節點
 * @param element 添加的元素
 */
private void add(Node node, E element) {
    // 終止條件
    if (node.element.equals(element)) {
        // 添加的元素已有,忽略回傳
        return;
    } else if (element.compareTo(node.element) < 0 && node.left == null) {
        // 添加的元素添加到某個節點的左節點時（該節點的左節點為空）
        node.left = new Node(element);
        size++;
        return;
    } else if (element.compareTo(node.element) > 0 && node.right == null) {
        // 添加的元素添加到某個節點的右節點時（該節點的右節點為空）
        node.right = new Node(element);
        size++;
        return;
    }

    // 不滿足終止條件時,遞回的進行添加元素
    if (element.compareTo(node.element) < 0) {
        // 比當前節點小,添加到左子樹中
        add(node.left, element);
    } else {
        // 比當前節點大,添加到右子樹中
        add(node.right, element);
    }
}

添加操作改進

在上面的添加操作實作中，在添加新元素的時候進行了兩輪的比較，第一輪是在終止條件時比較，第二輪是不滿足終止條件時比較，這樣子看起來終止條件顯得比較臃腫，
而對于二叉樹而言，空（null）也可以是一顆二叉樹，所以可以設計為添加元素時當遞回到某個節點的左節點或右節點時或者樹為空時添加元素時，這個節點正好為空（null），此時就可以 new 一個節點將元素添加進去并回傳這個節點給上一層的二分搜索樹的左節點或右節點接識訓者給根節點 root 接收，此時回傳的這個節點就是一棵二分搜索樹同時也是這棵樹的根節點，對于相等的元素則不做處理，最后再回傳遞回最開始的根節點回去給上層節點或者根節點 root 接收即可，
此時在初始呼叫添加操作時，就不需要再判斷二分搜索樹是否為空了，只需使用 root 接收呼叫結果即可，
以上程序用動圖表示如下:

代碼改進后如下:

/**
 * 向二分搜索樹中添加新的元素 element
 * @param element 添加的新元素
 */
public void add(E element) {
    root = add(root, element);
}

/**
 * 向根節點為 node 的二分搜索樹中添加元素 element
 * 遞回函式
 * @param node 添加元素的二分搜索樹的根節點
 * @param element 添加的元素
 * @return 回傳插入新節點后的二分搜索樹的根節點
 */
private Node add(Node node, E element) {
    // 終止條件
    if (node == null) {
        // 遞回到空節點時,new 一個根節點將元素添加到該節點中并回傳該節點給上一層的二分搜索樹的左節點或右節點或者 root 根節點接收
        size++;
        return new Node(element);
    }

    // 不滿足終止條件時,遞回的進行添加元素
    if (element.compareTo(node.element) < 0) {
        // 比當前節點小,添加到左子樹中,并使用當前節點的左節點接收結果
        node.left = add(node.left, element);
    } else if (element.compareTo(node.element) > 0) {
        // 比當前節點大,添加到右子樹中,并使用當前節點的右節點接收結果
        node.right = add(node.right, element);
    }

    // 最后回傳起始時的 node 節點給上層左節點或右節點或者 root 根節點接收
    return node;
}

查詢操作

對于二分搜索樹的查詢操作，這里實作一個 contains 方法用于判斷要查找的元素是否存在于二分搜索樹中，如果存在回傳 true，如果不存在回傳 false，
對于這個操作的實作步驟如下（遞回實作）:
1. 首先判斷當前遞回到的根節點是否為空，如果為空則說明當前遞回到的樹沒有元素，回傳 false，
2. 接著判斷當前遞回到的根節點中的元素是否為要查找的元素，如果是則回傳 true，否則進行后續的判斷，
3. 對于剩下的判斷則是判斷要查找的元素是大于還是小于當前遞回到的根節點，大于就在右子樹中繼續尋找，小于則在左子樹中繼續尋找，接著繼續以上 1、2、3 步的操作，直至出現結果為止，

此操作實作代碼為下:

/**
 * 查看二分搜索樹中是否包含元素 element
 * @param element 查找的元素
 * @return 包含元素 element 回傳 true;反之回傳 false
 */
public boolean contains(E element) {
    // 在整棵樹中查找
    return contains(root, element);
}

/**
 * 查看以 node 為根的二分搜索樹中是否包含元素 element
 * 遞回函式
 * @param node 進行查找的二分搜索樹的根節點
 * @param element 查找的元素
 * @return 包含元素 element 回傳 true;反之回傳 false
 */
private boolean contains(Node node, E element) {
    if (node == null) {
        // 當前查找的二分搜索樹的根節點為空的話,回傳 false
        return false;
    }

    if (element.compareTo(node.element) == 0) {
        // 當前遞回到的根節點的元素為 element,包含,回傳 true
        return true;
    } else if (element.compareTo(node.element) < 0) {
        // 如果 element 比當前根節點的元素小,在左子樹中尋找
        return contains(node.left, element);
    } else {
        // 如果 element 比當前根節點的元素大,在右子樹中尋找
        return contains(node.right, element);
    }
}

遍歷操作

對于遍歷，這個操作是十分常見的，在二分搜索樹中，遍歷操作就是把所有的節點都訪問一遍，在前面的線性結構中，遍歷是及其容易的，使用回圈就行了，不過在樹結構中遍歷也比線性結構難不了多少，也是比較簡單的，在樹結構中有這么幾種遍歷：前序遍歷、中序遍歷、后序遍歷、層序遍歷，下面就一一簡單地實作出二分搜索樹中的這幾種遍歷方式，

前序遍歷

對于二分搜索樹的前序遍歷操作，同樣也是使用遞回來實作，對于前序遍歷，遍歷的順序是先訪問當前節點，接著訪問該節點的左子樹繼而訪問該節點的右子樹，在子樹中也是重復此步驟，當遍歷到一個節點為 null 時直接回傳即可，用圖來表示這個程序就是以下所示:

以上程序實作為代碼形式如下:

/**
 * 二分搜索樹的前序遍歷
 */
public void preOrder() {
    // 從根節點開始遍歷
    preOrder(root);
}

/**
 * 前序遍歷以 node 為根的二分搜索樹
 * 遞回函式
 * @param node 前序遍歷的二分搜索樹的根節點
 */
private void preOrder(Node node) {
    // 終止條件
    if (node == null) {
        // 遍歷到空節點時直接回傳即可
        return;
    }

    // 訪問節點操作（此處簡單的列印一下節點中存盤的元素）
    System.out.println("element: " + node.element);
    // 遍歷當前節點的左子樹
    preOrder(node.left);
    // 遍歷當前節點的右子樹
    preOrder(node.right);
}

實作了代碼之后，做個小測驗驗證一下是否正確，測驗代碼如下:

/**
 * 測驗 BST
 */
public static void main(String[] args) {
    BST<Integer> bst = new BST<>();
    int[] nums = {8, 4, 9, 10, 5, 3};
    for (int num : nums) {
        bst.add(num);
    }
    //形成的二分搜索樹//
    /////////////////
    //      8      //
    //    /   \    //
    //   4     9   //
    //  / \     \  //
    // 3   5    10 //
    /////////////////
    
    // 前序遍歷
    bst.preOrder();
}

測驗結果如下，可以看出結果是符合前序遍歷的規則的，驗證了代碼的正確性:
在實作了前序遍歷之后，可以使用前序遍歷的方式為這個 BST 類重寫一下 toString 方法列印出二分搜索樹以便觀察，

實作代碼如下:

/**
 * 重寫 toString 方法列印二分搜索樹
 */
@Override
public String toString() {
    StringBuilder result = new StringBuilder();
    generateBSTString(root, 0, result);
    return result.toString();
}

/**
 * 生成以 node 為根節點,深度從 depth 開始的二分搜索樹的字串
 * @param node 根節點
 * @param depth 深度
 * @param result 生成的結果
 */
private void generateBSTString(Node node, int depth, StringBuilder result) {
    if (node == null) {
        result.append(generateDepthString(depth) + "null\n");
        return;
    }

    result.append(generateDepthString(depth) + node.element + "\n");
    result.append("left : ");
    generateBSTString(node.left, depth + 1, result);
    result.append("right: ");
    generateBSTString(node.right, depth + 1, result);
}

/**
 * 根據當前深度列印出當前深度對應的 -- 數量
 * @param depth 當前深度
 * @return 回傳當前深度對應數量的 -- 字串
 */
private String generateDepthString(int depth) {
    StringBuilder result = new StringBuilder();
    for (int i = 0; i < depth; i++) {
        result.append("--");
    }
    return result.toString();
}

同樣也對此測驗一下:

/**
 * 測驗 BST
 */
public static void main(String[] args) {
    BST<Integer> bst = new BST<>();
    int[] nums = {8, 4, 9, 10, 5, 3};
    for (int num : nums) {
        bst.add(num);
    }
    //形成的二分搜索樹//
    /////////////////
    //      8      //
    //    /   \    //
    //   4     9   //
    //  / \     \  //
    // 3   5    10 //
    /////////////////

    // 前序遍歷
    bst.preOrder();

    System.out.println("\n==========\n");

    System.out.println(bst);
}

運行效果如下，可以看出同一層的節點都列印了正確的深度，遍歷的順序也滿足了前序遍歷的規則:
至此，就完成了前序遍歷的實作，對于下面的中序遍歷和后序遍歷本質上實作方式和前序遍歷差不了多少，只是節點的訪問順序變化了，

中序遍歷

對于中序遍歷，遍歷的順序是先訪問當前節點的左子樹，接著訪問該節點繼而訪問該節點的右子樹，在子樹中也是重復此步驟，當遍歷到一個節點為 null 時直接回傳即可，用圖來表示這個程序就是以下所示:

以上程序實作為代碼形式如下:

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

/**
 * 中序遍歷以 node 為根的二分搜索樹
 * 遞回函式
 * @param node 中序遍歷的二分搜索樹的根節點
 */
private void inOrder(Node node) {
    // 終止條件
    if (node == null) {
        // 遍歷到空節點時直接回傳即可
        return;
    }

    // 遍歷當前節點的左子樹
    inOrder(node.left);
    // 訪問節點操作（此處簡單的列印一下節點中存盤的元素）
    System.out.println("element: " + node.element);
    // 遍歷當前節點的右子樹
    inOrder(node.right);
}

同樣對此也呼叫該方法測驗一下，運行結果如下，可以看出輸出的順序符合中序遍歷的規則，驗證了代碼的正確性:
從結果中也可以看出中序遍歷的一個特點：輸出的結果是排好序后的，原因在于二分搜索樹的左子樹是小于父親節點，右子樹大于父親節點，而中序遍歷的順序正好是先訪問左子樹，接著訪問父親節點，最后再訪問右子樹，所以輸出的結果是按從小到大的順序輸出的，

后序遍歷

對于后序遍歷，遍歷的順序是先訪問當前節點的左子樹，接著訪問該節點的右子樹繼而訪問該節點，在子樹中也是重復此步驟，當遍歷到一個節點為 null 時直接回傳即可，用圖來表示這個程序就是以下所示:

以上程序實作為代碼形式如下:

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

/**
 * 后序遍歷以 node 為根的二分搜索樹
 * 遞回函式
 * @param node 后序遍歷的二分搜索樹的根節點
 */
private void postOrder(Node node) {
    // 終止條件
    if (node == null) {
        // 遍歷到空節點時直接回傳即可
        return;
    }

    // 遍歷當前節點的左子樹
    postOrder(node.left);
    // 遍歷當前節點的右子樹
    postOrder(node.right);
    // 訪問節點操作（此處簡單的列印一下節點中存盤的元素）
    System.out.println("element: " + node.element);
}

同樣對此也呼叫該方法測驗一下，運行結果如下，可以看出輸出的順序符合中序遍歷的規則，驗證了代碼的正確性:
從結果中也可以看出后序遍歷是按從后往前的順序由子節點開始一一遍歷到父節點的，這種特性也應對了一種應用：為二分搜索樹釋放記憶體，當想要為一個符合二分搜索樹特性的模型釋放記憶體的時候，就可以使用二分搜索樹的后序遍歷來完成，

前、中、后序遍歷的非遞回實作

在實作了前、中、后序遍歷的遞回方式之后，可以使用非遞回方式對這三種遍歷一一再實作一次，加深對二分搜索樹的理解，
在對遞回的學習中，可以知道遞回呼叫函式的時候是會被壓入到系統堆疊中記錄執行順序的，當執行完之后就進行出堆疊回到上一次呼叫函式的地方繼續執行余下操作，
所以對于非遞回的實作，可以借助堆疊這個資料結構，手動模擬系統堆疊的方式實作二分搜索樹的前、中、后序遍歷，接下來一一實作這三種遍歷的非遞回方式，

前序遍歷的非遞回實作

對于使用堆疊來幫助模擬系統堆疊來實作前序遍歷的程序，用動圖來表示如下所示：
對于以上程序，由于堆疊的后進先出的特性，加上前序遍歷的規則，所以在遍歷完一個節點將其出堆疊后是先將該節點的右節點先入堆疊再入堆疊左節點，這樣子后續出堆疊遍歷節點后就滿足了前序遍歷的規則，

以上程序代碼實作如下:

/**
 * 二分搜索樹的非遞回方式的前序遍歷
 */
public void preOrderNotRecursive() {
	// 如果樹為空,則不遍歷,沒有元素可遍歷
    if (root == null) {
        return;
    }
    
    // 借助一個堆疊來模擬系統堆疊實作前序遍歷
    Stack<Node> stack = new Stack<>();
    // 從根節點開始遍歷
    stack.push(root);
    // 當堆疊非空時,回圈往復以下程序對二分搜索樹進行前序遍歷
    while (!stack.isEmpty()) {
        // 當前遍歷的節點
        Node currentNode = stack.pop();
        System.out.println("element: " + currentNode.element);
        
        // 如果當前遍歷的節點的左右節點不為空,按右節點、左節點的順序入堆疊
        if (currentNode.right != null) {
            stack.push(currentNode.right);
        }
        if (currentNode.left != null) {
            stack.push(currentNode.left);
        }
    }
}

實作之后，呼叫之前的遞回方式和這個非遞回方式比對兩者的結果是否一致:
從結果可看出，非遞回方式的實作是正確的，對比遞回實作的步驟，非遞回的實作相對來說還是比較復雜的，不過通過這樣的實作也能加強對于二分搜索樹前序遍歷的理解，還是相當有好處的，接著繼續實作中序遍歷和后序遍歷的非遞回方式的實作，

中序遍歷的非遞回實作

對于中序遍歷的非遞回實作，同樣也是使用一個堆疊來模擬系統堆疊的遞回程序來實作，首先在這里先使用一個內部類用于封裝當前的指令（繼續模擬遞回、列印節點）和當前模擬遞回到的節點，以便模擬堆疊遞回實作中序遍歷，

對于這個內部類的具體實作如下所示，其中 s 代表指令，如果 s 為 go 則表示繼續模擬遞回，如果 s 為 print 則表示列印當前節點資訊，

/**
 * 用于封裝模擬系統堆疊時的指令和遞回到的節點資訊
 */
private class Command {
    // s: 指令
    // go: 表示繼續模擬遞回
    // print: 表示列印當前節點資訊
    private String s;
    // 當前模擬遞回到的節點
    private Node node;
    public Command(String s, Node node){
        this.s = s;
        this.node = node;
    }
}

當封裝了這么一個內部類之后，非遞回方式的中序遍歷就比較好實作了，具體程序為:
- 初始時將根節點和指令 go 入堆疊，表示從根節點開始繼續模擬遞回下去，
- 接著開始回圈，只要堆疊不為空，就重復回圈中的內容:
  - 首先先從堆疊頂取出當前堆疊頂資訊，
  - 接著判斷堆疊頂資訊中的指令是否為 print，如果為 print 列印節點資訊，否則做下面的操作，
  - 如果指令為 go，則將當前節點的右子樹和指令 go 先入堆疊，（和前面的非遞回前序遍歷一樣，由于堆疊的后入先出特性，需要反過來入堆疊，后面出堆疊時才能符合中序遍歷）
  - 接著將當前節點和指令 print 入堆疊，當后面這個節點出堆疊時就可以判斷到 print 指令列印這個節點，
  - 最后再將當前節點的左子樹和指令 go 入堆疊，這樣子后面最先出堆疊的就是左節點再到左節點的父節點再到右節點，滿足中序遍歷的規則，
- 這樣子，重復以上程序，就可以模擬系統堆疊的遞回實作出二分搜索樹的中序遍歷了，以上程序的圖示演示如下:

具體代碼實作如下:

/**
 * 二分搜索樹的非遞回方式的中序遍歷
 */
public void inOrderNotRecursive() {
    // 如果樹為空,則不遍歷,沒有元素可遍歷
    if (root == null) {
        return;
    }

    // 借助一個堆疊來模擬系統堆疊實作中序遍歷
    Stack<Command> stack = new Stack<>();
    // 初始時將根節點和指令 go 入堆疊
    stack.push(new Command("go", root));
    // 當堆疊非空時,回圈往復以下程序對二分搜索樹進行中序遍歷
    while (!stack.isEmpty()) {
        // 將堆疊頂資訊出堆疊,判斷其中的指令做相應操作
        Command command = stack.pop();

        if ("print".equals(command.s)) {
            System.out.println("element: " + command.node.element);
        } else {
            if (command.node.right != null) {
                stack.push(new Command("go", command.node.right));
            }
            
            stack.push(new Command("print", command.node));
            
            if (command.node.left != null) {
                stack.push(new Command("go", command.node.left));
            }
        }
    }
}

同樣地，也對此進行測驗，驗證是否撰寫正確，運行結果如下:
從測驗結果可以看出，遍歷的結果是符合預期的，和之前實作的遞回方式的結果是一致的，驗證了代碼的正確性，在實作完了非遞回方式的中序遍歷后，對于后序遍歷也就手到擒來了，原理也是相似的，接下來就實作后序遍歷的非遞回方式，

后序遍歷的非遞回實作

對于后序遍歷的非遞回方式的實作，同樣也是使用 Command 來封裝入堆疊的資訊，其中的具體實作程序如下:
- 初始時將根節點和指令 go 入堆疊，表示從根節點開始繼續模擬遞回下去，
- 接著開始回圈，只要堆疊不為空，就重復回圈中的內容:
  - 首先先從堆疊頂取出當前堆疊頂資訊，
  - 接著判斷堆疊頂資訊中的指令是否為 print，如果為 print 列印節點資訊，否則做下面的操作，
  - 如果指令為 go，則將當前節點和指令 print 先入堆疊，當后面這個節點出堆疊時就可以判斷到 print 指令列印這個節點，（和前面的非遞回前序遍歷一樣，由于堆疊的后入先出特性，需要反過來入堆疊，后面出堆疊時才能符合后序遍歷）
  - 接著將當前節點的右子樹和指令 go 入堆疊，
  - 最后再將當前節點的左子樹和指令 go 入堆疊，這樣子后面最先出堆疊的就是左節點再到右節點再到左右節點的父節點，滿足后序遍歷的規則，
- 這樣子，重復以上程序，就可以模擬系統堆疊的遞回實作出二分搜索樹的后序遍歷了，以上程序的圖示演示如下:

具體代碼實作如下:

/**
 * 二分搜索樹的非遞回方式的后序遍歷
 */
public void postOrderNotRecursive() {
    // 如果樹為空,則不遍歷,沒有元素可遍歷
    if (root == null) {
        return;
    }

    // 借助一個堆疊來模擬系統堆疊實作后序遍歷
    Stack<Command> stack = new Stack<>();
    // 初始時將根節點和指令 go 入堆疊
    stack.push(new Command("go", root));
    // 當堆疊非空時,回圈往復以下程序對二分搜索樹進行后序遍歷
    while (!stack.isEmpty()) {
        // 將堆疊頂資訊出堆疊,判斷其中的指令做相應操作
        Command command = stack.pop();

        if ("print".equals(command.s)) {
            System.out.println("element: " + command.node.element);
        } else {
            stack.push(new Command("print", command.node));

            if (command.node.right != null) {
                stack.push(new Command("go", command.node.right));
            }

            if (command.node.left != null) {
                stack.push(new Command("go", command.node.left));
            }
        }
    }
}

同樣地，也對此進行測驗，驗證是否撰寫正確，運行結果如下:
從測驗結果可以看出，遍歷的結果是符合預期的，和之前實作的遞回方式的結果是一致的，驗證了代碼的正確性，至此，就將前、中、后序遍歷的非遞回方式都實作了一遍了，使用的是模擬系統堆疊的方式，如此也加深了對這三種遍歷的理解以及對遞回的理解，接下來就實作二分搜索樹中的最后一種遍歷層序遍歷，

層序遍歷

在前面的前、中、后序三種遍歷方式的實作程序中，可以發現這三種遍歷方式總是會先到最下層的節點處再往上回傳，這種方式也就是深度優先遍歷，
而對于層序遍歷而言，它是按一層一層從左往右的順序來遍歷的，這種方式也就是廣度優先遍歷，
對于這種遍歷方式，通常使用的實作方式是非遞回方式的實作，同時可以借助佇列這個資料結構來實作，
對于實作程序，當一個節點入隊并出隊時，這個節點就被遍歷到了，同時在該節點出隊時，由于佇列的先入先出特性以及層序遍歷的規則，此時將該節點的左右節點按左節點、右節點的順序入隊，此時再當隊首的節點出隊時，又再將出隊節點的左右節點按左節點、右節點的順序入隊，以此類推回圈往復，就完成了二分搜索樹的層序遍歷操作，這個程序用圖來表示如下所示:

以上程序代碼實作如下:

/**
 * 二分搜索樹的層序遍歷
 */
public void levelOrder() {
    // 借助一個佇列來實作層序遍歷
    Queue<Node> queue = new LinkedList<>();
    // 從根節點開始遍歷
    queue.add(root);
    // 當佇列非空時,回圈往復以下程序對二分搜索樹進行層序遍歷
    while (!queue.isEmpty()) {
        // 當前遍歷的節點
        Node currentNode = queue.remove();
        System.out.println(currentNode.element);

        // 如果當前遍歷的節點的左右節點不為空,按左節點、右節點的順序入隊
        if (currentNode.left != null) {
            queue.add(currentNode.left);
        }
        if (currentNode.right != null) {
            queue.add(currentNode.right);
        }
    }
}

此時呼叫該方法驗證是否正確:
從結果可看出，遍歷的順序符合了預期，驗證了代碼的正確性，至此，二分搜索樹的幾種遍歷方式也就都實作了，接下來實作最后的洗掉操作，

洗掉操作

洗掉最大元素和最小元素

對于洗掉操作，首先先從洗掉二分搜索樹的最大值和最小值開始，因為根據二分搜索樹的特性，最左邊的節點就是整棵樹的最小值，最右邊的節點就是整棵樹的最大值，所以相對來說這兩個操作比較容易實作，同時先實作了這兩個操作后，對于后續的洗掉任意元素也有輔助的作用，以下是最大值和最小值的幾個示例圖:

在實作洗掉的操作之前，先實作兩個函式用于找到二分搜索樹的最小元素和最大元素以備洗掉時使用，具體實作如下:

/**
 * 找到二分搜索樹的最小元素
 * @return 回傳當前二分搜索樹的最小元素
 */
public E minimum() {
    // 判斷當前二分搜索樹是否為空樹
    if (size == 0) {
        throw new IllegalArgumentException("Minimum failed. Current BST is empty!");
    }
    
    return minimum(root).element;
}

/**
 * 回傳以 node 為根的二分搜索樹的最小值所在的節點
 * @param node 尋找最小值的二分搜索樹的根節點
 * @return 回傳當前二分搜索樹的最小元素
 */
private Node minimum(Node node) {
    // 當一個節點的左節點為空時,該節點就是樹中的最左節點了
    if (node.left == null) {
        return node;
    }
    
    // 否則繼續往左子樹中尋找
    return minimum(node.left);
}

/**
 * 找到二分搜索樹的最大元素
 * @return 回傳當前二分搜索樹的最大元素
 */
public E maximum() {
    // 判斷當前二分搜索樹是否為空樹
    if (size == 0) {
        throw new IllegalArgumentException("Maximum failed. Current BST is empty!");
    }

    return maximum(root).element;
}

/**
 * 回傳以 node 為根的二分搜索樹的最大值所在的節點
 * @param node 尋找最大值的二分搜索樹的根節點
 * @return 回傳當前二分搜索樹的最大元素
 */
private Node maximum(Node node) {
    // 當一個節點的右節點為空時,該節點就是樹中的最右節點了
    if (node.right == null) {
        return node;
    }

    // 否則繼續往右子樹中尋找
    return maximum(node.right);
}

在實作完以上函式之后，就可以進行洗掉的操作了，
首先先進行最小值的洗掉，對于最小值的洗掉，有兩種情況：洗掉的節點是葉子節點、洗掉的節點有右子樹，
對于葉子節點，直接洗掉即可，而對于有右子樹的節點，洗掉的邏輯也很簡單，即將當前的節點和樹脫離，再將這個節點的右子樹接到它原來的位置即可，而對于葉子節點，它的左右節點都是 null 的，所以對于葉子節點也可以使用這個邏輯來洗掉，只不過接到節點原來位置的是 null 而已，
以上程序的圖示如下:

代碼實作如下:

/**
 * 洗掉二分搜索樹中最小值所在的節點并且回傳洗掉的最小值
 * @return 回傳洗掉的節點中的元素
 */
public E removeMin() {
    // 先接收當前二分搜索樹中的最小值,以備洗掉后回傳
    E delElement = minimum();
    // 洗掉操作
    root = removeMin(root);
    // 回傳洗掉的最小值
    return delElement;
}

/**
 * 洗掉以 node 為根的二分搜索樹的最小節點
 * @param node 洗掉最小節點的二分搜索樹的根節點
 * @return 回傳洗掉節點后新的二分搜索樹的根,即洗掉的節點的右子樹的根節點
 */
private Node removeMin(Node node) {
    // 當遞回到一個節點的左節點為空時,此節點為最小節點,進行洗掉操作
    if (node.left == null) {
        // 先將洗掉的節點 node 的右子樹記錄下來
        Node rightNode = node.right;
        // 將 node 和它的右子樹脫離
        node.right = null;
        size--;
        // 回傳 node 的右子樹給上層節點接收,此時 node 和上層節點也脫離了
        return rightNode;
    }
    
    // 左節點不為空時,繼續往左子樹遞回,使用當前根節點的左節點接收
    node.left = removeMin(node.left);
    // 最后回傳當前根節點,完成洗掉
    return node;
}

在處理完了最小元素的洗掉之后，對于最大的元素洗掉就容易許多了，洗掉的邏輯總體上還是一樣的，也就是把洗掉節點的左子樹接到節點原來的位置即可，洗掉程序圖示如下:

代碼實作如下:

/**
 * 洗掉二分搜索樹中最大值所在的節點并且回傳洗掉的最大值
 * @return 回傳洗掉的節點中的元素
 */
public E removeMax() {
    // 先接收當前二分搜索樹中的最大值,以備洗掉后回傳
    E delElement = maximum();
    // 洗掉操作
    root = removeMax(root);
    // 回傳洗掉的最小值
    return delElement;
}

/**
 * 洗掉以 node 為根的二分搜索樹的最大節點
 * @param node 洗掉最大節點的二分搜索樹的根節點
 * @return 回傳洗掉節點后新的二分搜索樹的根,即洗掉的節點的左子樹的根節點
 */
private Node removeMax(Node node) {
    // 當遞回到一個節點的右節點為空時,此節點為最大節點,進行洗掉操作
    if (node.right == null) {
        // 先將洗掉的節點 node 的左子樹記錄下來
        Node leftNode = node.left;
        // 將 node 和它的左子樹脫離
        node.left = null;
        size--;
        // 回傳 node 的左子樹給上層節點接收,此時 node 和上層節點也脫離了
        return leftNode;
    }

    // 右節點不為空時,繼續往右子樹遞回,使用當前根節點的右節點接收
    node.right = removeMax(node.right);
    // 最后回傳當前根節點,完成洗掉
    return node;
}

在實作了以上兩個操作之后，對它們進行一下測驗，
測驗的邏輯為：隨機生成 1000 個 [0, 10000) 的數添加到二分搜索樹中，然后分別使用這兩個操作將洗掉的元素添加到一個 ArrayList 中，再對這個 ArrayList 進行校驗，看看里面的元素是不是按從小到大的順序或從大到小的順序排列，校驗成功的話說明以上的操作實作的代碼是正確的，

測驗代碼如下所示:

private static void testRemoveMin() {
    // 測驗洗掉最小節點
    BST<Integer> bst = new BST<>();
    Random random = new Random();

    int n = 1000;
    for (int i = 0; i < n; i++) {
        bst.add(random.nextInt(10000));
    }

    ArrayList<Integer> nums = new ArrayList<>();
    while (!bst.isEmpty()) {
        nums.add(bst.removeMin());
    }

    // 校驗 nums 是否按從小到大的順序排列
    for (int i = 1; i < nums.size(); i++) {
        if (nums.get(i - 1) > nums.get(i)) {
            // 如果有一個數比后面的大,則說明洗掉最小節點的操作的實作是錯誤的
            throw new IllegalArgumentException("removeMin error!");
        }
    }
    // 運行到此處校驗通過
    System.out.println("removeMin test completed.");
}

private static void testRemoveMax() {
    // 測驗洗掉最大節點
    BST<Integer> bst = new BST<>();
    Random random = new Random();

    int n = 1000;
    for (int i = 0; i < n; i++) {
        bst.add(random.nextInt(10000));
    }

    ArrayList<Integer> nums = new ArrayList<>();
    while (!bst.isEmpty()) {
        nums.add(bst.removeMax());
    }

    // 校驗 nums 是否按從大到小的順序排列
    for (int i = 1; i < nums.size(); i++) {
        if (nums.get(i - 1) < nums.get(i)) {
            // 如果有一個數比后面的小,則說明洗掉最大節點的操作的實作是錯誤的
            throw new IllegalArgumentException("removeMax error!");
        }
    }
    // 運行到此處校驗通過
    System.out.println("removeMax test completed.");
}

運行結果
從運行結果中，可以看出以上實作的兩個洗掉操作都是正確的，接下來就可以實作任意元素的洗掉了，

洗掉任意元素

對于洗掉二分搜索樹中的任意元素，同樣也分為幾種情況：洗掉只有左孩子的節點、洗掉只有右孩子的節點、洗掉左右都有孩子的節點，
對于前面兩種情況：洗掉只有左孩子的節點、洗掉只有右孩子的節點，具體步驟其實和前面的洗掉最大節點和洗掉最小節點差不多，也是將洗掉的節點的左子樹或者右子樹掛接在這個節點原來的位置，將原來的節點從二分搜索樹中脫離出去，所以對于這兩種情況的洗掉，實作起來和前面的基本相同，
而對于洗掉左右都有孩子的節點這種情況，就不能使用前面的法子了，這個時候可以使用 Hibbard 提出的 Hibbard Deketion 原理進行洗掉，
具體步驟是這樣的：
- 先將要洗掉的節點記錄為 d，然后從 d 的右子樹中找到子樹中最小的節點用 s 記錄下來，這個 s 也就是 d 的后繼節點，
- 然后將 d 的右子樹中洗掉掉最小的節點，也就是 s，并將洗掉 s 后的這個右子樹的根賦值給 s 的右節點，也就是 s 從右子樹中最小的位置移到了根的位置，
- 接著再將 d 的左子樹賦值給 s 的左子樹，
- 最后將 d 從二分搜索樹中脫離出來，將 s 接到 d 的位置，此時，d 就從樹中洗掉掉了，
以上步驟簡單來說就是 d 的右子樹的節點都是大于 d 的，而其中的最小節點就是排在它后面的節點，此時如果將這個 s 放到 d 的位置，這個 s 節點的左子樹依然滿足都小于它的特性、同樣右子樹也滿足都大于它的特性，此時就可以達到洗掉 d 的效果了，
同理，也可以在 d 的左子樹中找它的前驅，也就是左子樹中最大的節點，用 p 記錄下來，再將這個 p 按照以上操作 s 的原理將 p 放置到 d 的位置，也可以達成洗掉 d 的效果，這里就不實作這個找前驅的操作了，實作找后繼 s 的操作來洗掉 d，
對于以上洗掉的步驟，表示為圖為以下所示:
- 洗掉只有左孩子的節點示例:
- 洗掉只有右孩子的節點示例:
- 洗掉左右孩子均有的節點示例:

代碼實作如下:

/**
 * 從二分搜索樹中洗掉元素為 element 的節點
 * @param element 要從二分搜索樹中洗掉的元素
 */
public void remove(E element) {
    root = remove(root, element);
}

/**
 * 洗掉以 node 為根的二分搜索樹中值為 element 的節點
 * 遞回函式
 * @param node 要洗掉元素的二分搜索樹的根節點
 * @param element 要洗掉的元素
 * @return 回傳洗掉節點后新的二分搜索樹的根
 */
private Node remove(Node node, E element) {
    if (node == null) {
        // 如果根節點為空,沒有要洗掉的元素,回傳 null 即可
        return null;
    }

    if (element.compareTo(node.element) < 0) {
        // 如果要洗掉的元素比當前根節點的元素小,在左子樹中繼續尋找 element 進行洗掉,并使用當前根節點的左節點接收結果
        node.left = remove(node.left, element);
        // 洗掉后回傳當前根節點給上層節點接收
        return node;
    } else if (element.compareTo(node.element) > 0) {
        // 如果要洗掉的元素比當前根節點的元素大,在右子樹中繼續尋找 element 進行洗掉,并使用當前根節點的右節點接收結果
        node.right = remove(node.right, element);
        // 洗掉后回傳當前根節點給上層節點接收
        return node;
    } else {
        // 當前根節點的元素為 element,進行洗掉,三種情況
        // 當前洗掉節點只有右子樹
        if (node.left == null) {
            Node rightNode = node.right;
            node.right = null;
            size--;
            return rightNode;
        }

        // 當前洗掉節點只有左子樹
        if (node.right == null) {
            Node leftNode = node.left;
            node.left = null;
            size--;
            return leftNode;
        }

        // 當前洗掉節點左右子樹均不為空
        // 找到當前洗掉節點大的最小節點,即洗掉節點右子樹的最小節點
        // 用這個最小節點代替洗掉節點的位置
        Node successor = minimum(node.right);
        // 將右子樹的最小節點移動到右子樹的根位置
        successor.right = removeMin(node.right);
        // 將最小節點的左子樹賦為洗掉節點的左子樹
        successor.left = node.left;
        // 將洗掉節點和二分搜索樹脫離
        node.left = node.right = null;
        // 回傳 successor 給上層節點接收,頂替 node 的位置,將 node 洗掉掉
        return successor;
    }
}

實作完之后，也對此測驗一下，以驗證代碼的正確性，測驗代碼如下:

/**
 * 測驗 BST
 */
public static void main(String[] args) {
    BST<Integer> bst = new BST<>();
    int[] nums = {8, 4, 9, 10, 5, 3};
    for (int num : nums) {
        bst.add(num);
    }

    System.out.println("洗掉前: ");
    System.out.println(bst);

    //形成的二分搜索樹//
    /////////////////
    //      8      //
    //    /   \    //
    //   4     9   //
    //  / \     \  //
    // 3   5    10 //
    /////////////////

    // 洗掉 4 所在的節點
    bst.remove(4);

    //洗掉后的二分搜索樹//
    //////////////////
    //      8      ///
    //    /   \    ///
    //   5     9   ///
    //  /       \  ///
    // 3        10 ///
    //////////////////

    System.out.println("洗掉后: ");
    System.out.println(bst);

    // 層序遍歷
    // bst.levelOrder();

    // 前序遍歷
    // bst.preOrder();
    // System.out.println("\n==========\n");
    // 非遞回前序遍歷
    // bst.preOrederNotRecursive();

    // 中序遍歷
    // bst.inOrder();
    // System.out.println("\n==========\n");
    // 后序遍歷
    // bst.postOrder();
    // System.out.println(bst);


    // 校驗洗掉最小節點操作是否成功
    // testRemoveMin();

    // 校驗洗掉最大節點操作是否成功
    // testRemoveMax();
}

運行結果
從運行結果，可以看出是符合預期的，驗證了代碼撰寫正確，至此，二分搜索樹的這幾種操作就都實作完成了，
如有寫的不足的，還請見諒，也請大家多多指教，(*^▽^*)

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/67635.html

標籤：其他

上一篇：flume spooldir hdfs sink性能

下一篇：劍指Offer(第二版)面試題目分析與實作合集

詳細分析二分搜索樹的資料結構的實作程序（Java 實作）

樹結構簡介

二分搜索樹的基礎知識

二叉樹的基本概念

二分搜索樹的基本概念

二分搜索樹的基本結構代碼實作

二分搜索樹的常見基本操作實作

添加操作

添加操作初步實作

添加操作改進

查詢操作

遍歷操作

前序遍歷

中序遍歷

后序遍歷

前、中、后序遍歷的非遞回實作

前序遍歷的非遞回實作

中序遍歷的非遞回實作

后序遍歷的非遞回實作

層序遍歷

洗掉操作

洗掉最大元素和最小元素

洗掉任意元素