Java數(shù)據(jù)結(jié)構(gòu)之二叉查找樹的實現(xiàn)

更新時間：2022年03月28日 15:49:13 作者：gonghr

二叉查找樹（亦稱二叉搜索樹、二叉排序樹）是一棵二叉樹，且各結(jié)點關鍵詞互異，其中根序列按其關鍵詞遞增排列。本文將通過示例詳細講解二叉查找樹，感興趣的可以了解一下

定義

二叉查找樹（亦稱二叉搜索樹、二叉排序樹）是一棵二叉樹，且各結(jié)點關鍵詞互異，其中根序列按其關鍵詞遞增排列。

等價描述：二叉查找樹中任一結(jié)點 P，其左子樹中結(jié)點的關鍵詞都小于 P 的關鍵詞，右子樹中結(jié)點的關鍵詞都大于 P 的關鍵詞，且結(jié)點 P 的左右子樹也都是二叉查找樹

節(jié)點結(jié)構(gòu)

:one: key：關鍵字的值

:two: value：關鍵字的存儲信息

:three: left：左節(jié)點的引用

:four: right：右節(jié)點的引用

class BSTNode<K extends Comparable<K>,V>{
    public K key;
    public V value;

    public BSTNode<K,V> left;
    public BSTNode<K,V> right;
}

為了代碼簡潔，本文不考慮屬性的封裝，一律設為 public

查找算法

思想：利用二叉查找樹的特性，左子樹值小于根節(jié)點值，右子樹值大于根節(jié)點值，從根節(jié)點開始搜索

如果目標值等于某節(jié)點值，返回該節(jié)點
如果目標值小于某節(jié)點值，搜索該節(jié)點的左子樹
如果目標值大于某節(jié)點值，搜索該節(jié)點的右子樹

:one: 遞歸版本

public BSTNode<K, V> searchByRecursion(K key) {
        return searchByRecursion(root, key);
    }

    private BSTNode<K, V> searchByRecursion(BSTNode<K, V> t, K key) {
        if (t == null || t.key == key) return t;
        else if (key.compareTo(t.key) < 0) return searchByRecursion(t.left, key);
        else return searchByRecursion(t.right, key);
    }

:two: 迭代版本

public BSTNode<K,V> searchByIteration(K key) {
        BSTNode<K,V> p = this.root;
        while(p != null) {
            if(key.compareTo(p.key) < 0) p = p.left;
            else if(key.compareTo(p.key) > 0) p = p.right;
            else return p;
        }
        return null;
    }

插入算法

在以 t 為根的二叉查找樹中插入關鍵詞為 key 的結(jié)點
在 t 中查找 key ，在查找失敗處插入

:one: 遞歸版本

public void insertByRecursion(K key, V value) {
        this.root = insertByRecursion(root, key, value);
    }

    private BSTNode<K, V> insertByRecursion(BSTNode<K, V> t, K key, V value) {
        if (t == null) {
            return new BSTNode<>(key, value);
        } 
        else if (key.compareTo(t.key) < 0) t.left = insertByRecursion(t.left, key, value);
        else if (key.compareTo(t.key) > 0) t.right = insertByRecursion(t.right, key, value);
        else {
            t.value = value;  // 如果二叉查找樹中已經(jīng)存在關鍵字，則替換該結(jié)點的值
        }
        return t;
    }

:two: 迭代版本

public void insertByIteration(K key, V value) {
        BSTNode<K, V> p = root;
        if (p == null) {
            root = new BSTNode<>(key, value);
            return;
        }
        BSTNode<K, V> pre = null;
        while (p != null) {
            pre = p;
            if (key.compareTo(p.key) < 0) p = p.left;
            else if (key.compareTo(p.key) > 0) p = p.right;
            else {
                p.value = value;    // 如果二叉查找樹中已經(jīng)存在關鍵字，則替換該結(jié)點的值
                return;
            }
        }
        if(key.compareTo(pre.key) < 0) {
            pre.left = new BSTNode<>(key, value);
        } else {
            pre.right = new BSTNode<>(key, value);
        }
    }

刪除算法

在以 t 為根的二叉查找樹中刪除關鍵詞值為 key 的結(jié)點

在 t 中找到關鍵詞為 key 的結(jié)點，分三種情況刪除 key

1.若 key 是葉子節(jié)點，則直接刪除

2.若 key 只有一棵子樹，則子承父業(yè)

3.若 key 既有左子樹也有右子樹，則找到 key 的后繼結(jié)點，替換 key 和后繼節(jié)點的值，然后刪除后繼節(jié)點（后繼節(jié)點只有一棵子樹，轉(zhuǎn)化為第二種情況）。

后繼結(jié)點是當前結(jié)點的右子樹的最左結(jié)點，如果右子樹沒有左子樹，則后繼節(jié)點就是右子樹的根節(jié)點。

