二叉查找樹

樹的基本定義

樹是我們計算機中非常重要的一種資料結構，同時使用樹這種資料結構，可以描述現實生活中的很多事物，例如家 譜、機關的組織架構、等等。

樹是由n（n>=1）個有限結點組成一個具有層次關系的集合。把它叫做“樹”是因為它看起來像一棵倒挂的樹，也就是說它是根朝上，而葉朝下的。

樹具有以下特點：

• 每個結點有零個或多個子結點；
• 沒有父結點的結點為根結點；
• 每一個非根結點隻有一個父結點；
• 每個結點及其後代結點整體上可以看做是一棵樹，稱為目前結點的父結點的一個子樹；

樹的相關術語

結點的度： 一個結點含有的子樹的個數稱為該結點的度；

葉結點： 度為0的結點稱為葉結點，也可以叫做終端結點

分支結點： 度不為0的結點稱為分支結點，也可以叫做非終端結點

結點的層次： 從根結點開始，根結點的層次為1，根的直接後繼層次為2，以此類推

結點的層序編号：将樹中的結點，按照從上層到下層，同層從左到右的次序排成一個線性序列，把他們編成連續的自然數。

樹的度： 樹中所有結點的度的最大值

樹的高度(深度)： 樹中結點的最大層次

森林： m（m>=0）個互不相交的樹的集合，将一顆非空樹的根結點删去，樹就變成一個森林；給森林增加一個統一的根 結點，森林就變成一棵樹

孩子結點： 一個結點的直接後繼結點稱為該結點的孩子結點

雙親結點(父結點)： 一個結點的直接前驅稱為該結點的雙親結點

兄弟結點： 同一雙親結點的孩子結點間互稱兄弟結點

二叉樹

二叉樹就是度不超過2的樹(每個結點最多有兩個子結點)

滿二叉樹： 一個二叉樹，如果每一個層的結點樹都達到最大值，則這個二叉樹就是滿二叉樹。

完全二叉樹： 葉節點隻能出現在最下層和次下層，并且最下面一層的結點都集中在該層最左邊的若幹位置的二叉樹

二叉查找樹實作

根據對圖的觀察，我們發現二叉樹其實就是由一個一個的結點及其之間的關系組成的，按照面向對象的思想，我們 設計一個結點類來描述結點這個事物。

節點類如下：

private class Node {
        //存儲鍵
        public Key key;
        //存儲值
        private Value value;
        //記錄左子結點
        public Node left;
        //記錄右子結點
        public Node right;

        public Node(Key key, Value value, Node left, Node right) {
            this.key = key;
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }
           

樹的設計：

public class BinaryTree<Key extends Comparable<Key>, Value> {
    //根節點
    private Node root;
    
    private int N;

    public int size(){
        return N;
    }

    private class Node { //.....}
}
           

插入方法put

插入方法的實作思想：

• 如果目前樹中沒有任何一個結點，則直接把新結點當做根結點使用
• 如果目前樹不為空，則從根結點開始：
  • 如果新結點的key小于目前結點的key，則繼續找目前結點的左子結點；
  • 新結點的key大于目前結點的key，則繼續找目前結點的右子結點；
  • 如果新結點的key等于目前結點的key，則樹中已經存在這樣的結點，替換該結點的value值即可。

代碼實作如下：

public void put(Key key, Value value) {
        root = put(root, key, value);
    }

    /**
     * 向指定的樹x中添加key-value,并傳回添加元素後新的樹
     * @author wen.jie
     * @date 2021/8/23 10:56
     */
    private Node put(Node x, Key key, Value value) {
        //x子樹為空
        if (x == null) {
            N++;
            return new Node(key, value, null , null);
        }

        //x子樹不為空
        int cmp = key.compareTo(x.key);

        if (cmp > 0) {
            x.right = put(x.right, key, value);
        }else if(cmp < 0){
            x.left = put(x.left, key, value);
        }else {
            x.value = value;
        }
        return x;
    }
           

查詢方法get

查詢方法思路與插入方法類似，下面給出實作：

/**
     * @author wen.jie
     * @date 2021/8/23 11:02
     * 查找樹中指定key對應的value
     */
    public Value get(Key key){
        return get(root, key);
    }

    private Value get(Node x, Key key) {
        //x子樹為空
        if (x == null) return null;
        //x子樹不為空
        int cmp = key.compareTo(x.key);
        if (cmp > 0) {
            return get(x.right, key);
        }else if(cmp < 0){
            return get(x.left, key);
        }else {
            return x.value;
        }
    }
           

删除方法delete

删除方法思路：

1.找到被删除結點；

2.找到被删除結點右子樹中的最小結點minNode

3.删除右子樹中的最小結點

4.讓被删除結點的左子樹稱為最小結點minNode的左子樹，讓被删除結點的右子樹稱為最小結點minNode的右子 樹

5.讓被删除結點的父節點指向最小結點minNode

代碼實作：

/**
     * @author wen.jie
     * @date 2021/8/23 11:28
     * 删除樹中key對應的value
     */
    public void delete(Key key){
        root = delete(root, key);
    }

