在上一篇博客中，我们介绍了有序二叉树的构建、遍历、查找。
数据结构——有序二叉树的构建&遍历&查找-****博客文章浏览阅读707次，点赞18次，收藏6次。因为数据的类型决定数据在内存中的存储形式。left right示意为左右节点其类型也为TreeNode，用于接受后续一系列操作，保持了结构的一致性。为什么left和right的类型为TreeNode？我们采用递归的方式实现。我们创建一个test类。https://blog.****.net/2301_78566776/article/details/144160961?spm=1001.2014.3001.5501这篇博客我们来介绍一下有序二叉树的删除。
删除操作
删除操作的步骤相对复杂，因为需要处理三种情况：
1.要删除的节点是叶子节点（没有子节点）
删除叶子节点
1.找到要删除的节点targetNode
2.找到targetNode的父节点（考虑父节点是否存在）
3.确定targetNode是parentNode的左子树还是右子树
4.根据前面的情况进行删除
左子树：parentNode.left=null；右子树：parentNode.right=null；
2.要删除的节点只有一个子节点
删除有一个子树的节点
1.找到要删除的节点targetNode
2.找到targetNode的父节点（考虑父节点是否存在）
3.确定targetNode是左子树还是右子树
4.确定targetNode有的是左子树还是右子树
5.targetNode有的是左子树
parentNode.left = targetNode.left;——删除的节点是父节点的左子树
parentNode.right = targetNode.left;——删除的节点是父节点的右子树
6.targetNode有的是右子树:parentNode.left = targetNode.right;——删除的节点是父节点的左子树
parentNode.right = targetNode.right;——删除的节点是父节点的右子树
3.要删除的节点有两个子节点
对于第三种情况，通常的做法是找到要删除节点的中序后继（或中序前驱），将其值替换到要删除的节点上，然后删除这个中序后继（或中序前驱）。
删除有两个子树的节点
1.找到要删除的节点targetNode
2.找到targetNode的父节点（考虑父节点是否存在）
3.去找targetNode的右子树的左子树当中的最小值
4.将targetNode的值和最小值的值进行互换
5.删除最小值——即删除叶子节点（替换删除）
Java代码如下:
public TreeNode Search(TreeNode node,int value) {
if (node == null) {
return null;
}
if (value==node.data) {
return node;
}else if(value<node.data){
if(node.left!=null) {
return Search(node.left,value);
}
}else {
if(node.right!=null) {
return Search(node.right,value);
}
}
return null;
// TODO Auto-generated method stub
}
public TreeNode SearchParent(TreeNode node,int value){
if (node == null) {
return null;
}
if((node.left!=null&&node.left.data==value)||(node.right!=null&&node.right.data==value)){
return node;
}else {
if(node.left!=null&&value<node.data) {
return SearchParent(node.left,value);
}else if(node.right!=null&&value>node.data) {
return SearchParent(node.right,value);
}else {
return null;
}
}
}
public int delRightTreeMin(TreeNode node){
TreeNode tempNode = node;
while (tempNode.left !=null){
tempNode = tempNode.left;
}
return tempNode.data; //最值进行返回
}
public void delete(TreeNode node,int value){
if (node == null) {//空树，直接返回
return;
}
if(node.left==null&&node.right==null) {//单节点树，直接置空
node=null;
return;
}
//先查询要删除的节点
TreeNode targetNode=Search(node,value);
if(targetNode==null) {//没有找到
return;
}
//找父节点
TreeNode parentNode=SearchParent(node,value);
if(targetNode.left==null&&targetNode.right==null) {//如果targetNode是叶子节点
if(parentNode.left!=null&&parentNode.left.data==targetNode.data){//如果target是parent的左子树
parentNode.left=null;
}else if(parentNode.right!=null&&parentNode.right.data==targetNode.data) {//如果target是parent的右子树
parentNode.right=null;
}
}
else if(targetNode.left!= null && targetNode.right!=null) {//如果targetNode有两个子节点
int minValue = delRightTreeMin(targetNode.right); //找右子树的最小值
delete(targetNode.right,minValue);
targetNode.data = minValue;//互换最小值
}
else { //只有一个子节点的节点
if(targetNode.left !=null){ //当前要删除的节点有左子树
if(parentNode.left.data == targetNode.data){ //删除的节点是父节点的左子树
parentNode.left = targetNode.left;
}else {//删除的节点是父节点的右子树
parentNode.right = targetNode.left;
}
}
else {//当前要删除的节点有右子树
if(parentNode.left.data == targetNode.data){ //删除的节点是父节点的左子树
parentNode.left = targetNode.right;
}else {//删除的节点是父节点的右子树
parentNode.right = targetNode.right;
}
}
}
}