Java 數(shù)據(jù)結(jié)構(gòu)篇-實現(xiàn)二叉搜索樹的核心方法

這篇具有很好參考價值的文章主要介紹了Java 數(shù)據(jù)結(jié)構(gòu)篇-實現(xiàn)二叉搜索樹的核心方法。希望對大家有所幫助。如果存在錯誤或未考慮完全的地方，請大家不吝賜教，您也可以點擊"舉報違法"按鈕提交疑問。

??博客主頁：?【小扳_-CSDN博客】
?感謝大家點贊??收藏?評論??

Java 數(shù)據(jù)結(jié)構(gòu)篇-實現(xiàn)二叉搜索樹的核心方法,Java 數(shù)據(jù)結(jié)構(gòu)與算法篇,數(shù)據(jù)結(jié)構(gòu),java,鏈表,算法

文章目錄

? ? ? ? 1.0 二叉搜索樹的概述

? ? ? ? 2.0 二叉搜索樹的成員變量及其構(gòu)造方法

? ? ? ? 3.0 實現(xiàn)二叉樹的核心接口

? ? ? ? 3.1?實現(xiàn)二叉搜索樹 - 獲取值?get(int key)

? ? ? ? 3.2?實現(xiàn)二叉搜索樹 - 獲取最小的關(guān)鍵字?min(BinaryNode node)

????????3.3?實現(xiàn)二叉搜索樹 -?獲取最大的關(guān)鍵字?max(BinaryNode node)

? ? ? ? 3.4?實現(xiàn)二叉搜索樹 - 增、更新 put( int key, Object value)

? ? ? ? 3.5 實現(xiàn)二叉搜索樹 - 查找關(guān)鍵字的后驅(qū)節(jié)點?successor(int key)

? ? ? ? 3.6 實現(xiàn)二叉搜索樹 -?查找關(guān)鍵字的前驅(qū)節(jié)點?predecessor(int key)

? ? ? ? 3.7 實現(xiàn)二叉搜索樹 - 刪除關(guān)鍵字節(jié)點 delete(int key)

? ? ? ? 3.8 實現(xiàn)二叉搜索樹 - 查找范圍小于關(guān)鍵字的節(jié)點值?less(int key)

? ? ? ? 3.9?實現(xiàn)二叉搜索樹 - 查找范圍大于關(guān)鍵字的節(jié)點值?greater(int key)

? ? ? ? 4.0 實現(xiàn)二叉搜索樹 - 查找范圍大于 k1 且小于 k2 關(guān)鍵字的節(jié)點值?between(int k1, int k2)

? ? ? ? 5.0 實現(xiàn)二叉搜索樹核心方法的完整代碼

? ? ? ? 1.0 二叉搜索樹的概述

????????二叉搜索樹是一種數(shù)據(jù)結(jié)構(gòu)，用于存儲數(shù)據(jù)并支持快速的插入、刪除和搜索操作。它是一種樹形結(jié)構(gòu)。

????????它具有以下特點：

? ? ? ? ? ? ? ? - 每個節(jié)點最多有兩個子節(jié)點，分別稱為左子節(jié)點和右子節(jié)點。

? ? ? ? ? ? ? ? - 對于每個節(jié)點，其左子節(jié)點的值小于該節(jié)點的值，右子節(jié)點的值大于該節(jié)點的值。

? ? ? ? ? ? ? ? - 中序遍歷二叉搜索樹可以得到有序的元素序列。

????????由于其特性，二叉搜索樹在插入、刪除和搜索操作上具有較高的效率。在平均情況下，這些操作的時間復雜度為 O(log n)，其中 n 為樹中節(jié)點的數(shù)量。然而，如果樹的結(jié)構(gòu)不平衡，最壞情況下這些操作的時間復雜度可能會達到 O(n)。由于其高效的搜索特性，二叉搜索樹常被用于實現(xiàn)關(guān)聯(lián)數(shù)組和集合等數(shù)據(jù)結(jié)構(gòu)。然而，為了避免樹的結(jié)構(gòu)不平衡導致性能下降，人們也發(fā)展了平衡二叉搜索樹（如紅黑樹、AVL樹）等變種。

? ? ? ? 2.0 二叉搜索樹的成員變量及其構(gòu)造方法

? ? ? ? 外部類成員變量有：根節(jié)點、節(jié)點類（內(nèi)部類）。

????????外部類構(gòu)造方法：默認的構(gòu)造方法，對外公開二叉搜索樹的核心方法。

