上一篇：手把手教你实现二叉树数据添加 | 带你学《Java语言高级特性》之三十九
二叉树能够提升查询效率得益于其特殊的结构，而删除节点意味着其他节点也将受到影响，删除的节点的位置也决定了该次删除操作的复杂程度。本节将具体介绍二叉树删除节点功能的实现。
【本节目标】
通过阅读本节内容，你将通过具体的示例图了解到二叉树节点删除过程中遇到的难点问题，并理解删除时需要对其他节点做怎样的调整，学会其代码实现。
二叉树数据删除
二叉树之中的数据删除操作是非常复杂的，因为在进行数据删除的时候需要考虑的情况是比较多的：
情况1、如果待删除节点没有子节点，那么直接删掉即可：
数据的删除情况分析一
情况2、如果待删除节点只有一个子节点，那么直接删掉，并用其子节点去顶替它；
这个时候考虑两种情况分析，只有一个左子树。
数据的删除情况分析二左子树
只有一个右子树
数据的删除情况分析二右子树
情况3、如果待删除节点有两个子节点，这种情况比较复杂，首先找出它的后继节点，然后处理“后继节点”和“被删除节点的父节点”之间的关系，最后处理“后继节点的子节点”和“被删除节点的子节点”之间的关系。
数据的删除情况分析三
下面通过具体的代码实现操作功能。
import java.util.Arrays;
public class JavaAPIDemo {
public static void main(String[] args) throws Exception{
BinaryTree<Person> tree=new BinaryTree<Person>();
tree.add(new Person("小强-80",80));
tree.add(new Person("小强-50",50));
tree.add(new Person("小强-60",60));
tree.add(new Person("小强-30",30));
tree.add(new Person("小强-90",90));
tree.add(new Person("小强-10",10));
tree.add(new Person("小强-55",55));
tree.add(new Person("小强-70",70));
tree.add(new Person("小强-85",85));
tree.add(new Person("小强-95",95));
tree.remove(new Person("小强-80",80));
System.out.println(Arrays.toString(tree.toArray()));
}
}
/**
* 实现二叉树操作
* @param <T> 要进行二叉树的实现
*/
class BinaryTree<T extends Comparable<T>>{
private class Node{
private Comparable<T> data; //存放Comparable,可以比较大小
private Node parent; //保存父节点
private Node left; //保存左子树
private Node right; //保存右子树
public Node(Comparable<T> data){ //构造方法直接负责进行数据的存储
this.data=data;
}
/**
* 实现节点数据的适当位置的存储
* @param newNode 创建的新节点
* @throws IllegalArgumentException 保存的数据已存在
*/
public void addNode(Node newNode) {
if(newNode.data.compareTo((T)this.data) <= 0){ //比当前节点数据小
if(this.left==null){ //没有左子树
//当前没有左子树
this.left=newNode; //保存左子树
newNode.parent=this; //保存父节点
}else{ //需要向左边继续判断
this.left.addNode(newNode); //继续向下判断
}
}else{ //比根节点的数据大
if(this.right==null){ //当前没有右子树
this.right=newNode; //保存左子树
newNode.parent=this; //保存父节点
}else{
this.right.addNode(newNode); //继续向下判断
}
}
}
/**
* 实现所有数据的获取处理，按照中序遍历的形式来完成
*/
public void toArrayNode() {
if(this.left!=null){ //有左子树
this.left.toArrayNode(); //递归调用
}
BinaryTree.this.returnData[BinaryTree.this.foot++]=this.data;
if(this.right!=null){
this.right.toArrayNode();
}
}
/**
* 检查是否包含此节点
* @param data 比较的对象
* @return 找到返回true，找不到返回false
*/
public boolean containsNode( Comparable<T> data) {
if (data.compareTo((T)this.data) ==0) {
return true ; //查找到了
} else if (data.compareTo((T)this.data) < 0){ //左边有数据
if (this.left != null) {
return this.left.containsNode(data);
} else {
return false;
}
} else {
if (this.right != null) {
return this .right.containsNode(data);
} else {
return false;
}
}
}
/**
* 获取要删除的节点对象
* @param data 比较的对象
* @return 要删除的节点对象，对象一定存在
*/
public Node getRemoveNode(Comparable<T> data) {
if(data.compareTo((T)this.data) ==0){
return this;//查找到了
}
if (data.compareTo((T)this.data) < 0) {
if (this.left != null) {
return this.left.getRemoveNode(data);
}
return null;
}
if (this.right != null) {
return this.right.getRemoveNode(data);
}
return null;
}
}
//-------------------以下为二叉树的功能实现--------------
private Node root; //保存根节点
private int count; //保存数据个数
private Object[] returnData; //返回的数据
private int foot=0; //脚标控制
/**
* 进行数据的保存
* @param data 要保存的数据内容
* @exception NullPointerException 保存数据为空时抛出的异常
*/
public void add(Comparable<T> data){
if(data==null){
throw new NullPointerException("保存的数据不允许为空！");
}
//所有的数据本身不具备节点关系的匹配，那么一定要将其包装在Node类之中
Node newNode=new Node(data); //保存节点
if(this.root==null){ //现在没有根节点，则第一个节点作为根节点
this.root=newNode;
}else{ //需要为其保存到一个合适的节点
this.root.addNode(newNode); //交由node类负责处理
}
this.count++;
}
/**
* 以对象数组的形式返回全部数据，如果没有数据返回null
* @return 全部数据
*/
public Object[] toArray(){
if(this.count==0){
return null;
}
this.returnData=new Object[this.count];//保存长度为数组长度
this.foot=0; //脚标清零
this.root.toArrayNode(); //直接通过Node类负责
return this.returnData; //返回全部的数据
}
/**
* 进行数据的删除处理
* @param data 要删除的数据
*/
public void remove(Comparable<T> data){
if(this.root == null) { // 根节点不存在
return; // 结束调用
} else {
if(this.root.data.compareTo((T)data) == 0) { // 要删除的是根节点
Node moveNode = this.root.right; // 移动的节点
while(moveNode.left != null) { //现在还有左边的节点
moveNode = moveNode.left; //一直向左找
} // 就可以确定删除节点的右节点的最小的子节点
moveNode.parent.left = null;
moveNode.right = this.root.right;
moveNode.left = this.root.left;
this.root = moveNode; // 改变根节点
} else {
Node removeNode = this.root.getRemoveNode(data);// 找到要删除的节点
if(removeNode != null) { //找到要删除的对象信息
// 情况一：没有任何的子节点
if(removeNode.left == null && removeNode.right == null) {
removeNode.parent.left = null;
removeNode.parent.right = null;
removeNode.parent = null; //父节点直接断开引用
} else if(removeNode.left != null && removeNode.right == null) { //左边不为空
removeNode.parent.left = removeNode.left;
removeNode.left.parent = removeNode.parent;
} else if(removeNode.left == null && removeNode.right != null) { //右边不为空
removeNode.parent.left = removeNode.right;
removeNode.right.parent = removeNode.parent;
} else { //两遍都有节点，则将右边节点中最左边的节点找到，改变其指向
Node moveNode = removeNode.right; // 移动的节点
while(moveNode.left != null) { //现在还有左边的节点
moveNode = moveNode.left; //一直向左找
} // 就可以确定删除节点的右节点的最小的子节点
removeNode.parent.left = moveNode;
moveNode.parent.left = null; // 断开原本的连接
moveNode.parent = removeNode.parent;
moveNode.right = removeNode.right; // 改变原始的右节点的指向
moveNode.left = removeNode.left;
}
}
}
this.count--;
}
}
}
class Person implements Comparable<Person>{
private String name;
private int age;
public Person(String name, int age) {
this.name = name;
this.age = age;
}
@Override
public String toString() {
return "【Person类对象】姓名：" + this.name + "、年龄：" + this.age +"\n";
}
@Override
public int compareTo(Person person) {
return this.age-person.age;//升序
}
}运行结果：
[【Person类对象】姓名：小强-10、年龄：10
, 【Person类对象】姓名：小强-30、年龄：30
, 【Person类对象】姓名：小强-50、年龄：50
, 【Person类对象】姓名：小强-55、年龄：55
, 【Person类对象】姓名：小强-60、年龄：60
, 【Person类对象】姓名：小强-70、年龄：70
, 【Person类对象】姓名：小强-85、年龄：85
, 【Person类对象】姓名：小强-90、年龄：90
, 【Person类对象】姓名：小强-95、年龄：95
]
可见，二叉树数据结构删除操作是非常繁琐的，所以如果不是必须的情况下，不建议进行删除操作。
想学习更多的Java的课程吗？从小白到大神，从入门到精通，更多精彩不容错过！免费为您提供更多的学习资源。
本内容视频来源于阿里云大学
下一篇：认识红黑树，解决二叉树删除后遗症 | 带你学《Java语言高级特性》之四十一
更多Java面向对象编程文章查看此处
