java - 二叉搜索树实现和java

Question

我正在尝试使用 Cormen 的伪代码实现 BST 算法，但遇到了问题。

这是我的节点代码:

public class Node {
    Node left;
    Node right;
    int value;

    Node(int value){
        this.value = value;
        this.left = null;
        this.right = null;  
    }
}

对于 Bstree:

public class Btree {
    Node root;

    Btree(){
        this.root = null;
    }

    public static void inorderWalk(Node n){
        if(n != null){
            inorderWalk(n.left);
            System.out.print(n.value + " ");
            inorderWalk(n.right);
        }
    }

    public static Node getParent(Btree t, Node n){
        Node current = t.root;
        Node parent = null;


        while(true){
            if (current == null)
                return null;

            if( current.value == n.value ){
                break;
            }

            if (current.value > n.value){
                parent = current;
                current = current.left;
            }
            else{ //(current.value < n.value)
                parent = current;
                current = current.right;
            }       
        }
        return parent;
    }


    public static Node search(Node n,int key){
        if(n == null || key == n.value ){
            return n;
        }
        if(key < n.value){
            return search(n.left,key);
        }
        else{
            return search(n.right,key);

        }
    }

    public static Node treeMinimum(Node x){
        if(x == null){
            return null;
        }


        while(x.left != null){
            x = x.left;
        }
        return x;
    }

    public static Node treeMaximum(Node x){
        if(x == null){
            return null;
        }

        while(x.right != null){
            x = x.right;
        }
        return x;   
    }

    public static Node treeSuccessor(Btree t,Node x){
        if (x.right == null){
            return treeMinimum(x.right);
        }
        Node y = getParent(t,x);
        while(y != null && x == y.right){
            x = y;
            y = getParent(t,y);
        }
        return y;   
    }

    public static Btree insert(Btree t,Node z){
        Node y = null;
        Node x = t.root;

        while(x != null){
            y = x;
            if(z.value < x.value)
                x = x.left;
            else
                x = x.right;
        }
        Node tmp = getParent(t,z);
        tmp = y;
        if(y == null){
            t.root = z;
        }
        else if(z.value < y.value)
            y.left = z;
        else
            y.right = z;

        return t;
    }


    public static Btree delete(Btree t,Node z){
        Node y,x;
        if (z.left == null || z.right == null)
            y = z;
        else
            y = treeSuccessor(t,z);

        if (y.left != null)
            x = y.left;
        else
            x = y.right;
        if (x != null){
            Node tmp = getParent(t,x);
            tmp = getParent(t,y);
        }

        if (getParent(t,y) == null ){
            t.root = x;
        }
        else{
            if( y == getParent(t,y).left ){
                getParent(t,y).left = x;
            }
            else{
                getParent(t,y).right = x;

            }
    }
        if(y != z){
            z.value = y.value;
        }
    return t;
}

public static void main(String[] args){
    Btree test = new Btree(); 
    Node n1 = new Node(6);
    Node n2 = new Node(3);
    Node n3 = new Node(9);
    Node n4 = new Node(1);
    Node n5 = new Node(16);
    Node n6 = new Node(4);
    Node n7 = new Node(2);
    Node n8 = new Node(11);
    Node n9 = new Node(13);


    test = insert(test,n1);
    test = insert(test,n2);
    test = insert(test,n3);
    test = insert(test,n4);
    test = insert(test,n5);
    test = insert(test,n6);
    test = insert(test,n7);
    test = insert(test,n8);
    test = insert(test,n9);
    inorderWalk(test.root);
    System.out.println();
    test = delete(test,n8);
    inorderWalk(test.root);

    System.out.println();
    test = delete(test,n5);
    inorderWalk(test.root);

    System.out.println();
    test = delete(test,n2);
    inorderWalk(test.root);

    System.out.println();
    test = delete(test,n1);
    inorderWalk(test.root);




}

}

主要问题是删除部分，有时它按预期工作，有时错误地删除，有时空指针异常。可能是什么问题？

注意:这不是作业

Answer 1

您的代码存在一些直接问题:您的 treeSuccessor 以

开头

    if (x.right == null){
        return treeMinimum(x.right);
    }

当然应该是 if (x.right != null)。

您的insert 代码有以下几行

    Node tmp = getParent(t,z);
    tmp = y;

你分配给 tmp 并立即再次分配给它的地方。在我看来你根本不需要这些行，因为你不再使用 tmp 了。此时，y 是插入子节点 z 的节点，因此只需删除这些行即可。

同样，在 delete 中，您有以下行

    if (x != null){
        Node tmp = getParent(t,x);
        tmp = getParent(t,y);
    }

你实际上什么都不做，因为 tmp 在这段代码之外是不可见的。此外，在 delete 中，您重复表达式 getParent(t,y)，这可能是一个昂贵的操作，因此您应该只计算一次并将其分配给一些变量。

但总的来说，您的代码虽然看起来是正确的(可能除了 delete 之外，我不完全理解它但看起来很可疑)，但与典型的二叉树代码不太相似。您实际上不需要 getParent 和 treeSuccessor 方法来实现 search、insert 和 delete 。 search 的基本结构也适用于其他结构，只需进行以下修改:

• 使用 insert，当您到达 null 链接时，不会返回 null，而是将元素插入该点
• 使用delete，当您找到该元素时，如果它只有一个(或没有)子元素，则将其替换为该子元素，如果它有两个子元素，则将其替换为最大的左子树或右子树的最小值

这两者还需要您在下降到树中时跟踪父节点，但这是您需要对搜索 进行的唯一修改。特别是，永远不需要在树中向上移动(treeSuccessor 会这样做)。