数据结构——有序二叉树的删除

在上一篇博客中，我们介绍了有序二叉树的构建、遍历、查找。

数据结构——有序二叉树的构建&遍历&查找-CSDN博客文章浏览阅读707次，点赞18次，收藏6次。因为数据的类型决定数据在内存中的存储形式。left right示意为左右节点其类型也为TreeNode，用于接受后续一系列操作，保持了结构的一致性。为什么left和right的类型为TreeNode？我们采用递归的方式实现。我们创建一个test类。https://blog.csdn.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;
	             }
			 }
		}				
	}