二叉搜索树删除任意元素

在之前的博客中写了关于增加和删除二叉搜索树中的最值的操作.那么如何删除和增加二叉搜索树中的任意节点呢?如下.

二分搜索树删除任意节点

情况分析

被删除的节点只有一个子节点

示例01
直接使用这个子节点代替父节点

---

被删除的节点左右子节点都存在

• 1).假设删除的节点为d,找到d节点右子树中的最小值(也就是比d节点大的最小值)
  (1).找到替换的节点
  s = min(d->right)
  s是d的后继,removeMin()方法会返回最小值
  (2).替换并且删除d节点,这里的删除操作实际上就是父节点的引用指向了新的子节点s ,s是新的子树的根
  s->right = removeMin(d->right)
s -> left = d -> left
  

  示例02-后继替换

• 2).假设删除的节点为d,找到d节点左子树中的最大值(也就是比d节点小的最大值)
  (1).找到替换的节点
  m = max(d->left)
  s是d的前驱,removeMax()方法会返回最大值
  (2).替换并且删除d节点,这里的删除操作实际上就是父节点的引用指向了新的子节点s ,s是新的子树的根
  s->left = removeMax(d->left)
s -> right = d -> right
  

  示例02-前驱替换

---

代码实现

/**
     * 删除任意节点
     * @param data
     */
    public void remove(E data){
        //记录根节点位置
        root = remove(root,data);
    }

    /**
     * @param node  传入的节点
     * @param e 数值
     * @return
     */
    private Node remove(Node node,E e){
        //判断遍历完成之后找到节点没有
        if (node == null){
            return null;
        }

        //不等的情况进行递归查找

        //如果目标值比节点值小,节点向左边移动
        if (e.compareTo(node.data) < 0){
            node.left = remove(node.left,e);
            return node;

            //如果目标值比节点值大,节点向右边边移动
        }else if (e.compareTo(node.data) > 0){
            node.right = remove(node.right,e);
            return node;
        }else {

            //e == node.data,找到节点

            //左右为空时的处理
            if (node.left == null){
                Node rightNode = node.right;
                //释放内存
                node.right = null;
                size --;
                return rightNode;
            }

            if (node.right == null){
                Node leftNode = node.left;
                node.left = null;
                size--;
                return leftNode;
            }

            Node successor = getMin(node.right);
            successor.right = removeMin(node.right);
            successor.left = node.left;


            node.left = node.right = null;
            return successor;
        }
    }