二分搜尋樹-代碼實作

目錄

一、樹

1、二叉樹

2、二分搜尋樹Binary Search Tree

二、二分搜尋樹的代碼實作

1、向二分搜尋樹中添加元素

2、二分搜尋樹的查詢

3、二分搜尋樹的周遊

（1）前序周遊

（1）中序周遊（排序樹）

（3）後續周遊

4、二分搜尋樹前序周遊非遞歸寫法

5、二分搜尋樹的層序周遊

6、二分搜尋樹的删除操作

（1）删除二分搜尋樹的最大最小值

（2）删除二分搜尋樹的任意值

一、樹

樹結構，跟之前的數組和連結清單不同，它是一種非線性結構的資料結構。使用樹結構可以很大程度上的提高我們的搜尋效率，生活場景中有很多運用樹結構的例子。比如檔案搜尋，如果我們需要找照片相關的資料，就會直接去照片檔案下查找，而不會去選擇其他的檔案夾。這樣做避免搜尋了很多不必要的檔案，進而大大提高了搜尋的效率。

1、二叉樹

二叉樹和連結清單一樣，是一種動态的資料結構，即不要一開始就指定資料結構的大小。如果需要存儲新的元素，直接new 一個新的節點存儲就可以了。如下，是一顆二叉樹的圖示：

二叉樹的節點代碼示例：

// 具備左右節點的結構
private class Node{
        E e;
        Node left;
        Node right;
    }
           

當然，除了二叉樹，還有多叉樹，隻是多叉樹維護的節點更多罷了。下邊看一下二叉樹的相關圖解和定義：

葉子節點，是指沒有左孩子或右孩子的節點；根節點，此節點是唯一沒有父節點的節點。

二叉樹的變形有很多，一個節點可以沒有左孩子或者右孩子，或者整棵二叉樹的節點都隻有左孩子或者右孩子（這種情況下的結構跟連結清單非常相似，但也是一種二叉樹），更極端的情況是，隻有一個點，或者直接是null（二叉樹為空），都可以看成是一棵二叉樹。

2、二分搜尋樹Binary Search Tree

二分搜尋樹定義圖解：

二分搜尋樹可以非常大的提高我們查找資料的速度。比如我們需要查找42這個資料，就可以直接去根節點28的右子樹查找，這是因為根據二分搜尋樹的定義，根節點的左子樹此時的資料都是小于28的。

正因為二分搜尋樹的這個特點，是以，要求使用二分搜尋樹進行存儲的資料都必須具備可比較性。

二、二分搜尋樹的代碼實作

介紹了二分搜素樹的相關定義，下邊我們通過代碼來實作一個二分搜尋樹，初始化二分樹的代碼結構如下：

// 這裡限制泛型E,是可以用來比較的元素
public class BST<E extends Comparable<E>> {
    private class Node {
        public E e;
        public Node left, right;
        public Node(E e) {
            this.e = e;
            left = null;
            right = null;
        }
    }

    // 根節點
    private Node root;
    // 二叉樹中存儲的資料多少
    private int size;

    // 初始化二分搜尋樹
    public BST() {
        root = null;
        size = 0;
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }
}
           

1、向二分搜尋樹中添加元素

向二分搜尋樹中添加元素，此處我們實作的二分搜尋樹不包含重複元素。如果想要包含重複元素，我們需要修改下定義：左子樹小于等于節點或者右子樹大于等于節點。

下邊是向二分搜尋樹中添加元素的代碼實作：

// 向二分搜尋樹中添加新元素
    public void add(E e) {
        if (root == null) {
            root = new Node(e);
            size++;
        } else {
            add(root, e);
        }
    }

    // 向以node為根的二分搜尋樹中插入元素E,遞歸實作
    private void add(Node node, E e) {
        if (node.e.equals(e)) {
            return;
        } else if (node.e.compareTo(e) > 0 && node.left == null) {
            node.left = new Node(e);
            size++;
            return;
        } else if (node.e.compareTo(e) < 0 && node.right == null) {
            node.right = new Node(e);
            size++;
            return;
        } else if (node.e.compareTo(e) > 0) {
            add(node.left, e);
        } else {
            add(node.right, e);
        }
    }
           

不過反觀上邊的實作代碼，雖然程式的邏輯比較容易了解，但是，在遞歸算法的運用上卻沒有做得更優雅。因為，程式中還另外判斷了一下根節點不為空的情況，在遞歸方法中也做了多次的比較。接下來，看一下更優雅的實作。

