Java超详细讲解排序二叉树
排序二叉树概念
- 二叉排序树(Binary Sort Tree),又称二叉查找树(Binary Search Tree),亦称二叉搜索树。是数据结构中的一类。
- 对于二叉排序树的任何一个非叶子节点, 要求左子节点的值比当前节点的值小,右子节点的值比当前节点的值大。
- 对二叉排序树进行中序遍历,结果就是按从小到大排序的。
排序二叉树类的定义
public class binarySortTree { class Node{ int value; Node left; Node right; public Node(int value){ this.value = value; } public void display(){ System.out.print(this.value + " "); } } Node root; }
添加节点
排序二叉树添加节点的十分简单,无论使用递归还是循环,思路都一样,这里我用递归的方式讲解。
- 每次添加一个节点时,判断value(添加节点的值)与root的值的大小关系: 若
root.value < value
, 说明该节点应该添加在root的右子树上。如果右子树为空,直接添加:root.right = new Node(value)
;如果右子树不为空,那么递归进右子树(令root.right为root)。 - 若
root.value >= value
, 说明该节点应该添加在root的左子树上。如果左子树为空,直接添加:root.left = new Node(value)
;如果左子树不为空,那么递归进右子树(令root.left为root)。
代码如下:
//添加节点 //此方法可以类内部方法的调用 private void add(Node root,int value){ //添加节点的值大于根节点的值,该节点添加到根节点的右子树上 if(value > root.value){ //根节点的右子树为空,直接添加 if(root.right == null){ root.right = new Node(value); } //根节点右子树不为空,递归往右子树插 else{ add(root.right,value); } } //添加节点的值小于或者等于根节点的值,该节点应该添加到左子树 else{ //左子树为空,直接添加 if(root.left == null){ root.left = new Node(value); } //左子树不为空,递归往左子树添加 else{ add(root.left, value); } } } //此方法在类内部和类外部都可以调用 public void add(int value){ //当前树为空树 if(root == null){ root = new Node(value); return; } add(root, value); }
中序遍历
因为二叉排序树中序遍历的结果就是排序好的,所以这里只提供中序遍历。
代码如下:
//中序遍历树 private void inPrevOrder(Node root){ if(root == null) return; inPrevOrder(root.left); root.display(); inPrevOrder(root.right); } public void inPrevOrder(){ System.out.print("中序遍历:"); inPrevOrder(root); }
查找节点
该方法是查找value
在二叉树中对应的位置,是为删除节点提供的方法。
/** * 通过value查找二叉树中的节点 * @param root 被查找树的根节点 * @param value 要查找的值 * @return 返回查找到的节点 */ private Node searchNode(Node root, int value){ //被查找树为null,要查找节点不存在 if(root == null) return null; //找到了,返回节点 else if(root.value == value){ return root; } //该节点不是要查找节点,继续查找 else{ //该节点的值大于value,往该节点的左子树递归查找 if(root.value > value){ return searchNode(root.left, value); } //该节点的值小于value,往该节点的右子树递归查找 else{ return searchNode(root.right, value); } } }
查找某一节点的父节点
该方法是查找二叉树中一个节点的父节点,也是为删除节点提供的方法。
/** * 查找某节点的父节点,并返回 * @param root 被查找树的根节点 * @param node 要查找的节点 * @return 返回被查找节点的父节点 */ private Node searchParentNode(Node root, Node node){ //被查找树为null或者根节点就是要查找的节点,那么要查找节点的父节点不存在 if(root == null || root == node){ return null; } else if(root.left != null && root.left == node || root.right != null && root.right == node){ return root; } else{ if(root.value > node.value){ return searchParentNode(root.left, node); } else{ return searchParentNode(root.right, node); } } }
删除节点
删除节点是排序二叉树中最麻烦的方法,因为它有很多种情况。
方法如下:
第一种情况:删除的节点是叶子节点
(1)需求先去找到要删除的结点targetNode(2)找到targetNode的父结点parent
(3)确定targetNode是parent的左子结点还是右子结点
3.1如果targetNode是parent的左子结点:parent.left = null;
3.2如果targetNode是parent的右子结点:parent.right = null;
第二种情况:删除只有一颗子树的节点
(1)需求先去找到要删除的结点targetNode(2)找到targetNode的父结点parent
(3)确定targetNode的子结点是左子结点还是右子结点
(4)确定targetNode是parent的左子结点还是右子结点
(5)如果targetNode有左子结点
5.1如果targetNode是parent的左子结点parent.left = targetNode.left;
5.2如果targetNode是parent的右子结点parent.right = targetNode.left;
(6)如果targetNode有右子结点
6.1如果targetNode是 parent 的左子结点parent.left = targetNode.right;
6.2如果targetNode是parent 的右子结点parent.right = targetNode.right
第三种情况:删除的节点有左右两个子树
(1)需求先去找到要删除的结点targetNode(2)在右子树找到最小的节点,用一个temp保存这个节点的值,然后删除这个最小节点(该最小节点一定是满足第一种情况的)
(3)targetNode.value = temp
除了以上情况,还要考虑要删除的节点就是根节点的情况(此时它的父节点为null),下面会在代码中展示,代码如下:
public void remove(int vlaue){ //找到要删除的节点 Node targetNode = searchNode(root,vlaue); //要删除节点不存在 if(targetNode == null) return; //找到要删除节点的父节点 Node targetNodeParent = searchParentNode(root,targetNode); //要删除节点为叶子节点 if(targetNode.left == null && targetNode.right == null){ //要删除的节点就是根节点 if(targetNodeParent == null){ root = null; } else{ //要删除节点是其父节点的左节点 if(targetNodeParent.left == targetNode){ targetNodeParent.left = null; } else{ targetNodeParent.right = null; } } } //要删除节点只有一个左子树 else if(targetNode.left != null && targetNode.right == null){ //要删除的节点就是根节点 if(targetNodeParent == null) { root = root.left; } //要删除节点是其父节点的左节点 else if(targetNodeParent.left != null && targetNodeParent.left.value == targetNode.value){ targetNodeParent.left = targetNode.left; } //要删除节点是其父节点的右节点 else{ targetNodeParent.right = targetNode.left; } } //要删除节点只有一个右子树 else if(targetNode.right != null && targetNode.left == null){ //要删除的节点就是根节点 if(targetNodeParent == null) { root = root.right; return; } //要删除节点是其父节点的左节点 else if(targetNodeParent.left != null && targetNodeParent.left.value == targetNode.value){ targetNodeParent.left = targetNode.right; } //要删除节点是其父节点的右节点 else{ targetNodeParent.right = targetNode.right; } } //要删除节点右左右都有节点 else{ //找到右子树最小的节点 Node minNode = targetNode.right; while(minNode.left != null){ minNode = minNode.left; } int temp = minNode.value; //找到右子树上最小节点的父节点 Node minNodeParent = searchParentNode(targetNode.right,minNode); //右子树根节点就是最小节点 if(minNodeParent == null){ targetNode.right = minNode.right; } else{ //要删除节点是其父节点的左节点 minNodeParent.left = minNode.right; } targetNode.value = temp; } }
到此这篇关于Java超详细讲解排序二叉树的文章就介绍到这了,更多相关Java排序二叉树内容请搜索猪先飞以前的文章或继续浏览下面的相关文章希望大家以后多多支持猪先飞!
原文出处:https://blog.csdn.net/m0_62969222/article/details/124972134
相关文章
- 这篇文章主要介绍了如何利用java语言实现经典《复杂迷宫》游戏,文中采用了swing技术进行了界面化处理,感兴趣的小伙伴可以动手试一试...2022-02-01
java 运行报错has been compiled by a more recent version of the Java Runtime
java 运行报错has been compiled by a more recent version of the Java Runtime (class file version 54.0)...2021-04-01- 这篇文章主要介绍了在java中获取List集合中最大的日期时间操作,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-08-15
- 这篇文章主要介绍了教你怎么用Java获取国家法定节假日,文中有非常详细的代码示例,对正在学习java的小伙伴们有非常好的帮助,需要的朋友可以参考下...2021-04-23
- 这篇文章主要介绍了Java如何发起http请求的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-03-31
antdesign-vue结合sortablejs实现两个table相互拖拽排序功能
这篇文章主要介绍了antdesign-vue结合sortablejs实现两个table相互拖拽排序功能,本文通过实例图文相结合给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-01-09- 说起C#和Java这两门语言(语法,数据类型 等),个人以为,大概有90%以上的相似,甚至可以认为几乎一样。但是在工作中,我也发现了一些细微的差别...2020-06-25
- 这篇文章主要介绍了解决Java处理HTTP请求超时的问题,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-03-29
- 这篇文章主要介绍了java 判断两个时间段是否重叠的案例,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-08-15
- 这篇文章主要为大家详细介绍了js实现列表按字母排序,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2020-08-11
java 画pdf用itext调整表格宽度、自定义各个列宽的方法
这篇文章主要介绍了java 画pdf用itext调整表格宽度、自定义各个列宽的方法,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-01-31- 这篇文章主要介绍了超简洁java实现双色球若干注随机号码生成(实例代码),本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-04-02
- 这篇文章主要介绍了C# 参数按照ASCII码从小到大排序(字典序)的方法,非常不错,具有参考借鉴价值,需要的朋友可以参考下...2020-06-25
- 这篇文章主要介绍了Java生成随机姓名、性别和年龄的实现示例,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-10-01
- 这篇文章主要介绍了java正则表达式判断前端参数修改表中另一个字段的值,需要的朋友可以参考下...2021-05-07
Java使用ScriptEngine动态执行代码(附Java几种动态执行代码比较)
这篇文章主要介绍了Java使用ScriptEngine动态执行代码,并且分享Java几种动态执行代码比较,需要的朋友可以参考下...2021-04-15- 这篇文章主要介绍了Java开发实现人机猜拳游戏,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2020-08-03
- 这篇文章主要介绍了Java List集合返回值去掉中括号('[ ]')的操作,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-08-29
Java 8 Stream 的终极技巧——Collectors 功能与操作方法详解
这篇文章主要介绍了Java 8 Stream Collectors 功能与操作方法,结合实例形式详细分析了Java 8 Stream Collectors 功能、操作方法及相关注意事项,需要的朋友可以参考下...2020-05-20Java中lombok的@Builder注解的解析与简单使用详解
这篇文章主要介绍了Java中lombok的@Builder注解的解析与简单使用,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友可以参考下...2021-01-06