欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

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

 更新時(shí)間：2023年12月22日 10:37:29   作者：小扳  
二叉搜索樹是一種常用的數(shù)據(jù)結(jié)構(gòu),它是一棵二叉樹,且每個(gè)節(jié)點(diǎn)的值都大于其左子樹中任何節(jié)點(diǎn)的值,而小于其右子樹中任何節(jié)點(diǎn)的值,這篇文章主要給大家介紹了關(guān)于Java數(shù)據(jù)結(jié)構(gòu)篇之實(shí)現(xiàn)二叉搜索樹的核心方法,需要的朋友可以參考下

1.0 二叉搜索樹的概述

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

它具有以下特點(diǎn)：

- 每個(gè)節(jié)點(diǎn)最多有兩個(gè)子節(jié)點(diǎn)，分別稱為左子節(jié)點(diǎn)和右子節(jié)點(diǎn)。

- 對于每個(gè)節(jié)點(diǎn)，其左子節(jié)點(diǎn)的值小于該節(jié)點(diǎn)的值，右子節(jié)點(diǎn)的值大于該節(jié)點(diǎn)的值。

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

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

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

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

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

節(jié)點(diǎn)類的成員變量有：

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

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

- left ：鏈接左節(jié)點(diǎn)。

- right：鏈接右節(jié)點(diǎn)。

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

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

帶四個(gè)參數(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;
        }
    }

}

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

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

