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

Posted on by hackdl

博客主页：【小扳_-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 {

    /**
     *查找 key 对应的 value
     */
    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 。按这样的规则一直循环下去，直到 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

若 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

代码如下：

    @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

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

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

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 节点，同理，也是细分为以上描述的四种情况。

代码如下：

    //使用递归实现删除关键字节点
    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

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

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

代码如下：

    //找  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

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 且 = 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) {
                    break;
                }
                p = pop.right;
            }
        }
            return result;
    }

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

实现接口代码：

import java.util.ArrayList;

import java.util.List;
im服务器托管网port 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.left;
            } else if (p.key  key) {
                sParent = p;
                p = p.left;
            } else if (p.key  key) {
                p = p.left;
            } else if (p.key  key) {
                parent = p;
                p = p.left;
            } else if (p.key  key) {
            node.left = deleteRecursion(node.left,key);
            return node;
        } else if (node.key  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 的所有 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 且 = 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) {
                    break;
                }
                p = pop.right;
            }
        }
            return result;
    }

}

服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net

服务器托管，北京服务器托管，服务器租用，机房机柜带宽租用

服务器托管

咨询：董先生

电话13051898268 QQ/微信93663045！

上一篇:
下一篇: