首页 > 代码库 > 二叉树中删除一个节点

二叉树中删除一个节点

2024-07-08 08:46:31   222人阅读

 二叉树的删除可以算是二叉树最为复杂的操作，删除的时候要考虑到很多种情况：
1.被删除的节点是叶子节点
2.被删除的节点只有左孩子节点
3.被删除的节点只有右孩子节点
4.被删除的有两个孩子节点
 
所以在删除的时候，这4种情况都必须考虑进去，并且这4中情况之下，还会有细的划分，下面就细说怎么删除。
 
在二叉树中想要删除一个节点，首先需要找到这个节点，由于二叉树在插入节点的时候会遵循一个原则，就是利用节点的值来判断
节点将被插入的位置（或者给节点加一个key，用key来判断）。从根节点开始往下走，比当前节点小（或等于）的会被插入到
当前节点的左边，比当前节点大的会被插入到当前节点的右边。所以，根据根据二叉树的插入规则来找出即将被删除的节点。代码如下; 
//保存当前节点
		Node parent=root;//保存当前节点父节点
		boolean isLeft=true;//记录是否是左几点
		//定位到将被删除的节点 
		while(key!=curr.key){
			if(key<=curr.key){
				isLeft=true;//经过左节点
				if(curr.left!=null){
					parent=curr;
					curr=curr.left;
				}
			}else{
				isLeft=false;//经过右节点
				if(curr.right!=null){
					parent=curr;
					curr=curr.right;
				}
			}
			if(curr==null){
				return false;
			}
}


  在这断代码中，首先定义了两个引用，一个用来代表当前节点，一个用来代表当前节点的父节点，然后进入一个while循环，
循环里，首先会根据key的比较来决定该往左走还是往右走，如果往左走，就说明当前节点是它父节点的左孩子了，然后把
ifLeft设置为true，如果往右走，同理就把isLeft设置为false（isLeft在后面会被用到）。现在，往下走得方向
已经确定了，然后该就判断所经过的节点（即当前节点）是否为空，如果该节点的左右都为空，就说明你要删的节点没有找到，程序
将会返回false。如果如果当前节点左孩子不为空，就把当前节点等于它的左孩子，相当于又往下走了一步。正个寻找的过程，就是
不停的根据值判断，不停的往下走，直到满足条件，循环停止。这时，当前节点就保存的是即将被删除节点的引用，并且还知道被删除的
父节点是谁，被删除节点是它父节点的哪边的孩纸都知道。
找到了被删除的节点，下面就来看，要怎么删除它。
1.如果被删除的节点是叶子节点，用代码表示就是
if(curr.left==null&&curr.right==null){
			if(curr==root){
				root=null;
			}else if(isLeft){
				parent.left=null;
			}else{
				parent.right=null;
			}
		}


可以看出，情况又被细分了三种，当被删除节点即是叶子节点又是根节点，这是树中就只有一个根节点了，就直接删除
下面两种是判断的是，当前被删除节点是其父节点哪边的节点。

2.被删除的节点只有左孩子节点
if(curr.right==null){
			if(curr==root){
				root=root.left;
			}else if(isLeft){
				parent.left=curr.left;
			}else{
				parent.right=curr.left;
			}
		}
当被删除的节点只有一个孩子时，就只需要用它的孩子节点，把它自己给替换下去。具体的还是跟上面一样，需要分三种情况
来考虑，如果是根节点，就直接把根节点指向根节点的左孩子，这样一来，原来的根节点就无法访问到，会被虚拟机自动回收掉。
同理下面也一样。

 
3.被删除的节点只有右孩子节点，这种情况跟第二种情况类似
  
if(curr.left==null){
			if(curr==root){
				root=root.right;
			}else if(isLeft){
				parent.left=curr.right;
			}else{
				parent.right=curr.right;
			}
		}


 
