一、删除节点有三种情况
1,删除叶子节点
2,删除只有一个子树的节点
3,删除有两个子树的节点
二、步骤:
(一),删除叶子节点:
1,找到要删除的叶子节点(targetNode)
2,找到目标结点的父节点parentNode(考虑是否有父节点)
3,确定删除的节点是其父节点的左子树还是右子树
4,根据前边的情况进行删除
左子树:parent.left = null
右子树:parent.right = null
(二),删除只有一个子树的节点
1,找到要删除的叶子节点(targetNode)
2,找到目标结点的父节点parentNode(考虑是否有父节点)
3,确定删除的节点是其父节点的左子树还是右子树
4,根据前边的情况进行删除
1,targetNode是左子树
1,targetNode有左子树 parent.left = target.left
2,targetNode有右子树 parent.left = target.right
1,targetNode是右子树
1,targetNode有左子树 parent.right = target.left
2,targetNode有右子树 parent.right = target.right
(三),删除有两个子树的节点
1,找到要删除的叶子节点(targetNode)
2,找到目标结点的父节点parentNode(考虑是否有父节点)
3,找到删除节点右子树当中最小的/找到左子树当中最大的
4,将右子树当中最大的只替换掉删除节点的值
5,使用删除叶子节点的逻辑,删除最小值
代码实现:
//找到要删除的节点
public TreeNode Search(TreeNode node,int value){
if (root == null){
return null;
}
//判断node当前所指向的节点是不是要删除的节点
if (node.value == value){
return node;
}else if(value<node.value){
if (node.leftChild == null){
return null;
}
return Search(node.leftChild,value);
}else {
if (node.rightChild == null){
return null;
}
return Search(node.rightChild,value);
}
}
//找到父节点
public TreeNode SearchParent(TreeNode node,int value){
if (root == null){
return null;
}
//判断我们当前的节点的左或右孩子是不是我们要删除的值
if ((node.leftChild != null && node.leftChild.value == value) || (node.rightChild != null && node.rightChild.value == value) ){
return node;
}else {
// 往左走
if (node.leftChild !=null && value < node.value){
return SearchParent(node.leftChild,value);
}else if(node.rightChild !=null && value > node.value){
//向右走
return SearchParent(node.rightChild,value);
}else {
return null; //没有父节点
}
}
}
//删除方法
public void delete(TreeNode node,int value){
if (node == null){
return;
}
// 1.找到删除的节点
TreeNode targetNode = Search(node,value);
// 2.如果没有删除的节点
if (targetNode == null){
System.out.println("没有删除的节点");
return;
}
//如果这颗树只有一个节点
if (node.leftChild == null && node.rightChild == null){
root = null;
return;
}
//3.找到targetNode的父节点
TreeNode parentNode = SearchParent(node,value);
//删除的节点是叶子节点
if (targetNode.rightChild == null && targetNode.leftChild == null){
if (parentNode.leftChild !=null && parentNode.leftChild.value == targetNode.value){
parentNode.leftChild = null;
}else if (parentNode.rightChild !=null && parentNode.rightChild.value == targetNode.value){
parentNode.rightChild = null;
}
}else if(targetNode.rightChild!=null && targetNode.leftChild !=null){ //删除的是有两个子树的节点
//找到删除节点右子树当中最小的
int minValue = SearchRightMin(targetNode.rightChild);
targetNode.value = minValue;
}else { //删除只有一个子树的节点
//如果删除的节点有左子树
if (targetNode.leftChild !=null){
if (parentNode.leftChild.value == targetNode.value){ //删除的节点是父节的左子树
parentNode.leftChild = targetNode.leftChild;
}else {//删除的节点是父节的右子树
parentNode.rightChild = targetNode.leftChild;
}
}else {
if (parentNode.leftChild.value == targetNode.value){
parentNode.leftChild = targetNode.rightChild;
}else {
parentNode.rightChild = targetNode.rightChild;
}
}
}
}