iis服务器助手广告

扫码关注官方微信

扫码下载APP
返回顶部
首页 > 资讯 > 后端开发 > JAVA >Java 数据结构篇-实现二叉搜索树的核心方法
  • 110

0
分享到

Java 数据结构篇-实现二叉搜索树的核心方法

数据结构java链表算法 2024-01-21 15:01:31 110人浏览 薄情痞子
摘要

🔥博客主页： 【小扳_-CSDN博客】 ❤感谢大家点赞👍收藏⭐评论✍  文章目录         1.0 二叉搜索树的概述         2.0 二叉搜索树的成员变量及其构造方法        

🔥博客主页： 【小扳_-CSDN博客】
❤感谢大家点赞👍收藏⭐评论✍ 

文章目录

        1.0 二叉搜索树的概述

        2.0 二叉搜索树的成员变量及其构造方法

        3.0 实现二叉树的核心接口

        3.1 实现二叉搜索树 - 获取值 get(int key)

        3.2 实现二叉搜索树 - 获取最小的关键字 min(BinaryNode node)

        3.3 实现二叉搜索树 - 获取最大的关键字 max(BinaryNode node)

        3.4 实现二叉搜索树 - 增、更新 put( int key, Object value)

        3.5 实现二叉搜索树 - 查找关键字的后驱节点 successor(int key)

        3.6 实现二叉搜索树 - 查找关键字的前驱节点 predecessor(int key)

        3.7 实现二叉搜索树 - 删除关键字节点 delete(int key)

        3.8 实现二叉搜索树 - 查找范围小于关键字的节点值 less(int key)

        3.9 实现二叉搜索树 - 查找范围大于关键字的节点值 greater(int key)

        4.0 实现二叉搜索树 - 查找范围大于 k1 且小于 k2 关键字的节点值 between(int k1, int k2)

        5.0 实现二叉搜索树核心方法的完整代码

        1.0 二叉搜索树的概述

        二叉搜索树是一种数据结构，用于存储数据并支持快速的插入、删除和搜索操作。它是一种树形结构。

        它具有以下特点：

                - 每个节点最多有两个子节点，分别称为左子节点和右子节点。

                - 对于每个节点，其左子节点的值小于该节点的值，右子节点的值大于该节点的值。

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

        由于其特性，二叉搜索树在插入、删除和搜索操作上具有较高的效率。在平均情况下，这些操作的时间复杂度为 O(log n)，其中 n 为树中节点的数量。然而，如果树的结构不平衡，最坏情况下这些操作的时间复杂度可能会达到 O(n)。由于其高效的搜索特性，二叉搜索树常被用于实现关联数组和集合等数据结构。然而，为了避免树的结构不平衡导致性能下降，人们也发展了平衡二叉搜索树（如红黑树、AVL树）等变种。

        2.0 二叉搜索树的成员变量及其构造方法

        外部类成员变量有：根节点、节点类（内部类）。

        外部类构造方法：默认的构造方法，对外公开二叉搜索树的核心方法。

        节点类的成员变量有：

                - key 关键字：相对比一般的二叉树，二叉搜索树可以明显提高增删查改的效率原因在于关键字，可以根据比较两个关键字的大小进行操作。

                - value 值：作用则为存放值。

                - left ：链接左节点。

                - right：链接右节点。

        节点类的构造方法：

                带两个参数的构造方法：参数为 key 、value 

                带四个参数的构造方法：参数为 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;        }    }}

        补充二叉搜索树在增、删、查、改的效率高的原因：

        二叉搜索树的高效性与其关键字的特性密切相关。二叉搜索树的关键特性是，对于每个节点，其左子节点的值小于该节点的值，右子节点的值大于该节点的值。这种特性使得在二叉搜索树中进行搜索、插入和删除操作时，可以通过比较关键字的大小来快速定位目标节点，从而实现高效的操作。在平均情况下，这些操作的时间复杂度为 O(log n)，其中 n 为树中节点的数量。因此，关键字的有序性是二叉搜索树能够实现高效操作的关键原因之一。

        3.0 实现二叉树的核心接口

​public interface BinarySearchTreeInterface {        Object get(int key);        Object min();        Object max();        void put(int key, Object value);        Object successor(int key);        Object predecessor(int key);        Object delete(int key);}​

        3.1 实现二叉搜索树 - 获取值 get(int key)

        实现思路为：从根节点开始，先判断当前的节点 p.key 与 key 进行比较，若 p.key > key，则向左子树下潜 p = p.left ；若 p.key < key ，则向右子树下潜 p = p.right ；若 p.key == key ，则找到到了关键字，返回该节点的值 p.value 。按这样的规则一直循环下去，直到 p == null 退出循环，则说明没有找到对应的节点，则返回 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 ，则不需要再进行下去了，直接结束。

        3.2 实现二叉搜索树 - 获取最小的关键字 min(BinaryNode node)

        实现思路：在某一个树中，需要得到最小的关键字，由根据数据结构的特点，最小的关键字在数的最左边，简单来说：一直向左子树遍历下去，直到 p.left == null 时，则该 p 节点就是最小的关键字了。然后找到了最小的节点，返回该节点的值即可。

代码如下：

非递归实现：

    @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;    }

递归实现：

    //使用递归实现找最小关键字    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 实现二叉搜索树 - 获取最大的关键字 max(BinaryNode node)

        实现思路为：在某一个树中，需要得到最大的关键字，由根据数据结构的特点，最大的关键字在数的最右边，简单来说：一直向右子树遍历下去，直到 p.right == null 时，则该 p 节点就是最大的关键字了。然后找到了最大的节点，返回该节点的值即可。

代码如下：

非递归实现：

    @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;    }

递归实现：

    //使用递归实现找最大关键字    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 实现二叉搜索树 - 增、更新 put( int key, Object value)

        实现思路为：在二叉搜索树中先试着查找是否存在与 key 对应的节点 p.key 。若找到了，则为更新该值 p.value = value 即可。若找不到，则需要新增该关键字节点。

        具体来分析如何新增关键字，先定义 BinaryNode parent 、 BinaryNode p，p 指针在去比较 key 之前，先让 parent 指向 p 。最后循环结束后， p == null ，对于 parent 来说，此时正指着 p 节点的双亲节点。 接着创建一个新的节点，BinaryNode newNode = new BinaryNode(key, value) ，则此时还需要考虑的是，该新的节点该连接到 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;            }        }        //该树没有该关键字，因此需要新建节点对象        BinaryNode newNode = new BinaryNode(key,value);        if (newNode.key < parent.key) {            parent.left = newNode;        }else {            parent.right = newNode;        }    }

        3.5 实现二叉搜索树 - 查找关键字的后驱节点 successor(int key)

        具体实现思路为：先遍历找到该关键字的节点，若找不到，则返回 null ；若找到了，判断以下的两种情况，第一种情况：该节点有右子树，则该关键字的后驱为右子树的最小关键字；第二种情况：该节点没有右子树，则该关键字的后驱为从右向左而来的祖宗节点。最后返回该后驱节点的值 

