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

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

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

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

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

文章目录

        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 < 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<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 实现二叉搜索树 - 查找范围大于关键字的节点值 greater(int key)

        具体实现思路:利用中序遍历,来遍历每一个节点的 key ,若大于 key 的节点,直接放到数组容器中。

代码如下:

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

该方法的改进:遍历方向进行调整,先从右子树开始,再访问根节点,最后才到左子树。因此只要小于 key 的关键字节点,直接退出循环

代码如下:

//改进思路:遍历方向进行调整,先从右子树开始,再访问根节点,最后才到左子树 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 实现二叉搜索树 - 查找范围大于 k1 且小于 k2 关键字的节点值 between(int k1, int k2)

        实现思路跟以上的思路没有什么区别,唯一需要注意的是,当前节点的 key > k2 则可以退出循环了。

代码如下:

//找到 >= 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 实现二叉搜索树核心方法的完整代码

实现接口代码:

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<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; } //改进思路:遍历方向进行调整,先从右子树开始,再访问根节点,最后才到左子树 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 数据结构篇-实现二叉搜索树的核心方法,第4张

 

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/sjk/13518061.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2023-12-20
下一篇 2023-12-24

发表评论

登录后才能评论

评论列表(0条)

保存