????????節(jié)點類的成員變量有：

????????????????- key 關(guān)鍵字：相對比一般的二叉樹，二叉搜索樹可以明顯提高增刪查改的效率原因在于關(guān)鍵字，可以根據(jù)比較兩個關(guān)鍵字的大小進行操作。

????????????????- value 值：作用則為存放值。

????????????????- left ：鏈接左節(jié)點。

????????????????- right：鏈接右節(jié)點。

????????節(jié)點類的構(gòu)造方法：

? ? ? ? ? ? ? ? 帶兩個參數(shù)的構(gòu)造方法：參數(shù)為 key 、value?

? ? ? ? ? ? ? ? 帶四個參數(shù)的構(gòu)造方法：參數(shù)為 key 、value 、left 、right

代碼如下：

public class BinaryTree {

    BinaryNode root = null;
    static class BinaryNode {
        int key;
        Object value;
        BinaryNode left;
        BinaryNode right;

        public BinaryNode(int kty, Object value) {
            this.key = kty;
            this.value = value;
        }

        public BinaryNode(int key, Object value, BinaryNode left, BinaryNode right) {
            this.key = key;
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }

}

? ? ? ? 補充二叉搜索樹在增、刪、查、改的效率高的原因：

????????二叉搜索樹的高效性與其關(guān)鍵字的特性密切相關(guān)。二叉搜索樹的關(guān)鍵特性是，對于每個節(jié)點，其左子節(jié)點的值小于該節(jié)點的值，右子節(jié)點的值大于該節(jié)點的值。這種特性使得在二叉搜索樹中進行搜索、插入和刪除操作時，可以通過比較關(guān)鍵字的大小來快速定位目標節(jié)點，從而實現(xiàn)高效的操作。在平均情況下，這些操作的時間復雜度為 O(log n)，其中 n 為樹中節(jié)點的數(shù)量。因此，關(guān)鍵字的有序性是二叉搜索樹能夠?qū)崿F(xiàn)高效操作的關(guān)鍵原因之一。

? ? ? ? 3.0 實現(xiàn)二叉樹的核心接口

?
public interface BinarySearchTreeInterface {

    /**
     *查找 key 對應(yīng)的 value
     */
    Object get(int key);

    /**
     * 查找最小關(guān)鍵字對應(yīng)值
     */
    Object min();

    /**
     * 查找最大關(guān)鍵字對應(yīng)值
     */
    Object max();

    /**
     * 存儲關(guān)鍵字與對應(yīng)值
     */
    void put(int key, Object value);

    /**
     * 查找關(guān)鍵字的后驅(qū)
     */
    Object successor(int key);

    /**
     * 查找關(guān)鍵字的前驅(qū)
     */
    Object predecessor(int key);

    /**
     * 根據(jù)關(guān)鍵字刪除
     */
    Object delete(int key);
}

?

? ? ? ? 3.1?實現(xiàn)二叉搜索樹 - 獲取值?get(int key)

? ? ? ? 實現(xiàn)思路為：從根節(jié)點開始，先判斷當前的節(jié)點 p.key 與 key 進行比較，若?p.key >?key，則向左子樹下潛 p = p.left ；若 p.key < key ，則向右子樹下潛 p = p.right ；若 p.key == key ，則找到到了關(guān)鍵字，返回該節(jié)點的值 p.value 。按這樣的規(guī)則一直循環(huán)下去，直到 p == null 退出循環(huán)，則說明沒有找到對應(yīng)的節(jié)點，則返回 null 。

代碼如下：

    @Override
    public Object get(int key) {
        if (root == null) {
            return null;
        }
        BinaryNode p = root;
        while(p != null) {
            if (p.key > key) {
                p = p.left;
            }else if (p.key < key) {
                p = p.right;
            }else {
                return p.value;
            }
        }
        return null;
    }

? ? ? ? 若 root 為 null ，則不需要再進行下去了，直接結(jié)束。

? ? ? ? 3.2?實現(xiàn)二叉搜索樹 - 獲取最小的關(guān)鍵字?min(BinaryNode node)

? ? ? ? 實現(xiàn)思路：在某一個樹中，需要得到最小的關(guān)鍵字，由根據(jù)數(shù)據(jù)結(jié)構(gòu)的特點，最小的關(guān)鍵字在數(shù)的最左邊，簡單來說：一直向左子樹遍歷下去，直到 p.left == null 時，則該 p 節(jié)點就是最小的關(guān)鍵字了。然后找到了最小的節(jié)點，返回該節(jié)點的值即可。

代碼如下：

非遞歸實現(xiàn)：

    @Override
    public Object min() {
        if (root == null) {
            return null;
        }
        BinaryNode p = root;
        while(p.left != null) {
            p = p.left;
        }
        return p.value;
    }
    //重載了一個方法，帶參數(shù)的方法。
    public Object min(BinaryNode node) {
        if (node == null) {
            return null;
        }
        BinaryNode p = node;
        while (p.left != null) {
            p = p.left;
        }
        return p.value;
    }

遞歸實現(xiàn)：

    //使用遞歸實現(xiàn)找最小關(guān)鍵字
    public Object minRecursion() {
        return doMin(root);
    }
    private Object doMin(BinaryNode node) {
        if (node == null) {
            return null;
        }
        if (node.left == null) {
            return node.value;
        }
        return doMin(node.left);
    }

????????

????????3.3?實現(xiàn)二叉搜索樹 -?獲取最大的關(guān)鍵字?max(BinaryNode node)

? ? ? ? 實現(xiàn)思路為：在某一個樹中，需要得到最大的關(guān)鍵字，由根據(jù)數(shù)據(jù)結(jié)構(gòu)的特點，最大的關(guān)鍵字在數(shù)的最右邊，簡單來說：一直向右子樹遍歷下去，直到 p.right == null 時，則該 p 節(jié)點就是最大的關(guān)鍵字了。然后找到了最大的節(jié)點，返回該節(jié)點的值即可。

代碼如下：

非遞歸實現(xiàn)：

    @Override
    public Object max() {
        if (root == null) {
            return null;
        }
        BinaryNode p = root;
        while(p.right != null) {
            p = p.right;
        }
        return p.value;
    }
    //重載了一個帶參數(shù)的方法
    public Object max(BinaryNode node) {
        if (node == null) {
            return null;
        }
        BinaryNode p = node;
        while (p.right != null) {
            p = p.right;
        }
        return p.value;
    }

遞歸實現(xiàn)：

    //使用遞歸實現(xiàn)找最大關(guān)鍵字
    public Object maxRecursion() {
        return doMax(root);
    }
    private Object doMax(BinaryNode node) {
        if (node == null) {
            return null;
        }
        if (node.right == null) {
            return node.value;
        }
        return doMax(node.right);
    }

? ? ? ? 3.4?實現(xiàn)二叉搜索樹 - 增、更新 put( int key, Object value)

? ? ? ? 實現(xiàn)思路為：在二叉搜索樹中先試著查找是否存在與 key 對應(yīng)的節(jié)點 p.key 。若找到了，則為更新該值 p.value = value 即可。若找不到，則需要新增該關(guān)鍵字節(jié)點。

? ? ? ? 具體來分析如何新增關(guān)鍵字，先定義 BinaryNode parent 、 BinaryNode p，p 指針在去比較 key 之前，先讓 parent 指向 p 。最后循環(huán)結(jié)束后， p == null ，對于 parent 來說，此時正指著 p 節(jié)點的雙親節(jié)點。接著創(chuàng)建一個新的節(jié)點，BinaryNode newNode = new BinaryNode(key, value) ，則此時還需要考慮的是，該新的節(jié)點該連接到 parent 的左孩子還是右孩子？需要比較 parent.key 與 newNode.key 的大小即可，若?parent.key >?newNode.key，則鏈接到 parent.left?處；若 prent.key < newNode.key ，則連接到 parent.right 處。

代碼如下：

    @Override
    public void put(int key, Object value) {
        if (root == null) {
            root = new BinaryNode(key,value);
            return;
        }
        BinaryNode p = root;
        BinaryNode parent = null;
        while (p != null) {
            parent = p;
            if (p.key > key) {
                p = p.left;
            } else if (p.key < key) {
                p = p.right;
            }else {
                p.value = value;
                return;
            }
        }

        //該樹沒有該關(guān)鍵字，因此需要新建節(jié)點對象
        BinaryNode newNode = new BinaryNode(key,value);
        if (newNode.key < parent.key) {
            parent.left = newNode;
        }else {
            parent.right = newNode;
        }

    }

? ? ? ? 3.5 實現(xiàn)二叉搜索樹 - 查找關(guān)鍵字的后驅(qū)節(jié)點?successor(int key)

? ? ? ? 具體實現(xiàn)思路為：先遍歷找到該關(guān)鍵字的節(jié)點，若找不到，則返回 null ；若找到了，判斷以下的兩種情況，第一種情況：該節(jié)點有右子樹，則該關(guān)鍵字的后驅(qū)為右子樹的最小關(guān)鍵字；第二種情況：該節(jié)點沒有右子樹，則該關(guān)鍵字的后驅(qū)為從右向左而來的祖宗節(jié)點。最后返回該后驅(qū)節(jié)點的值?

代碼如下：

    @Override
    public Object successor(int key) {
        if (root == null) {
            return null;
        }
        //先找到該關(guān)鍵字節(jié)點
        BinaryNode p = root;
        BinaryNode sParent = null;
        while (p != null) {
            if (p.key > key) {
                sParent = p;
                p = p.left;
            } else if (p.key < key) {
                p = p.right;
            }else {
                break;
            }
        }
        //沒有找到關(guān)鍵字的情況
        if (p == null) {
            return null;
        }

        //情況一:該節(jié)點存在右子樹,則該后繼為右子樹的最小關(guān)鍵字
        if (p.right != null) {
            return min(p.right);
        }

        //情況二:該節(jié)點不存在右子樹，那么該后繼就需要到祖宗從右向左的節(jié)點
        if (sParent == null) {
            //可能不存在后繼節(jié)點,比如最大關(guān)鍵字的節(jié)點就沒有后繼節(jié)點了
            return null;
        }
        return sParent.value;
    }

? ? ? ? 3.6 實現(xiàn)二叉搜索樹 -?查找關(guān)鍵字的前驅(qū)節(jié)點?predecessor(int key)

? ? ? ? 具體實現(xiàn)思路為：先對該二叉樹進行遍歷尋找 key 的節(jié)點，若遍歷結(jié)束還沒找到，則返回 null ；若找到了，需要判斷以下兩種情況：

? ? ? ? 第一種情況：該節(jié)點有左子樹，則該前驅(qū)節(jié)點為該左子樹的最大關(guān)鍵字節(jié)點。

? ? ? ? 第二種情況：該節(jié)點沒有左子樹，則該前驅(qū)節(jié)點為從左向右而來的祖宗節(jié)點。

? ? ? ? 最后返回該前驅(qū)節(jié)點的值。

代碼如下：

    @Override
    public Object predecessor(int key) {
        if (root == null) {
            return null;
        }
        BinaryNode p = root;
        BinaryNode sParent = null;
        while (p != null) {
            if (p.key > key) {
                p = p.left;
            } else if (p.key < key) {
                sParent = p;
                p = p.right;
            }else {
                break;
            }
        }
        if (p == null) {
            return null;
        }
        //情況一:存在左子樹，則該前任就為左子樹的最大關(guān)鍵字節(jié)點
        if (p.left != null) {
            return max(p.left);
        }
        //情況二:不存在左子樹，則該前任為從祖宗自左向右而來的節(jié)點
        if (sParent == null) {
            return null;
        }
        return sParent.value;
    }

? ? ? ? 3.7 實現(xiàn)二叉搜索樹 - 刪除關(guān)鍵字節(jié)點 delete(int key)

? ? ? ? 具體實現(xiàn)思路為：先遍歷二叉樹，查找該關(guān)鍵字節(jié)點。若遍歷結(jié)束了還沒有找到，則返回 null ；若找到了，則需要以下四種情況：

? ? ? ? 第一種情況：找到該刪除的節(jié)點只有左子樹。則直接讓該左子樹 "托付" 給刪除節(jié)點的雙親節(jié)點，這就刪除了該節(jié)點了。至于左子樹是鏈接到雙親節(jié)點的左邊還有右邊這個問題，根據(jù)該數(shù)據(jù)結(jié)構(gòu)的特點，由該刪除節(jié)點來決定。若刪除的節(jié)點之前是鏈接該雙親節(jié)點的左邊，則左子樹也是鏈接到該雙親節(jié)點的左邊；若刪除的節(jié)點之前是鏈接該雙親節(jié)點的右邊，則左子樹也是鏈接到該雙親節(jié)點的右邊。

? ? ? ? 第二種情況：找到該刪除的節(jié)點只有右子樹。則直接讓該右子樹 "托付" 給刪除節(jié)點的雙親節(jié)點，這就刪除了該節(jié)點了。至于右子樹是鏈接到雙親節(jié)點的左邊還有右邊這個問題，根據(jù)該數(shù)據(jù)結(jié)構(gòu)的特點，由該刪除節(jié)點來決定。若刪除的節(jié)點之前是鏈接該雙親節(jié)點的左邊，則右子樹也是鏈接到該雙親節(jié)點的左邊；若刪除的節(jié)點之前是鏈接該雙親節(jié)點的右邊，則右子樹也是鏈接到該雙親節(jié)點的右邊。

