[数据结构与算法]有序二叉树节点的删除

一、删除节点有三种情况

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;
                }
            }
        }

    }