public void removeByRecursion(K key) {
        this.root = removeByRecursion(root, key);
    }
    private BSTNode<K, V> removeByRecursion(BSTNode<K, V> t, K key) {
        if(t == null) return root;
        else if(t.key.compareTo(key) < 0) t.right = removeByRecursion(t.right, key); // key大，遞歸處理右子樹
        else if(t.key.compareTo(key) > 0) t.left = removeByRecursion(t.left, key);   // key小，遞歸處理左子樹
        else {
            if(t.right == null) return t.left;  // 情況一、二一起處理
            if(t.left == null) return t.right;  // 情況一、二一起處理
            BSTNode<K, V> node = t.right;       // 情況三：右子樹沒有左子樹
            if (node.left == null) {
                node.left = t.left;
            } else {                            // 情況三：右子樹有左子樹
                BSTNode<K, V> pre = null;
                while (node.left != null) {
                    pre = node;
                    node = node.left;
                }
                t.key = node.key;
                t.value = node.value;
                pre.left = node.right;
            }
        }
        return t;
    }

完整代碼

class BSTNode<K extends Comparable<K>, V> {
    public K key;
    public V value;

    public BSTNode<K, V> left;
    public BSTNode<K, V> right;

    public BSTNode(K key, V value) {
        this.key = key;
        this.value = value;
    }
}

class BSTree<K extends Comparable<K>, V> {
    public BSTNode<K, V> root;

    private void inorder(BSTNode<K, V> root) {
        if (root != null) {
            inorder(root.left);
            System.out.print("(key: " + root.key + " , value: " + root.value + ") ");
            inorder(root.right);
        }
    }

    private void preorder(BSTNode<K, V> root) {
        if (root != null) {
            System.out.print("(key: " + root.key + " , value: " + root.value + ") ");
            preorder(root.left);
            preorder(root.right);
        }
    }

    private void postorder(BSTNode<K, V> root) {
        if (root != null) {
            postorder(root.left);
            postorder(root.right);
            System.out.print("(key: " + root.key + " , value: " + root.value + ") ");
        }
    }

    public void postorderTraverse() {
        System.out.print("后序遍歷：");
        postorder(root);
        System.out.println();
    }

    public void preorderTraverse() {
        System.out.print("先序遍歷：");
        preorder(root);
        System.out.println();
    }

    public void inorderTraverse() {
        System.out.print("中序遍歷：");
        inorder(root);
        System.out.println();
    }

    public BSTNode<K, V> searchByRecursion(K key) {
        return searchByRecursion(root, key);
    }

    private BSTNode<K, V> searchByRecursion(BSTNode<K, V> t, K key) {
        if (t == null || t.key == key) return t;
        else if (key.compareTo(t.key) < 0) return searchByRecursion(t.left, key);
        else return searchByRecursion(t.right, key);
    }

    public BSTNode<K, V> searchByIteration(K key) {
        BSTNode<K, V> p = this.root;
        while (p != null) {
            if (key.compareTo(p.key) < 0) p = p.left;
            else if (key.compareTo(p.key) > 0) p = p.right;
            else return p;
        }
        return null;
    }

    public void insertByRecursion(K key, V value) {
        this.root = insertByRecursion(root, key, value);
    }

    private BSTNode<K, V> insertByRecursion(BSTNode<K, V> t, K key, V value) {
        if (t == null) {
            return new BSTNode<>(key, value);
        } else if (key.compareTo(t.key) < 0) t.left = insertByRecursion(t.left, key, value);
        else if (key.compareTo(t.key) > 0) t.right = insertByRecursion(t.right, key, value);
        else {
            t.value = value;
        }
        return t;
    }

    public void insertByIteration(K key, V value) {
        BSTNode<K, V> p = root;
        if (p == null) {
            root = new BSTNode<>(key, value);
            return;
        }
        BSTNode<K, V> pre = null;
        while (p != null) {
            pre = p;
            if (key.compareTo(p.key) < 0) p = p.left;
            else if (key.compareTo(p.key) > 0) p = p.right;
            else {
                p.value = value;    // 如果二叉查找樹中已經(jīng)存在關鍵字，則替換該結(jié)點的值
                return;
            }
        }
        if (key.compareTo(pre.key) < 0) {
            pre.left = new BSTNode<>(key, value);
        } else {
            pre.right = new BSTNode<>(key, value);
        }
    }