? ? ? ? 第三種情況：找到該刪除節(jié)點都沒有左右子樹。該情況可以歸并到以上兩種情況的任意一種處理均可。

? ? ? ? 第四種情況：找到該刪除節(jié)點都有左右子樹。分兩步：第一步，先找后繼節(jié)點來替換刪除節(jié)點，找該后繼節(jié)點直接到刪除節(jié)點的右子樹中找最小的關(guān)鍵字節(jié)點即可。第二步，需要先將后繼節(jié)點的右子樹處理好，需要將該右子樹交給替換節(jié)點的雙親節(jié)點鏈接。還需要判斷兩種情況：第一種情況，若刪除節(jié)點與替換節(jié)點是緊挨著的，對替換節(jié)點的右子樹無需要求，只對左子樹重新賦值；若刪除節(jié)點與替換節(jié)點不是緊挨著的關(guān)系，對替換節(jié)點的左右子樹都要重新賦值。

代碼如下：

    @Override
    public Object delete(int key) {
        if (root == null) {
            return null;
        }
        BinaryNode p = root;
        BinaryNode parent = null;
        while (p != null) {
            if (p.key > key) {
                parent = p;
                p = p.left;
            } else if (p.key < key) {
                parent = p;
                p = p.right;
            }else {
                break;
            }
        }
        //沒有找到該關(guān)鍵字的節(jié)點
        if (p == null) {
            return null;
        }

        //情況一、二、三:只有左子樹或者右子樹或者都沒有
        if (p.right == null) {
            shift(parent,p,p.left);
        } else if (p.left == null) {
            shift(parent,p,p.right);
        }else {
            //情況四:有左右子樹
            //替換節(jié)點采用刪除節(jié)點的后繼節(jié)點
            //先看被刪的節(jié)點與替換的節(jié)點是否為緊挨在一起
            BinaryNode s = p.right;
            BinaryNode sParent = p;
            while (s.left != null) {
                sParent = s;
                s = s.left;
            }
            if (sParent != p) {
                //說明沒有緊挨在一起，則需要將替換節(jié)點的右子樹進行處理
                shift(sParent,s,s.right);
                s.right = p.right;
            }
            shift(parent,p,s);
            s.left = p.left;
        }

        return p.value;
    }
    private void shift(BinaryNode parent, BinaryNode delete, BinaryNode next) {
        if (parent == null) {
            root = next;
        } else if (parent.left == delete) {
            parent.left = next;
        }else if (parent.right == delete){
            parent.right = next;
        }
    }

? ? ? ? 為了方便，將刪除節(jié)點與替換節(jié)點之間的替換操作單獨成一個方法出來。

????????遞歸實現(xiàn)刪除關(guān)鍵字 key 節(jié)點，同理，也是細分為以上描述的四種情況。

代碼如下：

    //使用遞歸實現(xiàn)刪除關(guān)鍵字節(jié)點
    public BinaryNode deleteRecursion(BinaryNode node , int key) {
        if (node == null) {
            return null;
        }
        if (node.key > key) {
            node.left = deleteRecursion(node.left,key);
            return node;
        } else if (node.key < key) {
            node.right = deleteRecursion(node.right,key);
            return node;
        }else {
            if (node.right == null) {
                return node.left;
            } else if (node.left == null) {
                return node.right;
            }else {
                BinaryNode s = node.right;
                while (s.left != null) {
                    s = s.left;
                }

                s.right = deleteRecursion(node.right,s.key);
                s.left = node.left;
                return s;
            }

        }
    }

? ? ? ? 3.8 實現(xiàn)二叉搜索樹 - 查找范圍小于關(guān)鍵字的節(jié)點值?less(int key)

? ? ? ? 具體實現(xiàn)思路為：利用中序遍歷，來遍歷每一個節(jié)點的 key ，若小于 key 的節(jié)點，直接放到數(shù)組容器中；若大于 key 的，可以直接退出循環(huán)。最后返回該數(shù)組容器即可。

