数据结构之二叉搜索树的删除(Java实现)

提示：这里可以添加要学的内容
明白思路和原理，以及整个流程。

题目网址ALDS1_8_C
因为没有合适的独立题目的代码给大家展示，我这里只单独讲一下如何删除和相关的代码。
二叉搜索树是严格遵循左子树比根节点小，右子树比根节点大的二叉树。所以对于删除有严格规定的树的节点，不能随便的删除就完事。我们要根据树的节点的身份不同来确定不同的删除规则。

直接删除就好

这种情况需要判断被删除的节点是其父节点的左节点还是右节点。如果是左节点，需要将被删除节点的子节点作为其父节点新的左节点。右节点同理

这种情况比较麻烦，大家也经常被这种情况给搞乱。删除了一个节点之后，我们需要从树种找到一个节点来代替当前节点，从而保证树结构的完整和稳定。那么问题来了，究竟找哪个节点呢？根据二叉搜索树的定义得知，被删除节点的右子树上最左下角的节点是在比被删除节点大的节点中最小的。我们可以通过中序遍历来得知。如果将这个节点拿来代替被删除节点，那么树的结构仍会保持稳定。
思路明白了，那就开始实现。

void Delete(int data){}//返回删除元素后的头结点
private Node _delete(Node node, int data){}//返回操作中不断更新的节点

if(node == null)
    return null;
if(data < node.key)
    node.left = _delete(node.left,data);
else if(data > node.key)
    node.right = _delete(node.right,data);

如果node为null，就返回null。如果要删除的数据小于当前node.key，那么被删除的节点就会在node.left上，所以我们需要对node.left进行更新，右子树亦然。

else{
    if(node.left == null)
        return node.right;
    if(node.right == null)
        return node.left;
    Node minNode = minNode(node.right);
    node.key = minNode.key;
    node.right = _delete(node.right,minNode.key);
}

如果要删除的节点已经找到，那么就判断如果左子树为空就返回右子树，右子树亦然。如果都不为空，那么就需要找该节点右子树上的最左下角的节点。然后将该点的值赋给了要删除的节点，我们当前要删除节点的任务已经完成了。但是最左下角的节点在树中存在了两次，所以我们又要从当前节点的右子树出发，删除最左下角的节点。

private Node minNode(Node node) {
    while(node.left != null)
        node = node.left;
    return node;
}

不断遍历左子树，直到左子树为空，返回。
是不是很简单呢？

package AizuOJ.BinarySearchTree;

import java.util.Scanner;

public class Insertion {

    public static void main(String[] args) {
        Tree tree = new Tree();
        Scanner in = new Scanner(System.in);
        int n;
        n = in.nextInt();
        for(int i=0;i child.key)
                child = child.right;
            else
                child = child.left;
        }
        node.parent = parent;
        if(parent == null)
            this.root = node;
        else if(node.key < parent.key)
            parent.left = node;
        else
            parent.right = node;
        return node;
    }
    void InOrder(Node node)
    {
        if(node == null)
            return;
        InOrder(node.left);
        System.out.print(" "+node.key);
        InOrder(node.right);
    }
    void PreOrder(Node node)
    {
        if(node == null)
            return;
        System.out.print(" "+node.key);
        PreOrder(node.left);
        PreOrder(node.right);
    }
    Node Find(int x,Node node)
    {
        if(node == null)
        {
            return null;
        }
        if(node.key == x)
            return node;
        else if(node.key < x)
            return Find(x,node.right);
        else
            return Find(x,node.left);
    }
//    Node Minimum(Node x){
//        while(x.left != null)
//            x = x.left;
//        return x;
//    }
//    Node getSuccessor(Node x)
//    {
//        if(x.right != null)
//            return Minimum(x.right);
//        Node y = x.parent;
//        while(y != null && x == y.right)
//        {
//            x = y;
//            y = y.parent;
//        }
//        return y;
//    }
//    void Delete(Node z)
//    {
//        Node y,x;
//        if(z.left == null || z.right == null)
//        {
//            y = z;
//        }else
//            y = getSuccessor(z);
//        if(y.left != null){
//            x = y.left;
//        }else{
//            x = y.right;
//        }
//        if(x != null)
//            x.parent = y.parent;
//        if(y.parent == null) {
//            root = x;
//        }else {
//            if(y == y.parent.left) {
//                y.parent.left = x;
//            }else {
//                y.parent.right = x;
//            }
//        }
//        if(y != z) {
//            z.key = y.key;
//        }
//    }
    void Delete(int data){
        root = _delete(root,data);
    }

    private Node _delete(Node node, int data) {
        if(node == null)
            return null;
        if(data < node.key)
            node.left = _delete(node.left,data);
        else if(data > node.key)
            node.right = _delete(node.right,data);
        else{
            if(node.left == null)
                return node.right;
            if(node.right == null)
                return node.left;
            Node minNode = minNode(node.right);
            node.key = minNode.key;
            node.right = _delete(node.right,minNode.key);
        }
        return node;
    }

    private Node minNode(Node node) {
        while(node.left != null)
            node = node.left;
        return node;
    }
}