// 向二分搜尋樹中添加新元素
    public void add(E e) {
        root = add(root, e);
    }

    // 向以node為根的二分搜尋樹中插入元素E,遞歸實作
    // 傳回插入節點後的二分搜尋樹的跟
    private Node add(Node node, E e) {
        if (node == null) {
            size++;
            return new Node(e);
        }
        if (node.e.compareTo(e) > 0) {
            node.left = add(node.left, e);
        } else if (node.e.compareTo(e) < 0) {
            node.right = add(node.right, e);
        }
        return node;
    }
           

2、二分搜尋樹的查詢

判斷一個二分搜尋樹中是否包含某一進制素，代碼實作如下：

// 檢視二分搜尋樹中是否包含元素e
    public boolean contains(E e) {
        return contains(root, e);
    }

    // 看以node為根的二分搜尋樹中是否包含元素e,遞歸算法
    private boolean contains(Node node, E e) {
        if (node == null) {
            return false;
        }
        if (e.equals(node.e)) {
            return true;
        } else if (e.compareTo(node.e) > 0) {
            return contains(node.right, e);
        } else {
            return contains(node.left, e);
        }
    }
           

3、二分搜尋樹的周遊

（1）前序周遊

所謂周遊，就是通路整顆二叉樹的所有元素。

前序周遊，就是從樹的根節點處開始通路，把根節點的通路順序放在開頭（前序周遊）；然後依次通路根節點的左子樹和右子樹。首先我們來看看前序周遊的代碼

// 二分搜尋樹的前序周遊
    public void preOrder() {
        preOrder(root);
    }

    // 前序周遊從根節點處進行周遊
    public void preOrder(Node node) {
        // 遞歸終止條件
        if (node == null) {
            return;
        }
        System.out.println(node.e);
        preOrder(node.left);
        preOrder(node.right);
    }
           

對于周遊程式，我們接下來做個小小的測試：

public static void main(String[] args) {
        BST<Integer> bst = new BST<Integer>();
        int[] nums = {5, 3, 6, 8, 4, 2};
        for (int num : nums) {
            bst.add(num);
        }
        bst.preOrder();
    }
           

此測試程式，元素添加到二分搜尋樹中，它的結構應該是這樣的

來看一下列印輸出的元素的順序：

最後，補充下前序周遊的toString()方法的代碼實作

@Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        generateBSTString(root, 0, sb);
        return sb.toString();
    }

    private void generateBSTString(Node node, int depth, StringBuilder sb) {
        if (node == null) {
            sb.append(generateDepthString(depth) + "null\n");
            return;
        }
        sb.append(generateDepthString(depth) + node.e + "\n");
        generateBSTString(node.left, depth + 1, sb);
        generateBSTString(node.right, depth + 1, sb);
    }

    // 周遊深度
    private String generateDepthString(int depth) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < depth; i++) {
            sb.append("--");
        }
        return sb.toString();
    }
           

（1）中序周遊（排序樹）

所謂的中序周遊，就是把根節點的通路放在中間位置進行通路。下邊來看一實作代碼

// 二分搜尋樹的中序周遊
    public void inOrder() {
        inOrder(root);
    }

    public void inOrder(Node node) {
        if (node == null) {
            return;
        }
        // 先通路左子樹
        inOrder(node.left);
        System.out.println(node.e);
        // 最後通路右子樹
        inOrder(node.right);
    }
           

根據上邊代碼，我們可以簡單的編寫一下測試程式進行調用

public static void main(String[] args) {
        BST<Integer> bst = new BST<Integer>();
        int[] nums = {5, 3, 6, 8, 4, 2};
        for (int num : nums) {
            bst.add(num);
        }
         bst.inOrder();
    }
           

執行結果輸出如下：

我們發現：二分搜尋樹的中序周遊的結果是順序的。

（3）後續周遊

所謂後續周遊，就是把根節點的通路順序放在最後，這種風格就是把所有的孩子節點周遊完以後再去通路根節點。下邊來看一下代碼的具體實作，非常簡單

// 後序周遊
    public void postOrder() {
        postOrder(root);
    }

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

簡單的編寫一個測試程式

public static void main(String[] args) {
        BST<Integer> bst = new BST<Integer>();
        int[] nums = {5, 3, 6, 8, 4, 2};
        for (int num : nums) {
            bst.add(num);
        }
         bst.postOrder();
    }
           

執行結果如下：

使用二分搜尋樹後序周遊的場景：手動釋放記憶體。按照從孩子節點到根節點的順序進行釋放。

4、二分搜尋樹前序周遊非遞歸寫法

前序周遊也叫深度優先周遊，有點像模拟系統棧的調用。這種不停把元素壓入棧和取出棧的操作可以通過debug方法來跟蹤其中的邏輯，具體代碼實作如下：