代碼如下：

    //找 < key 的所有 value
    public List<Object> less(int key) {
        if (root == null) {
            return null;
        }
        ArrayList<Object> result = new ArrayList<>();
        BinaryNode p = root;
        Stack<BinaryNode> stack = new Stack<>();
        while (p != null || !stack.isEmpty()) {
            if (p != null) {
                stack.push(p);
                p = p.left;
            }else {
                BinaryNode pop = stack.pop();
                if (pop.key < key) {
                    result.add(pop.value);
                }else {
                    break;
                }
                p = pop.right;
            }
        }
        return result;
    }

? ? ? ? 3.9?實現(xiàn)二叉搜索樹 - 查找范圍大于關(guān)鍵字的節(jié)點值?greater(int key)

? ? ? ? 具體實現(xiàn)思路：利用中序遍歷，來遍歷每一個節(jié)點的 key ，若大于 key 的節(jié)點，直接放到數(shù)組容器中。

代碼如下：

    //找 > key 的所有 value
    public List<Object> greater(int key) {
        if (root == null) {
            return null;
        }
        ArrayList<Object> result = new ArrayList<>();
        Stack<BinaryNode> stack = new Stack<>();
        BinaryNode p = root;
        while (p != null || !stack.isEmpty()) {
            if (p != null) {
                stack.push(p);
                p = p.left;
            }else {
                BinaryNode pop = stack.pop();
                if (pop.key > key) {
                    result.add(pop.value);
                }
                p = pop.right;
            }
        }
        return result;
    }

該方法的改進：遍歷方向進行調(diào)整，先從右子樹開始，再訪問根節(jié)點，最后才到左子樹。因此只要小于 key 的關(guān)鍵字節(jié)點，直接退出循環(huán)。

代碼如下：

    //改進思路:遍歷方向進行調(diào)整，先從右子樹開始，再訪問根節(jié)點，最后才到左子樹
    public List<Object> greater1(int key) {
        if (root == null) {
            return null;
        }
        ArrayList<Object> result = new ArrayList<>();
        Stack<BinaryNode> stack = new Stack<>();
        BinaryNode p = root;
        while (p != null || !stack.isEmpty()) {
            if (p != null ) {
                stack.push(p);
                p = p.right;
            }else {
                BinaryNode pop = stack.pop();
                if (pop.key > key) {
                    result.add(pop.value);
                }else {
                    break;
                }
                p = pop.left;
            }
        }
        return result;
    }

? ? ? ? 4.0 實現(xiàn)二叉搜索樹 - 查找范圍大于 k1 且小于 k2 關(guān)鍵字的節(jié)點值?between(int k1, int k2)

? ? ? ? 實現(xiàn)思路跟以上的思路沒有什么區(qū)別，唯一需要注意的是，當前節(jié)點的 key > k2 則可以退出循環(huán)了。

代碼如下：

//找到 >= k1 且 =< k2 的所有value
    public List<Object> between(int k1, int k2) {
        if (root == null) {
            return null;
        }
        ArrayList<Object> result = new ArrayList<>();
        Stack<BinaryNode> stack = new Stack<>();
        BinaryNode p = root;
        while(p != null || !stack.isEmpty()) {
            if (p != null) {
                stack.push(p);
                p = p.left;
            }else {
                BinaryNode pop = stack.pop();
                if (pop.key >= k1 && pop.key <= k2) {
                    result.add(pop.value);
                } else if (pop.key > k2) {
                    break;
                }
                p = pop.right;
            }
        }
            return result;
    }

? ? ? ? 5.0 實現(xiàn)二叉搜索樹核心方法的完整代碼

實現(xiàn)接口代碼：

import java.util.ArrayList;

import java.util.List;
import java.util.Stack;

public class BinaryTree implements BinarySearchTreeInterface{

    BinaryNode root = null;
    static class BinaryNode {
        int key;
        Object value;
        BinaryNode left;
        BinaryNode right;

        public BinaryNode(int kty, Object value) {
            this.key = kty;
            this.value = value;
        }

        public BinaryNode(int key, Object value, BinaryNode left, BinaryNode right) {
            this.key = key;
            this.value = value;
            this.left = left;
            this.right = right;
        }
    }

    @Override
    public Object get(int key) {
        if (root == null) {
            return null;
        }
        BinaryNode p = root;
        while(p != null) {
            if (p.key > key) {
                p = p.left;
            }else if (p.key < key) {
                p = p.right;
            }else {
                return p.value;
            }
        }
        return null;
    }