    /**
     * @author wen.jie
     * @date 2021/8/23 11:28
     * 删除指定樹x中的key對應的value,并傳回删除後的新樹
     */
    public Node delete(Node x, Key key){
        if (x == null) return null;

        int cmp = key.compareTo(x.key);
        if (cmp > 0) {
            //找x節點的右子樹
            x.right = delete(x.right, key);
        }else if(cmp < 0){
            //找x節點的左子樹
            x.left = delete(x.left, key);
        }else {
            N--;
            if(x.right == null) return x.left;
            if(x.left == null) return x.right;

            //得找到右子樹中最小的節點
            Node minNode = min(x.right);

            //删除右子樹最小的節點,傳回新的右子樹
            Node n = deleteMin(x.right);

            //讓x節點的左子樹成為minNode的左子樹
            minNode.left = x.left;
            //讓新的右子樹成為minNode的右子樹
            minNode.right = n;
            return minNode;
        }

        return x;
    }

    /**
     * @author wen.jie
     * @date 2021/8/23 16:47
     * 删除指定樹中最小的節點,并傳回新的樹
     */
    private Node deleteMin(Node x){
        if(x.left == null) return x.right;
        x.left = deleteMin(x.left);
        return x;
    }

    /**
     * @author wen.jie
     * @date 2021/8/23 16:43
     * 傳回指定樹中最小的節點
     */
    private Node min(Node x){
        if(x.left == null) return x;
        return min(x.left);
    }
           

二叉樹的基礎周遊

很多情況下，我們可能需要像周遊數組數組一樣，周遊樹，進而拿出樹中存儲的每一個元素，由于樹狀結構和線性結構不一樣，它沒有辦法從頭開始依次向後周遊，是以存在如何周遊，也就是按照什麼樣的搜尋路徑進行周遊的問題。

我們把樹簡單的畫作上圖中的樣子，由一個根節點、一個左子樹、一個右子樹組成，那麼按照根節點什麼時候被通路，我們可以把二叉樹的周遊分為以下三種方式：

• 前序周遊； 先通路根結點，然後再通路左子樹，最後通路右子樹
• 中序周遊； 先通路左子樹，中間通路根節點，最後通路右子樹
• 後序周遊； 先通路左子樹，再通路右子樹，最後通路根節點

如果我們分别對下面的樹使用三種周遊方式進行周遊，得到的結果如下：

代碼實作：Queue隊列的代碼見：javascript:void(0)

/**
     * @author wen.jie
     * @date 2021/8/23 17:26
     * 前序周遊擷取整個樹中所有的鍵
     */
    public Queue<Key> preErgodic() {
        Queue<Key> keys = new Queue<>();
        preErgodic(root, keys);
        return keys;
    }

    private void preErgodic(Node x, Queue<Key> keys){
        if(x == null) return;
        keys.enqueue(x.key);
        if(x.left != null) preErgodic(x.left, keys);
        if(x.right != null) preErgodic(x.right, keys);
    }

    /**
     * @author wen.jie
     * @date 2021/8/23 17:26
     * 中序周遊擷取整個樹中所有的鍵
     */
    public Queue<Key> midErgodic() {
        Queue<Key> keys = new Queue<>();
        midErgodic(root, keys);
        return keys;
    }

    private void midErgodic(Node x, Queue<Key> keys){
        if(x == null) return;
        if(x.left != null) midErgodic(x.left, keys);
        keys.enqueue(x.key);
        if(x.right != null) midErgodic(x.right, keys);
    }

    /**
     * @author wen.jie
     * @date 2021/8/23 17:26
     * 後序周遊擷取整個樹中所有的鍵
     */
    public Queue<Key> afterErgodic() {
        Queue<Key> keys = new Queue<>();
        afterErgodic(root, keys);
        return keys;
    }

    private void afterErgodic(Node x, Queue<Key> keys){
        if(x == null) return;
        if(x.left != null) afterErgodic(x.left, keys);
        if(x.right != null) afterErgodic(x.right, keys);
        keys.enqueue(x.key);
    }
           

二叉樹的層序周遊

所謂的層序周遊，就是從根節點（第一層）開始，依次向下，擷取每一層所有結點的值，有二叉樹如下：

那麼層序周遊的結果是：EBGADFHC

實作思路：

• 建立隊列，存儲每一層的結點；
• 使用循環從隊列中彈出一個結點：
  • 擷取目前結點的key；
  • 如果目前結點的左子結點不為空，則把左子結點放入到隊列中
  • 如果目前結點的右子結點不為空，則把右子結點放入到隊列中

public Queue<Key> layerErgodic(){
        Queue<Key> keys = new Queue<>();
        Queue<Node> nodes = new Queue<>();
        nodes.enqueue(root);

        while (!nodes.isEmpty()){
            Node node = nodes.dequeue();
            keys.enqueue(node.key);
            if(node.left != null) nodes.enqueue(node.left);
            if(node.right != null) nodes.enqueue(node.right);
        }
        return keys;
    }
           

二叉樹的最大深度問題

• 如果根結點為空，則最大深度為0；
• 計算左子樹的最大深度；
• 計算右子樹的最大深度；
• 目前樹的最大深度=左子樹的最大深度和右子樹的最大深度中的較大者+1

/**
     * @author wen.jie
     * @date 2021/8/23 17:56
     * 求整個樹的最大深度
     */
    public Integer maxDepth(){
        return maxDepth(root);
    }

    private Integer maxDepth(Node x){
        if (x == null)  return 0;
        int max = 0;
        int maxL = 0;
        int maxR = 0;
        //2.計算左子樹的最大深度；
        if (x.left != null) {
            maxL = maxDepth(x.left);
        }
        //3.計算右子樹的最大深度；
        if (x.right != null) {
            maxR = maxDepth(x.right);
        }
        //4.目前樹的最大深度=左子樹的最大深度和右子樹的最大深度中的較大者+1
        max = maxL > maxR ? maxL + 1 : maxR + 1;
        return max;
    }