代码如下：

    @Override    public Object successor(int key) {        if (root == null) {            return null;        }        //先找到该关键字节点        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;            }        }        //没有找到关键字的情况        if (p == null) {            return null;        }        //情况一:该节点存在右子树,则该后继为右子树的最小关键字        if (p.right != null) {            return min(p.right);        }        //情况二:该节点不存在右子树，那么该后继就需要到祖宗从右向左的节点        if (sParent == null) {            //可能不存在后继节点,比如最大关键字的节点就没有后继节点了            return null;        }        return sParent.value;    }

        3.6 实现二叉搜索树 - 查找关键字的前驱节点 predecessor(int key)

        具体实现思路为：先对该二叉树进行遍历寻找 key 的节点，若遍历结束还没找到，则返回 null ；若找到了，需要判断以下两种情况：

        第一种情况：该节点有左子树，则该前驱节点为该左子树的最大关键字节点。

        第二种情况：该节点没有左子树，则该前驱节点为从左向右而来的祖宗节点。

        最后返回该前驱节点的值。

代码如下：

    @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;        }        //情况一:存在左子树，则该前任就为左子树的最大关键字节点        if (p.left != null) {            return max(p.left);        }        //情况二:不存在左子树，则该前任为从祖宗自左向右而来的节点        if (sParent == null) {            return null;        }        return sParent.value;    }

        3.7 实现二叉搜索树 - 删除关键字节点 delete(int key)

        具体实现思路为：先遍历二叉树，查找该关键字节点。若遍历结束了还没有找到，则返回 null ；若找到了，则需要以下四种情况：

        第一种情况：找到该删除的节点只有左子树。则直接让该左子树 "托付" 给删除节点的双亲节点，这就删除了该节点了。至于左子树是链接到双亲节点的左边还有右边这个问题，根据该数据结构的特点，由该删除节点来决定。若删除的节点之前是链接该双亲节点的左边，则左子树也是链接到该双亲节点的左边；若删除的节点之前是链接该双亲节点的右边，则左子树也是链接到该双亲节点的右边。

        第二种情况：找到该删除的节点只有右子树。则直接让该右子树 "托付" 给删除节点的双亲节点，这就删除了该节点了。至于右子树是链接到双亲节点的左边还有右边这个问题，根据该数据结构的特点，由该删除节点来决定。若删除的节点之前是链接该双亲节点的左边，则右子树也是链接到该双亲节点的左边；若删除的节点之前是链接该双亲节点的右边，则右子树也是链接到该双亲节点的右边。

        第三种情况：找到该删除节点都没有左右子树。该情况可以归并到以上两种情况的任意一种处理均可。

        第四种情况：找到该删除节点都有左右子树。分两步：第一步，先找后继节点来替换删除节点，找该后继节点直接到删除节点的右子树中找最小的关键字节点即可。第二步，需要先将后继节点的右子树处理好，需要将该右子树交给替换节点的双亲节点链接。还需要判断两种情况：第一种情况，若删除节点与替换节点是紧挨着的，对替换节点的右子树无需要求，只对左子树重新赋值；若删除节点与替换节点不是紧挨着的关系，对替换节点的左右子树都要重新赋值。

代码如下：

    @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;            }        }        //没有找到该关键字的节点        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 {            //情况四:有左右子树            //替换节点采用删除节点的后继节点            //先看被删的节点与替换的节点是否为紧挨在一起            BinaryNode s = p.right;            BinaryNode sParent = p;            while (s.left != null) {                sParent = s;                s = s.left;            }            if (sParent != p) {                //说明没有紧挨在一起，则需要将替换节点的右子树进行处理                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;        }    }

        为了方便，将删除节点与替换节点之间的替换操作单独成一个方法出来。

        递归实现删除关键字 key 节点，同理，也是细分为以上描述的四种情况。

代码如下：

    //使用递归实现删除关键字节点    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 实现二叉搜索树 - 查找范围小于关键字的节点值 less(int key)

        具体实现思路为：利用中序遍历，来遍历每一个节点的 key ，若小于 key 的节点，直接放到数组容器中；若大于 key 的，可以直接退出循环。最后返回该数组容器即可。

代码如下：

    //找 < key 的所有 value    public List less(int key) {        if (root == null) {            return null;        }        ArrayList result = new ArrayList<>();        BinaryNode p = root;        Stack 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 实现二叉搜索树 - 查找范围大于关键字的节点值 greater(int key)
 
        具体实现思路：利用中序遍历，来遍历每一个节点的 key ，若大于 key 的节点，直接放到数组容器中。
 
代码如下：
 
  
    //找 > key 的所有 value    public List greater(int key) {        if (root == null) {            return null;        }        ArrayList result = new ArrayList<>();        Stack 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;    }    
该方法的改进：遍历方向进行调整，先从右子树开始，再访问根节点，最后才到左子树。因此只要小于 key 的关键字节点，直接退出循环。
 
代码如下：
 
  
    //改进思路:遍历方向进行调整，先从右子树开始，再访问根节点，最后才到左子树    public List greater1(int key) {        if (root == null) {            return null;        }        ArrayList result = new ArrayList<>();        Stack 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 实现二叉搜索树 - 查找范围大于 k1 且小于 k2 关键字的节点值 between(int k1, int k2)
 
        实现思路跟以上的思路没有什么区别，唯一需要注意的是，当前节点的 key > k2 则可以退出循环了。
 