// 二分搜尋樹前序周遊非遞歸實作
    public void preOrderNR(){
        Stack<Node> stack = new Stack<Node>();
        // 根元素壓入棧
        stack.push(root);
        while(!stack.isEmpty()){
            // 取出棧元素
            Node cur = stack.pop();
            System.out.println(cur.e);
            if(cur.right != null){
                stack.push(cur.right);
            }
            // 後進先出
            if(cur.left != null){
                stack.push(cur.left);
            }
        }
    }
           

5、二分搜尋樹的層序周遊

二分搜尋樹的層序周遊，也叫廣度優先周遊，是按照二分搜尋樹的層次結構，一層一層從左到右的來訪元素。

層序優先周遊的代碼實作:

// 二分搜尋樹的層序周遊
    public void levelOrder() {
        Queue<Node> q = new LinkedList<Node>();
        q.add(root);
        while (!q.isEmpty()) {
            Node cur = q.remove();
            System.out.println(cur.e);
            if (cur.left != null) {
                q.add(cur.left);
            }
            if (cur.right != null) {
                q.add(cur.right);
            }
        }
    }
           

廣度優先周遊的意義

6、二分搜尋樹的删除操作

（1）删除二分搜尋樹的最大最小值

要删除二分搜尋樹中的最大最小值，首先需要找到二分搜尋樹的最大最小值。在二分搜尋樹中，最小值是左子樹中最左的元素，想反最大值，就是右子樹中最右的元素。接下來看一下具體代碼的實作：

// 尋找二分搜尋樹中的最小元素
    public E minimum(){
        if(size == 0){
            throw new IllegalArgumentException("BST is empty.");
        }
        return minimum(root).e;
    }

    private Node minimum(Node node){
        if(node.left == null){
            return node;
        }
        return minimum(node.left);
    }

    // 尋找二分搜尋樹中的最大元素
    public E maximum(){
        if(size == 0){
            throw new IllegalArgumentException("BST is empty.");
        }
        return  maximum(root).e;
    }

    private Node maximum(Node node){
        if(node.right == null){
            return node;
        }
        return maximum(node.right);
    }

    // 删除最小元素
    public E removeMin() {
        E ret = minimum();
        root = removeMin(root);
        return ret;
    }

    private Node removeMin(Node node) {
        // 遞歸到底的邏輯
        if (node.left == null) {
            // 保留右子樹
            Node rightNode = node.right;
            // 删除最小值，此時的右子樹成為新的節點
            node.right = null;
            size--;
            return rightNode;
        }
        node.left = removeMin(node.left);
        return node;
    }

    // 删除最大元素
    public E removeMax() {
        E ret = maximum();
        root = removeMax(root);
        return ret;
    }

    private Node removeMax(Node node) {
        // 遞歸到底的邏輯
        if (node.right == null) {
            // 保留左子樹
            Node leftNode = node.left;
            // 除了左子樹以外，其他都不要，也就是把元素删除了
            node.left = null;
            size--;
            return leftNode;
        }
        node.right = removeMax(node.right);
        return node;
    }
           

（2）删除二分搜尋樹的任意值

删除任意元素的難點在于，左右都有孩子節點的節點。比如這個時候要删除58這個節點，就不僅僅是把左孩子或者右孩子替換掉原來的節點那麼簡單了，需要有更複雜的邏輯。

如上圖，當我們删除58的節點後，這個時候用哪個節點來彌補58這個節點的位置呢？答案是，我們選擇58節點右子樹中最小的那個節點59，用它來做58的後繼。圖示如下

具體的代碼實作如下：

// 删除任意元素
    public void remove(E e) {
        // 傳回删除元素後的二叉樹
        root = remove(root, e);
    }

    private Node remove(Node node, E e) {
        // 二分搜尋樹為空
        if (node == null) {
            return null;
        }
        if (e.compareTo(node.e) > 0) {
            // 大于根節點，從右子樹删除
            node.right = remove(node.right, e);
            return node;
        } else if (e.compareTo(node.e) < 0) {
            // 小于根節點，從左子樹删除
            node.left = remove(node.left, e);
            return node;
        } else { // 等于根節點
            // 如果左子樹為空，直接用右子樹來替換
            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;
            return successor;
        }
    }
           

注：在待删除的節點左右孩子都存在的情況下，删除後繼節點的時候，我們其實并沒有真正的删除此節點，而是把它維護了起來。但是我們維護的size在removeMin()方法中已經做了減減的操作，是以當我們真正删除要删除的節點時：node.left = node.right = null；我們就不需要再維護一下size--的操作了。