二叉搜索树的实例和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);




}

}

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

Ps:这不是作业

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,插入元素到该点
• with delete,当你找到该元素时,如果它只有一个(或没有)子元素,则将其替换为该子元素,如果它有两个子元素,则将其替换为左子树的最大值或右子元素的最小值树

这两个都需要您在下降到树时跟踪父节点,但这是您需要进行的唯一修改search.特别是,从来没有必要在树中向上(这treeSuccessor将做).