    public void removeByRecursion(K key) {
        this.root = removeByRecursion(root, key);
    }
    private BSTNode<K, V> removeByRecursion(BSTNode<K, V> t, K key) {
        if(t == null) return root;
        else if(t.key.compareTo(key) < 0) t.right = removeByRecursion(t.right, key); // key大，遞歸處理右子樹
        else if(t.key.compareTo(key) > 0) t.left = removeByRecursion(t.left, key);   // key小，遞歸處理左子樹
        else {
            if(t.right == null) return t.left;  // 情況一、二一起處理
            if(t.left == null) return t.right;  // 情況一、二一起處理
            BSTNode<K, V> node = t.right;       // 情況三：右子樹沒有左子樹
            if (node.left == null) {
                node.left = t.left;
            } else {                            // 情況三：右子樹有左子樹
                BSTNode<K, V> pre = null;
                while (node.left != null) {
                    pre = node;
                    node = node.left;
                }
                t.key = node.key;
                t.value = node.value;
                pre.left = node.right;
            }
        }
        return t;
    }
}

:bug: 方法測試：

public class Main {
    public static void main(String[] args) {
        BSTree<Integer, Integer> tree = new BSTree<>();
//        tree.insertByRecursion(1, 1);
//        tree.insertByRecursion(5, 1);
//        tree.insertByRecursion(2, 1);
//        tree.insertByRecursion(4, 1);
//        tree.insertByRecursion(3, 1);
//        tree.insertByRecursion(1, 2);
        tree.insertByIteration(1, 1);
        tree.insertByIteration(5, 1);
        tree.insertByIteration(2, 1);
        tree.insertByIteration(4, 1);
        tree.insertByIteration(3, 1);
        tree.insertByIteration(1, 5);
        tree.removeByRecursion(4);
        tree.inorderTraverse();
        tree.postorderTraverse();
        tree.preorderTraverse();
        BSTNode<Integer, Integer> node = tree.searchByIteration(1);
        System.out.println(node.key + " " + node.value);
    }
}

中序遍歷：(key: 1 , value: 5) (key: 2 , value: 1) (key: 3 , value: 1) (key: 5 , value: 1)
后序遍歷：(key: 3 , value: 1) (key: 2 , value: 1) (key: 5 , value: 1) (key: 1 , value: 5)
先序遍歷：(key: 1 , value: 5) (key: 5 , value: 1) (key: 2 , value: 1) (key: 3 , value: 1)
1 5

以上就是Java數(shù)據(jù)結(jié)構(gòu)之二叉查找樹的實現(xiàn)的詳細內(nèi)容，更多關于Java二叉查找樹的資料請關注腳本之家其它相關文章！

您可能感興趣的文章:

詳解java 中的CAS與ABA
這篇文章主要介紹了java 中的CAS與ABA的相關資料，幫助大家更好的理解和學習使用Java，感興趣的朋友可以了解下
2021-05-05
dependencies導致的Maven依賴出錯包紅問題解決方法
多模塊和分布式開發(fā)一般都是有專門的的dependencies來進行jar包的版本依賴問題，本文主要介紹了dependencies導致的Maven依賴出錯包紅問題解決方法，具有一定的參考價值，感興趣的可以了解一下
2022-05-05
spring項目如何配置多數(shù)據(jù)源(已上生產(chǎn),親測有效)
這篇文章主要介紹了spring項目如何配置多數(shù)據(jù)源(已上生產(chǎn),親測有效),具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教
2023-12-12
Spring?Security自定義認證邏輯實例詳解
這篇文章主要給大家介紹了關于Spring?Security自定義認證邏輯的相關資料,文中通過實例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下
2022-01-01
Java詳細分析連接數(shù)據(jù)庫的流程
Java數(shù)據(jù)庫連接，JDBC是Java語言中用來規(guī)范客戶端程序如何來訪問數(shù)據(jù)庫的應用程序接口，提供了諸如查詢和更新數(shù)據(jù)庫中數(shù)據(jù)的方法。JDBC也是Sun Microsystems的商標。我們通常說的JDBC是面向關系型數(shù)據(jù)庫的
2022-05-05
Java你不了解的大數(shù)型BigInteger與BigDecimal類
這篇文章主要介紹了Java 處理超大數(shù)類型之BigInteger與BigDecimal案例詳解,本篇文章通過簡要的案例,講解了該項技術(shù)的了解與使用,以下就是詳細內(nèi)容,需要的朋友可以參考下
2022-05-05
restTemplate實現(xiàn)跨服務API調(diào)用方式
這篇文章主要介紹了restTemplate實現(xiàn)跨服務API調(diào)用方式，具有很好的參考價值，希望對大家有所幫助。
2023-07-07
Spring Boot實現(xiàn)跨域訪問實現(xiàn)代碼
本文通過實例代碼給大家介紹了Spring Boot實現(xiàn)跨域訪問的知識，然后在文中給大家介紹了spring boot 服務器端設置允許跨域訪問的方法，感興趣的朋友一起看看吧
2017-07-07
Java調(diào)用python的方法（jython）
這篇文章主要介紹了Java調(diào)用python的方法（jython），小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧
2017-06-06
java獲取json中的全部鍵值對實例
下面小編就為大家分享一篇java獲取json中的全部鍵值對實例，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧
2018-03-03