    @Override
    public Object min() {
        if (root == null) {
            return null;
        }
        BinaryNode p = root;
        while(p.left != null) {
            p = p.left;
        }
        return p.value;
    }
    public Object min(BinaryNode node) {
        if (node == null) {
            return null;
        }
        BinaryNode p = node;
        while (p.left != null) {
            p = p.left;
        }
        return p.value;
    }

    //使用遞歸實現(xiàn)找最小關(guān)鍵字
    public Object minRecursion() {
        return doMin(root);
    }
    private Object doMin(BinaryNode node) {
        if (node == null) {
            return null;
        }
        if (node.left == null) {
            return node.value;
        }
        return doMin(node.left);
    }


    @Override
    public Object max() {
        if (root == null) {
            return null;
        }
        BinaryNode p = root;
        while(p.right != null) {
            p = p.right;
        }
        return p.value;
    }
    public Object max(BinaryNode node) {
        if (node == null) {
            return null;
        }
        BinaryNode p = node;
        while (p.right != null) {
            p = p.right;
        }
        return p.value;
    }

    //使用遞歸實現(xiàn)找最大關(guān)鍵字
    public Object maxRecursion() {
        return doMax(root);
    }
    private Object doMax(BinaryNode node) {
        if (node == null) {
            return null;
        }
        if (node.right == null) {
            return node.value;
        }
        return doMax(node.right);
    }


    @Override
    public void put(int key, Object value) {
        if (root == null) {
            root = new BinaryNode(key,value);
            return;
        }
        BinaryNode p = root;
        BinaryNode parent = null;
        while (p != null) {
            parent = p;
            if (p.key > key) {
                p = p.left;
            } else if (p.key < key) {
                p = p.right;
            }else {
                p.value = value;
                return;
            }
        }

        //該樹沒有該關(guān)鍵字，因此需要新建節(jié)點對象
        BinaryNode newNode = new BinaryNode(key,value);
        if (newNode.key < parent.key) {
            parent.left = newNode;
        }else {
            parent.right = newNode;
        }

    }

    @Override
    public Object successor(int key) {
        if (root == null) {
            return null;
        }
        //先找到該關(guān)鍵字節(jié)點
        BinaryNode p = root;
        BinaryNode sParent = null;
        while (p != null) {
            if (p.key > key) {
                sParent = p;
                p = p.left;
            } else if (p.key < key) {
                p = p.right;
            }else {
                break;
            }
        }
        //沒有找到關(guān)鍵字的情況
        if (p == null) {
            return null;
        }

        //情況一:該節(jié)點存在右子樹,則該后繼為右子樹的最小關(guān)鍵字
        if (p.right != null) {
            return min(p.right);
        }

        //情況二:該節(jié)點不存在右子樹，那么該后繼就需要到祖宗從右向左的節(jié)點
        if (sParent == null) {
            //可能不存在后繼節(jié)點,比如最大關(guān)鍵字的節(jié)點就沒有后繼節(jié)點了
            return null;
        }
        return sParent.value;
    }

    @Override
    public Object predecessor(int key) {
        if (root == null) {
            return null;
        }
        BinaryNode p = root;
        BinaryNode sParent = null;
        while (p != null) {
            if (p.key > key) {
                p = p.left;
            } else if (p.key < key) {
                sParent = p;
                p = p.right;
            }else {
                break;
            }
        }
        if (p == null) {
            return null;
        }
        //情況一:存在左子樹，則該前任就為左子樹的最大關(guān)鍵字節(jié)點
        if (p.left != null) {
            return max(p.left);
        }
        //情況二:不存在左子樹，則該前任為從祖宗自左向右而來的節(jié)點
        if (sParent == null) {
            return null;
        }
        return sParent.value;
    }

    @Override
    public Object delete(int key) {
        if (root == null) {
            return null;
        }
        BinaryNode p = root;
        BinaryNode parent = null;
        while (p != null) {
            if (p.key > key) {
                parent = p;
                p = p.left;
            } else if (p.key < key) {
                parent = p;
                p = p.right;
            }else {
                break;
            }
        }
        //沒有找到該關(guān)鍵字的節(jié)點
        if (p == null) {
            return null;
        }

        //情況一、二、三:只有左子樹或者右子樹或者都沒有
        if (p.right == null) {
            shift(parent,p,p.left);
        } else if (p.left == null) {
            shift(parent,p,p.right);
        }else {
            //情況四:有左右子樹
            //替換節(jié)點采用刪除節(jié)點的后繼節(jié)點
            //先看被刪的節(jié)點與替換的節(jié)點是否為緊挨在一起
            BinaryNode s = p.right;
            BinaryNode sParent = p;
            while (s.left != null) {
                sParent = s;
                s = s.left;
            }
            if (sParent != p) {
                //說明沒有緊挨在一起，則需要將替換節(jié)點的右子樹進行處理
                shift(sParent,s,s.right);
                s.right = p.right;
            }
            shift(parent,p,s);
            s.left = p.left;
        }

        return p.value;
    }
    private void shift(BinaryNode parent, BinaryNode delete, BinaryNode next) {
        if (parent == null) {
            root = next;
        } else if (parent.left == delete) {
            parent.left = next;
        }else if (parent.right == delete){
            parent.right = next;
        }
    }