代码如下：
 
  
//找到 >= k1 且 =< k2 的所有value    public List between(int k1, int k2) {        if (root == null) {            return null;        }        ArrayList result = new ArrayList<>();        Stack 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 实现二叉搜索树核心方法的完整代码
 
  
实现接口代码：
  
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;    }    //使用递归实现找最小关键字    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;    }    //使用递归实现找最大关键字    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;            }        }        //该树没有该关键字，因此需要新建节点对象        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;        }        //先找到该关键字节点        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;            }        }        //没有找到关键字的情况        if (p == null) {            return null;        }        //情况一:该节点存在右子树,则该后继为右子树的最小关键字        if (p.right != null) {            return min(p.right);        }        //情况二:该节点不存在右子树，那么该后继就需要到祖宗从右向左的节点        if (sParent == null) {            //可能不存在后继节点,比如最大关键字的节点就没有后继节点了            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;        }        //情况一:存在左子树，则该前任就为左子树的最大关键字节点        if (p.left != null) {            return max(p.left);        }        //情况二:不存在左子树，则该前任为从祖宗自左向右而来的节点        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;            }        }        //没有找到该关键字的节点        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 {            //情况四:有左右子树            //替换节点采用删除节点的后继节点            //先看被删的节点与替换的节点是否为紧挨在一起            BinaryNode s = p.right;            BinaryNode sParent = p;            while (s.left != null) {                sParent = s;                s = s.left;            }            if (sParent != p) {                //说明没有紧挨在一起，则需要将替换节点的右子树进行处理                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;        }    }    //使用递归实现删除关键字节点    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 less(int key) {        if (root == null) {            return null;        }        ArrayList result = new ArrayList<>();        BinaryNode p = root;        Stack 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 greater(int key) {        if (root == null) {            return null;        }        ArrayList result = new ArrayList<>();        Stack 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;    }    //改进思路:遍历方向进行调整，先从右子树开始，再访问根节点，最后才到左子树    public List greater1(int key) {        if (root == null) {            return null;        }        ArrayList result = new ArrayList<>();        Stack 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 between(int k1, int k2) {        if (root == null) {            return null;        }        ArrayList result = new ArrayList<>();        Stack 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;    }}    
 
 
来源地址：https://blog.csdn.net/Tingfeng__/article/details/135088389




点击免费下载>>软考高级考试备考技巧/历年真题/备考精华资料








--结束END--


 本文标题: Java 数据结构篇-实现二叉搜索树的核心方法


 本文链接: https://www.lsjlt.com/news/556117.html(转载时请注明来源链接)


有问题或投稿请发送至:
邮箱/279061341@qq.com    QQ/279061341














本篇文章演示代码以及资料文档资料下载


下载Word文档到电脑，方便收藏和打印～






下载Word文档







去做题








猜你喜欢







    

  • 

    

    

    Java 数据结构篇-实现二叉搜索树的核心方法
    
 
      🔥博客主页： 【小扳_-CSDN博客】 ❤感谢大家点赞👍收藏⭐评论✍     文章目录         1.0 二叉搜索树的概述         2.0 二叉搜索树的成员变量及其构造方法         ...

    

     

    

    

    

    

    99+
    

    2024-01-21
    

    
数据结构
java
链表
算法

    

    

    

    

    • 

  • 

    

    

    【Java 数据结构】实现一个二叉搜索树
    
 
      目录  1、认识二叉搜索树 2、实现一个二叉搜索树 2.1 成员变量 2.2 insert 方法 2.3 search 方法  2.4 remove 方法(重点) 3、二叉搜索树总结   1、认识二叉搜索树 从字面上来看，它只比二叉树多...

    

     

    

    

    

    

    99+
    

    2023-09-02
    

    
数据结构
算法
二叉搜索树

    

    

    

    

    • 

  • 

    

    

    java数据结构之搜索二叉树
    
 
    
                            本文实例为大家分享了java数据结构之搜索二叉树的具体代码，供大家参考，具体内容如下
搜索二叉树的定义是：在一个二叉树上，左节点一定比父节点小，右节点一定比父节点大，其他定义跟二叉树...

    

     

    

    

    

    

    99+
    

    2024-04-02
    

    

    

    

    

    

    • 

  • 

    

    

    Java 数据结构篇-实现 AVL 树的核心方法
    
 
      🔥博客主页： 【小扳_-CSDN博客】 ❤感谢大家点赞👍收藏⭐评论✍     文章目录         1.0 AVL 树的说明         2.0 AVL 树的成员变量及其构造方法         ...

    

     

    

    

    

    

    99+
    

    2024-01-21
    

    
