开发者学堂课程【Java 高级编程： 二叉树数据删除】学习笔记，与课程紧密联系，让用户快速学习知识。
课程地址：https://developer.aliyun.com/learning/course/20/detail/365
二叉树数据删除
内容介绍：
一、二叉树数据删除的基本规则
二、范例:在 Node 类中追加有新的处理功能
三、范例:在 BinaryTree 类里面进行节点的处理。
基本规则：
• 1、如果待删除节点没有子节点，那么直接删掉即可﹔
• 2、如果待删除节点只有一个子节点，那么直接删掉，并用其子节点去顶替它;
这个时候考虑两种情况分析，只有一个左子树。
只有一个右子树的情况。
左右子树操作一样，只要删除一个节点。
• 3、如果待删除节点有两个子节点，这种情况比较复杂︰首选找出它的后继节点，然后处理“后继节点”和“被删除节点的父节点”之间的关系，最后处理“后继节点的子节点”和“被删除节点的子节点”之间的关系。
下面通过具体的代码实现操作功能。
范例:在 Node 类中追加有新的处理功能
获取要删除的节点对象
@param data 比较的对象.
return 要删除的节点对象，对象一定存在。
public Node getRemoveNode(Comparable<T> data) {
if (data.compareTo((T)this.data) == 0) {
return this ; //查找到了。
}else if (data.compareTo((T)this.data)< 0) {//左边有数据
if (this.left != null) {
return this.left.getRemoveNode(data) ;
}else {
return null ;
}
}else {
if ( this.right != null) {
return this.right.getRemoveNode(data) ;
}else {
return null ;
}
}
}
public void remove( Comparable<T> data) {
Node removeNode = this.root.getRemoveNode(data) ;//找到要删除的节点
if ( removeNode != null) { //找到要册除的对象信息
//情况一:没有任何的子节点
if ( removeNode.left == null removeNode.right == null) {removeNode.parent = null ; //父节点直接断开引用
} else if (removeNode.left != null && removeNode.right == null) {//左边不为空
removeNode.left.parent = removeNode.parent;
} else if (removeNode.left == null && removeNode.right != null) {//右边不为空
removeNode.right.parent = removeNode.parent ;
}else {//两边都有节点,则向右边节点中最左边的节点找到，改变其方向
Node moveNode = removeNode.right ; //移动的节点
while(moveNode.left != nu11) { //现在还有左边的节点
moveNode = moveNode. 1eft ; //一直向左找
} //就可以确定删除节点的右节点的最小的左节点
moveNode.parent . left = null ;//断开原本的连接
moveNode.parent = removeNode. parent ;
moveNode.right = removedode.right ; //改变原始的右节点的指向
}
}
}
}
范例:在 BinaryTree 类里面进行节点的处理。
/**
*执行数据的删除处理
*@param data要删除的数据*/
public void remove(comparable<T>data) {
if (this.root == nul1) { //根节点不存在
return ;//结束调用
else {Node removeNode = this.root.getRemoveNode(data);//找到要删除的节点
if (removeNode != nul1) {//找到要删除的对象信息
//情况一。没有任何的子节点
if (removeNode.left == nu11 && removeNode.right == nul1) {
removeNode.parent. left = nul1 ;
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 != nul1){
removeNode.parent . left = removeNode.right ;
removeNode.right.parent = removeNode.parent ;
}else //两边都有节点，则将右边节点中最左边的节点找到，改变其指向;
Node moveNode = removeNode.right ; //移动的节点
while(moveNode.left != null) { //现在还有左边的节点
moveNode = moveNode. left ; //一直向左找
if (this.root.data.compareTo((T)data) == 0) { //要删除的是根节点
}else {
Node removeNode = this.root.getRemoveNode(data) ;//找到要删除的节点
if (removeNode != nul1) {//找到要删除的对象信息
//情况一。没有任何的子节点
if (removeNode.left == nu11 && removeNode.right == nul1) {
removeNode.parent. left = nul1 ;
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 &8 removeNode.right != nul1){
removeNode.parent . left = removeNode.right ;
removeNode.right.parent = removeNode.parent ;
}else //两边都有节点，则将右边节点中最左边的节点找到，改变其指向;
Node moveNode = removeNode.right ; //移动的节点
while(moveNode.left != null) { //现在还有左边的节点
moveNode = moveNode. left ; //一直向左找
这种数据结构的删除操作是非常繁琐的，所以如果不是必须的情况下不建议使用删除。