    //使用遞歸實現(xiàn)刪除關(guān)鍵字節(jié)點
    public BinaryNode deleteRecursion(BinaryNode node , int key) {
        if (node == null) {
            return null;
        }
        if (node.key > key) {
            node.left = deleteRecursion(node.left,key);
            return node;
        } else if (node.key < key) {
            node.right = deleteRecursion(node.right,key);
            return node;
        }else {
            if (node.right == null) {
                return node.left;
            } else if (node.left == null) {
                return node.right;
            }else {
                BinaryNode s = node.right;
                while (s.left != null) {
                    s = s.left;
                }

                s.right = deleteRecursion(node.right,s.key);
                s.left = node.left;
                return s;
            }

        }
    }

    //找 < key 的所有 value
    public List<Object> less(int key) {
        if (root == null) {
            return null;
        }
        ArrayList<Object> result = new ArrayList<>();
        BinaryNode p = root;
        Stack<BinaryNode> stack = new Stack<>();
        while (p != null || !stack.isEmpty()) {
            if (p != null) {
                stack.push(p);
                p = p.left;
            }else {
                BinaryNode pop = stack.pop();
                if (pop.key < key) {
                    result.add(pop.value);
                }else {
                    break;
                }
                p = pop.right;
            }
        }
        return result;
    }

    //找 > key 的所有 value
    public List<Object> greater(int key) {
        if (root == null) {
            return null;
        }
        ArrayList<Object> result = new ArrayList<>();
        Stack<BinaryNode> stack = new Stack<>();
        BinaryNode p = root;
        while (p != null || !stack.isEmpty()) {
            if (p != null) {
                stack.push(p);
                p = p.left;
            }else {
                BinaryNode pop = stack.pop();
                if (pop.key > key) {
                    result.add(pop.value);
                }
                p = pop.right;
            }
        }
        return result;
    }
    //改進思路:遍歷方向進行調(diào)整，先從右子樹開始，再訪問根節(jié)點，最后才到左子樹
    public List<Object> greater1(int key) {
        if (root == null) {
            return null;
        }
        ArrayList<Object> result = new ArrayList<>();
        Stack<BinaryNode> stack = new Stack<>();
        BinaryNode p = root;
        while (p != null || !stack.isEmpty()) {
            if (p != null ) {
                stack.push(p);
                p = p.right;
            }else {
                BinaryNode pop = stack.pop();
                if (pop.key > key) {
                    result.add(pop.value);
                }else {
                    break;
                }
                p = pop.left;
            }
        }
        return result;
    }


    //找到 >= k1 且 =< k2 的所有value
    public List<Object> between(int k1, int k2) {
        if (root == null) {
            return null;
        }
        ArrayList<Object> result = new ArrayList<>();
        Stack<BinaryNode> stack = new Stack<>();
        BinaryNode p = root;
        while(p != null || !stack.isEmpty()) {
            if (p != null) {
                stack.push(p);
                p = p.left;
            }else {
                BinaryNode pop = stack.pop();
                if (pop.key >= k1 && pop.key <= k2) {
                    result.add(pop.value);
                } else if (pop.key > k2) {
                    break;
                }
                p = pop.right;
            }
        }
            return result;
    }

}

Java 數(shù)據(jù)結(jié)構(gòu)篇-實現(xiàn)二叉搜索樹的核心方法,Java 數(shù)據(jù)結(jié)構(gòu)與算法篇,數(shù)據(jù)結(jié)構(gòu),java,鏈表,算法

?文章來源地址http://www.zghlxwxcb.cn/news/detail-760399.html

到了這里，關(guān)于Java 數(shù)據(jù)結(jié)構(gòu)篇-實現(xiàn)二叉搜索樹的核心方法的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！