开发者学堂课程【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
;
}
}
}
p
ublic void remove( Comparable 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
;
//一直向左找
这种数据结构的删除操作是非常繁琐的,所以如果不是必须的情况下不建议使用删除。