3.0 實(shí)現(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();

    /**
     * 存儲(chǔ)關(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 實(shí)現(xiàn)二叉搜索樹 - 獲取值 get(int key)

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

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

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

代碼如下：

非遞歸實(shí)現(xiàn)：

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

遞歸實(shí)現(xiàn)：

    //使用遞歸實(shí)現(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 實(shí)現(xiàn)二叉搜索樹 - 獲取最大的關(guān)鍵字 max(BinaryNode node)

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

代碼如下：

非遞歸實(shí)現(xiàn)：

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

遞歸實(shí)現(xiàn)：

    //使用遞歸實(shí)現(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 實(shí)現(xiàn)二叉搜索樹 - 增、更新 put( int key, Object value)

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

具體來分析如何新增關(guān)鍵字，先定義 BinaryNode parent 、 BinaryNode p，p 指針在去比較 key 之前，先讓 parent 指向 p 。最后循環(huán)結(jié)束后， p == null ，對于 parent 來說，此時(shí)正指著 p 節(jié)點(diǎn)的雙親節(jié)點(diǎn)。 接著創(chuàng)建一個(gè)新的節(jié)點(diǎn)，BinaryNode newNode = new BinaryNode(key, value) ，則此時(shí)還需要考慮的是，該新的節(jié)點(diǎn)該連接到 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é)點(diǎn)對象
        BinaryNode newNode = new BinaryNode(key,value);
        if (newNode.key < parent.key) {
            parent.left = newNode;
        }else {
            parent.right = newNode;
        }

    }

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

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

代碼如下：

    @Override
    public Object successor(int key) {
        if (root == null) {
            return null;
        }
        //先找到該關(guān)鍵字節(jié)點(diǎn)
        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é)點(diǎn)存在右子樹,則該后繼為右子樹的最小關(guān)鍵字
        if (p.right != null) {
            return min(p.right);
        }

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

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

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

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

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

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

代碼如下：

    @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é)點(diǎn)
        if (p.left != null) {
            return max(p.left);
        }
        //情況二:不存在左子樹，則該前任為從祖宗自左向右而來的節(jié)點(diǎn)
        if (sParent == null) {
            return null;
        }
        return sParent.value;
    }

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

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

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

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

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

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

代碼如下：

    @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é)點(diǎn)
        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é)點(diǎn)采用刪除節(jié)點(diǎn)的后繼節(jié)點(diǎn)
            //先看被刪的節(jié)點(diǎn)與替換的節(jié)點(diǎn)是否為緊挨在一起
            BinaryNode s = p.right;
            BinaryNode sParent = p;
            while (s.left != null) {
                sParent = s;
                s = s.left;
            }
            if (sParent != p) {
                //說明沒有緊挨在一起，則需要將替換節(jié)點(diǎn)的右子樹進(jìn)行處理
                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é)點(diǎn)與替換節(jié)點(diǎn)之間的替換操作單獨(dú)成一個(gè)方法出來。

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

代碼如下：

    //使用遞歸實(shí)現(xiàn)刪除關(guān)鍵字節(jié)點(diǎn)
    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 實(shí)現(xiàn)二叉搜索樹 - 查找范圍小于關(guān)鍵字的節(jié)點(diǎn)值 less(int key)

具體實(shí)現(xiàn)思路為：利用中序遍歷，來遍歷每一個(gè)節(jié)點(diǎn)的 key ，若小于 key 的節(jié)點(diǎn)，直接放到數(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 實(shí)現(xiàn)二叉搜索樹 - 查找范圍大于關(guān)鍵字的節(jié)點(diǎn)值 greater(int key)

具體實(shí)現(xiàn)思路：利用中序遍歷，來遍歷每一個(gè)節(jié)點(diǎn)的 key ，若大于 key 的節(jié)點(diǎn)，直接放到數(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;
    }

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

代碼如下：

    //改進(jìn)思路:遍歷方向進(jìn)行調(diào)整，先從右子樹開始，再訪問根節(jié)點(diǎn)，最后才到左子樹
    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 實(shí)現(xiàn)二叉搜索樹 - 查找范圍大于 k1 且小于 k2 關(guān)鍵字的節(jié)點(diǎn)值 between(int k1, int k2)

實(shí)現(xiàn)思路跟以上的思路沒有什么區(qū)別，唯一需要注意的是，當(dāng)前節(jié)點(diǎn)的 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 實(shí)現(xiàn)二叉搜索樹核心方法的完整代碼

實(shí)現(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;
    }

    //使用遞歸實(shí)現(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;
    }

    //使用遞歸實(shí)現(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é)點(diǎn)對象
        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é)點(diǎn)
        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é)點(diǎn)存在右子樹,則該后繼為右子樹的最小關(guān)鍵字
        if (p.right != null) {
            return min(p.right);
        }

        //情況二:該節(jié)點(diǎn)不存在右子樹，那么該后繼就需要到祖宗從右向左的節(jié)點(diǎn)
        if (sParent == null) {
            //可能不存在后繼節(jié)點(diǎn),比如最大關(guān)鍵字的節(jié)點(diǎn)就沒有后繼節(jié)點(diǎn)了
            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é)點(diǎn)
        if (p.left != null) {
            return max(p.left);
        }
        //情況二:不存在左子樹，則該前任為從祖宗自左向右而來的節(jié)點(diǎn)
        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é)點(diǎn)
        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é)點(diǎn)采用刪除節(jié)點(diǎn)的后繼節(jié)點(diǎn)
            //先看被刪的節(jié)點(diǎn)與替換的節(jié)點(diǎn)是否為緊挨在一起
            BinaryNode s = p.right;
            BinaryNode sParent = p;
            while (s.left != null) {
                sParent = s;
                s = s.left;
            }
            if (sParent != p) {
                //說明沒有緊挨在一起，則需要將替換節(jié)點(diǎn)的右子樹進(jìn)行處理
                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;
        }
    }

    //使用遞歸實(shí)現(xiàn)刪除關(guān)鍵字節(jié)點(diǎn)
    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;
    }
    //改進(jìn)思路:遍歷方向進(jìn)行調(diào)整，先從右子樹開始，再訪問根節(jié)點(diǎn)，最后才到左子樹
    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;
    }

}

總結(jié)

到此這篇關(guān)于Java數(shù)據(jù)結(jié)構(gòu)篇之實(shí)現(xiàn)二叉搜索樹的核心方法的文章就介紹到這了,更多相關(guān)Java實(shí)現(xiàn)二叉搜索樹內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

相關(guān)文章

最新評論