全面理解二进制排序树(2)

删除节点

删除节点是二进制排序树最复杂的地方，主要是因为删除时有很多情况

前三种情况更容易处理，只需将父亲指给孩子，后一种情况更复杂，并且通过查看带有注释的代码可以更容易直接理解

    // 删除节点
    public void remove(Node target){
        if (target == null){
            return;
        }
        // 只有右子树
        if (target.left == null){
            // 如果target是其父亲的左子树
            if (target.parent.left == target){
                // 将target的右孩子连接到父亲的左孩子，
                // 也就是target的右孩子替代父亲
                target.parent.left = target.right;
            }else {
                // 如果target是右孩子，则连接到parent的右孩子
                target.parent.right = target.right;
            }
            // 如果右孩子非空，右孩子的parent指向target.parent
            if (target.right != null){
                target.right.parent = target.parent;
            }
        // 如果target的右子树为空，而且此时左子树不为空
        // 操作基本同上
        }else if (target.right == null){
            if (target.parent.left == target){
                target.parent.left = target.left;
            }else {
                target.parent.right = target.left;
            }
            target.left.parent = target.parent;
        // 如果左右子树都非空，则用右子树的最左子树进行替代
        }else {
            // 如果target的右子树没有左子树，直接拿右子树进行替代
            if (target.right.left == null){
                if (target.parent.left == target){
                    target.parent.left = target.right;
                }else {
                    target.parent.right = target.right;
                }
                // 指向target的parent
                target.right.parent = target.parent;
                // 接管target的左子树
                target.right.left = target.left;
            }else {
                // 寻找target的右子树的最左子树
                Node current = target;
                target = target.right;
                while (target.left != null){
                    target = target.left;
                }
                // 直接替换其值即可
                current.value = target.value;
                // 此时target为右子树的最左子树，但是target可能有右子树
                // 所以删除只有，target.parent.left需要接管target的右子树
                target.parent.left = target.right;
            }
        }
    }

本节主要学习二进制排序树的基本原理，并通过代码方式学习创建，插入，搜索最大值，最小值，指定值的节点和节点的节点. 指定值前者，后继者，删除节点等，其中删除节点可以说是最复杂，最难理解的构造二叉排序树，最好在学习过程中结合特定图片，然后手动演示整个过程处理

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-255931-2.html