Java 实现二叉搜索树的查找、插入、删除、遍历
作者:Michaelwjw 发布时间:2023-10-04 05:37:39
由于最近想要阅读下JDK1.8 中HashMap的具体实现,但是由于HashMap的实现中用到了红黑树,所以我觉得有必要先复习下红黑树的相关知识,所以写下这篇随笔备忘,有不对的地方请指出~
学习红黑树,我觉得有必要从二叉搜索树开始学起,本篇随笔就主要介绍Java实现二叉搜索树的查找、插入、删除、遍历等内容。
二叉搜索树需满足以下四个条件:
若任意节点的左子树不空,则左子树上所有结点的值均小于它的根结点的值;
若任意节点的右子树不空,则右子树上所有结点的值均大于它的根结点的值;
任意节点的左、右子树也分别为二叉查找树;
没有键值相等的节点。
二叉搜索树举例:
图一
接下来将基于图一介绍二叉搜索树相关操作。
首先,应先有一个节点对象相关的类,命名为 Node。
class Node {
int key;
int value;
Node leftChild;
Node rightChild;
public Node(int key, int value) {
this.key = key;
this.value = value;
}
public void displayNode() {
}
}
Node 类中包含 key 值,用于确定节点在树中相应位置,value 值代表要存储的内容,还含有指向左右孩子节点的两个引用。
接下来看下搜索树相应的类:
class Tree {
Node root;//保存树的根
public Node find(int key) {//查找指定节点
}
public void insert(int key, int value) {//插入节点
}
public boolean delete(int key) {//删除指定节点
}
private Node getDirectPostNode(Node delNode) {//得到待删除节点的直接后继节点
}
public void preOrder(Node rootNode) {//先序遍历树
}
public void inOrder(Node rootNode) {//中序遍历树
}
public void postOrder(Node rootNode) {//后序遍历树
}
}
类中表示树的框架,包含查找、插入、遍历、删除相应方法,其中删除节点操作最为复杂,接下来一一介绍。
一、查找某个节点
由于二叉搜索树定义上的特殊性,只需根据输入的 key 值从根开始进行比较,若小于根的 key 值,则与根的左子树比较,大于根的key值与根的右子树比较,以此类推,找到则返回相应节点,否则返回 null。
public Node find(int key) {
Node currentNode = root;
while (currentNode != null && currentNode.key != key) {
if (key < currentNode.key) {
currentNode = currentNode.leftChild;
} else {
currentNode = currentNode.rightChild;
}
}
return currentNode;
}
二、插入节点
与查找操作相似,由于二叉搜索树的特殊性,待插入的节点也需要从根节点开始进行比较,小于根节点则与根节点左子树比较,反之则与右子树比较,直到左子树为空或右子树为空,则插入到相应为空的位置,在比较的过程中要注意保存父节点的信息 及 待插入的位置是父节点的左子树还是右子树,才能插入到正确的位置。
public void insert(int key, int value) {
if (root == null) {
root = new Node(key, value);
return;
}
Node currentNode = root;
Node parentNode = root;
boolean isLeftChild = true;
while (currentNode != null) {
parentNode = currentNode;
if (key < currentNode.key) {
currentNode = currentNode.leftChild;
isLeftChild = true;
} else {
currentNode = currentNode.rightChild;
isLeftChild = false;
}
}
Node newNode = new Node(key, value);
if (isLeftChild) {
parentNode.leftChild = newNode;
} else {
parentNode.rightChild = newNode;
}
}
三、遍历二叉搜索树
遍历操作与遍历普通二叉树操作完全相同,不赘述。
public void preOrder(Node rootNode) {
if (rootNode != null) {
System.out.println(rootNode.key + " " + rootNode.value);
preOrder(rootNode.leftChild);
preOrder(rootNode.rightChild);
}
}
public void inOrder(Node rootNode) {
if (rootNode != null) {
inOrder(rootNode.leftChild);
System.out.println(rootNode.key + " " + rootNode.value);
inOrder(rootNode.rightChild);
}
}
public void postOrder(Node rootNode) {
if (rootNode != null) {
postOrder(rootNode.leftChild);
postOrder(rootNode.rightChild);
System.out.println(rootNode.key + " " + rootNode.value);
}
}
四、删除指定节点。
在二叉搜索树中删除节点操作较复杂,可分为以下三种情况。
1、待删除的节点为叶子节点,可直接删除。
public boolean delete(int key) {
Node currentNode = root;//用来保存待删除节点
Node parentNode = root;//用来保存待删除节点的父亲节点
boolean isLeftChild = true;//用来确定待删除节点是父亲节点的左孩子还是右孩子
while (currentNode != null && currentNode.key != key) {
parentNode = currentNode;
if (key < currentNode.key) {
currentNode = currentNode.leftChild;
isLeftChild = true;
} else {
currentNode = currentNode.rightChild;
isLeftChild = false;
}
}
if (currentNode == null) {
return false;
}
if (currentNode.leftChild == null && currentNode.rightChild == null) {//要删除的节点为叶子节点
if (currentNode == root)
root = null;
else if (isLeftChild)
parentNode.leftChild = null;
else
parentNode.rightChild = null;
}
......
}
2、待删除节点只有一个孩子节点
例如删除图一中的 key 值为 11 的节点,只需将 key 值为 13 的节点的左孩子指向 key 值为 12的节点即可达到删除 key 值为 11 的节点的目的。
由以上分析可得代码如下(接上述 delete 方法省略号后):
else if (currentNode.rightChild == null) {//要删除的节点只有左孩子
if (currentNode == root)
root = currentNode.leftChild;
else if (isLeftChild)
parentNode.leftChild = currentNode.leftChild;
else
parentNode.rightChild = currentNode.leftChild;
} else if (currentNode.leftChild == null) {//要删除的节点只有右孩子
if (currentNode == root)
root = currentNode.rightChild;
else if (isLeftChild)
parentNode.leftChild = currentNode.rightChild;
else
parentNode.rightChild = currentNode.rightChild;
}
......
3、待删除节点既有左孩子,又有右孩子。
例如删除图一中 key 值为 10 的节点,这时就需要用 key 值为 10 的节点的中序后继节点(节点 11)来代替 key 值为 10 的节点,并删除 key 值为 10 的节点的中序后继节点,由中序遍历相关规则可知, key 值为 10 的节点的直接中序后继节点一定是其右子树中 key 值最小的节点,所以此中序后继节点一定不含子节点或者只含有一个右孩子,删除此中序后继节点就属于上述 1,2 所述情况。图一中 key 值为 10 的节点的直接中序后继节点 为 11,节点 11 含有一个右孩子 12。
所以删除 图一中 key 值为 10 的节点分为以下几步:
a、找到 key 值为 10 的节点的直接中序后继节点(即其右子树中值最小的节点 11),并删除此直接中序后继节点。
private Node getDirectPostNode(Node delNode) {//方法作用为得到待删除节点的直接后继节点
Node parentNode = delNode;//用来保存待删除节点的直接后继节点的父亲节点
Node direcrPostNode = delNode;//用来保存待删除节点的直接后继节点
Node currentNode = delNode.rightChild;
while (currentNode != null) {
parentNode = direcrPostNode;
direcrPostNode = currentNode;
currentNode = currentNode.leftChild;
}
if (direcrPostNode != delNode.rightChild) {//从树中删除此直接后继节点
parentNode.leftChild = direcrPostNode.rightChild;
direcrPostNode.rightChild = null;
}
return direcrPostNode;//返回此直接后继节点
}
b、将此后继节点的 key、value 值赋给待删除节点的 key,value值。(接情况二中省略号代码之后)
else { //要删除的节点既有左孩子又有右孩子
//思路:用待删除节点右子树中的key值最小节点的值来替代要删除的节点的值,然后删除右子树中key值最小的节点
//右子树key最小的节点一定不含左子树,所以删除这个key最小的节点一定是属于叶子节点或者只有右子树的节点
Node directPostNode = getDirectPostNode(currentNode);
currentNode.key = directPostNode.key;
currentNode.value = directPostNode.value;
}
至此删除指定节点的操作结束。
最后给出完整代码及简单测试代码及测试结果:
class Node {
int key;
int value;
Node leftChild;
Node rightChild;
public Node(int key, int value) {
this.key = key;
this.value = value;
}
public void displayNode() {
}
}
class Tree {
Node root;
public Node find(int key) {
Node currentNode = root;
while (currentNode != null && currentNode.key != key) {
if (key < currentNode.key) {
currentNode = currentNode.leftChild;
} else {
currentNode = currentNode.rightChild;
}
}
return currentNode;
}
public void insert(int key, int value) {
if (root == null) {
root = new Node(key, value);
return;
}
Node currentNode = root;
Node parentNode = root;
boolean isLeftChild = true;
while (currentNode != null) {
parentNode = currentNode;
if (key < currentNode.key) {
currentNode = currentNode.leftChild;
isLeftChild = true;
} else {
currentNode = currentNode.rightChild;
isLeftChild = false;
}
}
Node newNode = new Node(key, value);
if (isLeftChild) {
parentNode.leftChild = newNode;
} else {
parentNode.rightChild = newNode;
}
}
public boolean delete(int key) {
Node currentNode = root;
Node parentNode = root;
boolean isLeftChild = true;
while (currentNode != null && currentNode.key != key) {
parentNode = currentNode;
if (key < currentNode.key) {
currentNode = currentNode.leftChild;
isLeftChild = true;
} else {
currentNode = currentNode.rightChild;
isLeftChild = false;
}
}
if (currentNode == null) {
return false;
}
if (currentNode.leftChild == null && currentNode.rightChild == null) {
//要删除的节点为叶子节点
if (currentNode == root)
root = null;
else if (isLeftChild)
parentNode.leftChild = null;
else
parentNode.rightChild = null;
} else if (currentNode.rightChild == null) {//要删除的节点只有左孩子
if (currentNode == root)
root = currentNode.leftChild;
else if (isLeftChild)
parentNode.leftChild = currentNode.leftChild;
else
parentNode.rightChild = currentNode.leftChild;
} else if (currentNode.leftChild == null) {//要删除的节点只有右孩子
if (currentNode == root)
root = currentNode.rightChild;
else if (isLeftChild)
parentNode.leftChild = currentNode.rightChild;
else
parentNode.rightChild = currentNode.rightChild;
} else { //要删除的节点既有左孩子又有右孩子
//思路:用待删除节点右子树中的key值最小节点的值来替代要删除的节点的值,然后删除右子树中key值最小的节点
//右子树key最小的节点一定不含左子树,所以删除这个key最小的节点一定是属于叶子节点或者只有右子树的节点
Node directPostNode = getDirectPostNode(currentNode);
currentNode.key = directPostNode.key;
currentNode.value = directPostNode.value;
}
return true;
}
private Node getDirectPostNode(Node delNode) {//方法作用为得到待删除节点的直接后继节点
Node parentNode = delNode;//用来保存待删除节点的直接后继节点的父亲节点
Node direcrPostNode = delNode;//用来保存待删除节点的直接后继节点
Node currentNode = delNode.rightChild;
while (currentNode != null) {
parentNode = direcrPostNode;
direcrPostNode = currentNode;
currentNode = currentNode.leftChild;
}
if (direcrPostNode != delNode.rightChild) {//从树中删除此直接后继节点
parentNode.leftChild = direcrPostNode.rightChild;
direcrPostNode.rightChild = null;
}
return direcrPostNode;//返回此直接后继节点
}
public void preOrder(Node rootNode) {
if (rootNode != null) {
System.out.println(rootNode.key + " " + rootNode.value);
preOrder(rootNode.leftChild);
preOrder(rootNode.rightChild);
}
}
public void inOrder(Node rootNode) {
if (rootNode != null) {
inOrder(rootNode.leftChild);
System.out.println("key: " + rootNode.key + " " + "value: " + rootNode.value);
inOrder(rootNode.rightChild);
}
}
public void postOrder(Node rootNode) {
if (rootNode != null) {
postOrder(rootNode.leftChild);
postOrder(rootNode.rightChild);
System.out.println(rootNode.key + " " + rootNode.value);
}
}
}
public class BinarySearchTreeApp {
public static void main(String[] args) {
Tree tree = new Tree();
tree.insert(6, 6);//插入操作,构造图一所示的二叉树
tree.insert(3, 3);
tree.insert(14, 14);
tree.insert(16, 16);
tree.insert(10, 10);
tree.insert(9, 9);
tree.insert(13, 13);
tree.insert(11, 11);
tree.insert(12, 12);
System.out.println("删除前遍历结果");
tree.inOrder(tree.root);//中序遍历操作
System.out.println("删除节点10之后遍历结果");
tree.delete(10);//删除操作
tree.inOrder(tree.root);
}
}
测试结果:
来源:http://www.cnblogs.com/Michaelwjw/p/6384428.html
猜你喜欢
- SpringBoot 工厂模式自动注入Map一、建立工厂类public interface AnimalFactory { S
- 上一篇JavaMail入门第四篇 接收邮件中,控制台打印出的内容,我们无法阅读,其实,让我们自己来解析一封复杂的邮件是很不容易的,邮件里面格
- 由于jdk 1.8 之后sun.misc 包下的 BASE64Decode的依赖 被移除我们需要在自己的项目中引入EncodeUtils 工
- 获取方法的相关信息的两种形式反射是一种允许用户获得类信息的C#功能,Type对象映射它代表的底层对象;在.Net 中, 一旦获得了Type对
- 本文实例讲述了C#中Out与Ref的区别,可以加深C#程序设计人员对Out和Ref用法的理解,具体分析如下:一、区别分析:Out和Ref作为
- 开发环境:IntelliJ IDEA 2019.2.2Spring Boot版本:2.1.8一、发布REST服务1、IDEA新建一个名称为r
- 1、局部变量在方法或语句块中定义的变量被称为局部变量。变量声明和初始化都是在方法中,方法结束后,变量就会自动销毁。局部变量声明在方法、构造方
- Springboot + Vue,定时任务调度的全套实现方案。这里用了quartz这个框架,实现分布式调度任务很不错,关于quarz的使用方
- 一、问题描述有时候,我们会遇到在遍历List集合的过程中删除数据的情况。看着自己写的代码,感觉完全没有问题,但就是达不到预期的效果,这是为什
- 使用RateLimiter通过AOP方式进行限流1、引入依赖<!-- guava 限流 --><dependency>
- Java语言的垃圾回收1.垃圾回收机制的基本概念问:1.什么是Java垃圾回收?答:在Java语言的生命周期中,Java运行环境提供了一个系
- 一、题目描述题目:使用ThreadLocal管理一号和二号线程,分别存入100元,在三号线程中使用利用一号和二号的计算结果来算出账户的实际金
- 问题描述平常用的是java8,最近在学习java的新特性。这就需要从java8往更高的java版本切换。由于还在使用java8,测试完新特性
- 引言MyBatis-Plus | 最优雅最简洁地完成数据库操作是对MyBatis-Plus的功能进行简单介绍,虽然是介绍,也让我们领略到他的
- 引言:最近在工作中遇到与某些API对接的post的数据需要将对象的字段首字母小写。解决办法有两种:第一种:使用对象的字段属性设置JsonPr
- 前言在我们日常的开发中,很多时候,定时任务都不是写死的,而是写到数据库中,从而实现定时任务的动态配置,下面就通过一个简单的示例,来实现这个功
- 如下面代码以交灯为示例:public class Test { public static
- 前言在前面的篇章中,对Java语言的简单数据类型、数组、运算符和表达式以及流程控制的方法做了详细介绍。从本章开始,我们正式介绍面向对象的程序
- 本文实例讲述了C#清除WebBrowser中Cookie缓存的方法。分享给大家供大家参考,具体如下:最近用C#写一个程序,用一个窗体中的We
- 第1部分 ArrayList介绍ArrayList简介ArrayList 是一个数组队列,相当于 动态数组。与Java中的数组相比,它的容量