数据结构
算法
java

    

    

    

    

    • 

  • 

    

    

    C++数据结构之搜索二叉树的实现
    
 
    
                            目录零.前言1.概念2.作用3.迭代实现(1)查找(2)插入(3)删除4.递归实现(1)查找(2)插入(3)删除5.key/value模型的应用(1)对应查找(2)判断出现次数6.总...

    

     

    

    

    

    

    99+
    

    2024-04-02
    

    

    

    

    

    

    • 

  • 

    

    

    Java数据结构之二叉搜索树详解
    
 
    
                            目录前言性质实现节点结构初始化插入节点查找节点删除节点最后前言
今天leetcode的每日一题450是关于删除二叉搜索树节点的，题目要求删除指定值的节点，并且需要保证二叉搜索树性质不...

    

     

    

    

    

    

    99+
    

    2024-04-02
    

    

    

    

    

    

    • 

  • 

    

    

    Java数据结构之二叉搜索树实例分析
    
 
    这篇文章主要介绍“Java数据结构之二叉搜索树实例分析”，在日常操作中，相信很多人在Java数据结构之二叉搜索树实例分析问题上存在疑惑，小编查阅了各式资料，整理出简单好用的操作方法，希望对大家解答”Java数据结构之二叉搜索树实例分析”的疑...

    

     

    

    

    

    

    99+
    

    2023-06-30
    

    

    

    

    

    

    • 

  • 

    

    

    C++数据结构之二叉搜索树的实现详解
    
 
    
                            目录前言介绍实现节点的实现二叉搜索树的查找二叉搜索树的插入二叉搜索树的删除总结前言
今天我们来学一个新的数据结构：二叉搜索树。
介绍
二叉搜索树也称作二叉排序树，它具有以下性质：
非...

    

     

    

    

    

    

    99+
    

    2024-04-02
    

    

    

    

    

    

    • 

  • 

    

    

    Java数据结构超详细分析二叉搜索树
    
 
    
                            目录1.搜索树的概念2.二叉搜索树的简单实现2.1查找2.2插入2.3删除2.4修改3.二叉搜索树的性能
1.搜索树的概念
二叉搜索树是一种特殊的二叉树，又称二叉查找树，二叉排序树，...

    

     

    

    

    

    

    99+
    

    2024-04-02
    

    

    

    

    

    

    • 

  • 

    

    

    Java数据结构之线索化二叉树的实现
    
 
    
                            目录1.线索化二叉树的介绍2.线索化二叉树的基本特点3.线索化二叉树的应用案例4.前序线索化二叉树、遍历5.后序线索化二叉树1.线索化二叉树的介绍
将数列 {1, 3, 6, 8, ...

    

     

    

    

    

    

    99+
    

    2024-04-02
    

    

    

    

    

    

    • 

  • 

    

    

    C++详解数据结构中的搜索二叉树
    
 
    
                            目录定义查找某个元素构造搜索二叉树往搜索二叉树中插入元素搜索二叉树删除节点定义
搜索二叉树，也称有序二叉树，排序二叉树，是指一棵空树或者具有下列性质的二叉树：
1、若任意节点的左子树...

    

     

    

    

    

    

    99+
    

    2024-04-02
    

    

    

    

    

    

    • 

  • 

    

    

    C++数据结构二叉搜索树的实现应用与分析
    
 
    
                            目录概念二叉搜索树的实现基本框架二叉搜索树的插入二叉搜索树的查找二叉搜索树的删除（重点）二叉搜索树的应用二叉树性能分析总结⭐️博客代码已上传至gitee：https://gitee....

    

     

    

    

    

    

    99+
    

    2024-04-02
    

    

    

    

    

    

    • 

  • 

    

    

    Java数据结构之线索化二叉树怎么实现
    
 
    这篇文章主要介绍“Java数据结构之线索化二叉树怎么实现”，在日常操作中，相信很多人在Java数据结构之线索化二叉树怎么实现问题上存在疑惑，小编查阅了各式资料，整理出简单好用的操作方法，希望对大家解答”Java数据结构之线索化二叉树怎么实现...

    

     

    

    

    

    

    99+
    

    2023-06-30
    

    

    

    

    

    

    • 

  • 

    

    

    python实现二叉搜索树的四种方法
    
 
    
                            目录树的介绍二叉搜索树列举几种Python中几种常见的实现方式：1.使用类和递归函数实现2.使用列表实现3.使用字典实现4.使用堆栈实现树的介绍
树不同于链表或哈希表，是一种非线性数...

    

     

    

    

    

    

    99+
    

    2023-05-15
    

    
python
二叉搜索树

    

    

    

    

    • 

  • 

    

    

    Java数据结构之二叉查找树的实现
    
 
    
                            目录定义节点结构查找算法插入算法删除算法完整代码定义
二叉查找树（亦称二叉搜索树、二叉排序树）是一棵二叉树，且各结点关键词互异，其中根序列按其关键词递增排列。
等价描述：二叉查找树中...

    

     

    

    

    

    

    99+
    

    2024-04-02
    

    

    

    

    

    

    • 

  • 

    

    

    Java数据结构之二叉排序树的实现
    
 
    
                            目录1 二叉排序树的概述2 二叉排序树的构建2.1 类架构2.2 查找的方法2.3 插入的方法2.4 查找最大值和最小值2.5 删除的方法3 二叉排序树的总结1 二叉排序树的概述
本...

    

     

    

    

    

    

    99+
    

    2024-04-02
    

    

    

    

    

    

    • 

  • 

    

    

    Java二叉搜索树与数组查找的方法
    
 
    本篇内容介绍了“Java二叉搜索树与数组查找的方法”的有关知识，在实际案例的操作过程中，不少人都会遇到这样的困境，接下来就让小编带领大家学习一下如何处理这些情况吧！希望大家仔细阅读，能够学有所成！题目一 解法class ...

    

     

    

    

    

    

    99+
    

    2023-06-29
    

    

    

    

    

    

    • 

  • 

    

    

    python实现二叉搜索树的方法有哪些
    
 
    这篇文章主要介绍“python实现二叉搜索树的方法有哪些”，在日常操作中，相信很多人在python实现二叉搜索树的方法有哪些问题上存在疑惑，小编查阅了各式资料，整理出简单好用的操作方法，希望对大家解答”python实现二叉搜索树的方法有哪些...

    

     

    

    

    

    

    99+
    

    2023-07-06
    

    

    

    

    

    

    • 

  • 

    

    

    C语言数据结构系列篇二叉树的概念及满二叉树与完全二叉树
    
 
    
                            
 链接：C语言数据结构系列之树的概念结构和常见表示方法
0x00 概念
 定义：二叉树既然叫二叉树，顾名思义即度最大为2的树称为二叉树。 它的度可以为 1 也可...

    

     

    

    

    

    

    99+
    

    2024-04-02
    

    

    

    

    

    

    • 

  • 

    

    

    Java数据结构之平衡二叉树的实现详解
    
 
    
                            目录定义结点结构查找算法插入算法LL 型RR 型LR 型RL 型插入方法删除算法概述实例分析代码完整代码定义

动机：二叉查找树的操作实践复杂度由树高度决定，所以希望控制树高，左右子...

    

     

    

    

    

    

    99+
    

    2024-04-02
    

    

    

    

    

    

    • 














软考高级职称资格查询









iis服务器助手广告





软考职称历年真题下载











软考职称资料下载











热门wiki
















近期文章
















推荐阅读
















热门问答















热门标签





















        

            

                

                    

                    
编程网，编程工程师的家园，是目前国内优秀的开源技术社区之一，形成了由开源软件库、代码分享、资讯、协作翻译、讨论区和博客等几大频道内容，为IT开发者提供了一个发现、使用、并交流开源技术的平台。
                    

                

                

                    

                        
                    

                    

                        
                    

                

                

                    
    
                        
  • 
                            
    
                            
    官方手机版
    
                        
    • 
                        
  • 
                            
    
                            
    微信公众号
    
                        
    • 
                        
  • 
                            
    
                            
    商务合作
    
                        
    •