4.被删除的有两个孩子节点，这种情况最复杂，因为要考虑到删除之后顺序不能乱。
所以这种类型的节点要删除，如果直接删，真个树的大小顺序就乱了，所以需要考虑，在树中找到一个合适的节点来把这个节点
给替换掉，用这种方法来保持整个数的稳定。所以又一个问题又来了了，该找哪个节点来替换它？结论是，需要在树中找出所有比
被删除节点的值大的所有数，并在这些数中找出一个最小的数来。听起来很拗，如果把它用图形来描述的话，就是，从被删除的节点出发
经过它的右节点，然后右节点最左边的叶子节点就是我们要找的，它有一个专业名词叫中序后继节点。下面专门来写一个方法来找它：
  
   
 public Node getSuccessor(Node delNode){  //参数为被删除的节点
			//定义一个当前节点的引用，直接让往下走一步，走到被删除节点的右节点
			Node curr=delNode.right; 
			Node successor=curr;  //用来指向中级后续节点
			Node sucParent=null; //用来指向中级后续节点的父节点
			while(curr!=null){  
				sucParent=successor;
				successor=curr;
				curr=curr.left;
			}
			//循环停止，中级后续节点被找出
			if(successor!=delNode.right){
				//将后继节点的子节点（只可能有右节点）替补到后继节点的位置上
				sucParent.left=successor.right;
				//将被删除的右孩子连接到后继节点的右节点上
				successor.right=delNode.right;
				//将被删除的左孩子连接到后继节点的右节点上（就是用后继节点替换掉被删除的节点）
			}
			return successor;
		}



由于过程比较复杂，这里用图来表示



删除节点的完成代码：

/**
	 * 删除节点
	 * @param key
	 */
	public boolean delete(int key){
		Node curr=root;//保存当前节点
		Node parent=root;//保存当前节点父节点
		boolean isLeft=true;//记录是否是左几点
		//定位到将被删除的节点 
		while(key!=curr.key){
			if(key<=curr.key){
				isLeft=true;//经过左节点
				if(curr.left!=null){
					parent=curr;
					curr=curr.left;
				}
			}else{
				isLeft=false;//经过右节点
				if(curr.right!=null){
					parent=curr;
					curr=curr.right;
				}
			}
			if(curr==null){
				return false;
			}
		}
		//如果被删除节点是叶子节点
		if(curr.left==null&&curr.right==null){
			if(curr==root){
				root=null;
			}else if(isLeft){
				parent.left=null;
			}else{
				parent.right=null;
			}
		//如果被删除节点只有左节点
		}else if(curr.right==null){
			if(curr==root){
				root=root.left;
			}else if(isLeft){
				parent.left=curr.left;
			}else{
				parent.right=curr.left;
			}
		//如果被删除节点只有右节点
		}else if(curr.left==null){
			if(curr==root){
				root=root.right;
			}else if(isLeft){
				parent.left=curr.right;
			}else{
				parent.right=curr.right;
			}
		}else{
			Node successor=getSuccessor(curr);
			//将后继节点与被删除的父节点进行连接，完成整个替换过程
			if(curr==root){
				root=successor;
			}else if(curr==parent.left){
				parent.left=successor;
			}else{
				parent.right=successor;
			}
			successor.left=curr.left;
		}
		return true;
		
	}
	
	public Node getSuccessor(Node delNode){
		Node curr=delNode.right;
		Node successor=curr;
		Node sucParent=null;
		while(curr!=null){
			sucParent=successor;
			successor=curr;
			curr=curr.left;
		}
		if(successor!=delNode.right){
			//将后继节点的子节点（只可能有右节点）替补到后继节点的位置上
			sucParent.left=successor.right;
			//将被删除的右孩子连接到后继节点的右节点上
			successor.right=delNode.right;
			//将被删除的左孩子连接到后继节点的右节点上（就是用后继节点替换掉被删除的节点）
		}
		return successor;
	}


联系
我们