2

我正在研究类的二进制搜索树，并且我的大部分代码都正确实现（我认为），尽管如果我尝试删除根节点，什么也不会发生。

有人看到我的代码有问题吗？

public class BinarySearchTree {
private Node root;
private int size = 0;

public BinarySearchTree(){
    root = null;
}

public BinarySearchTree create(){
    BinarySearchTree tree = new BinarySearchTree();
    return tree;
}

public int size(){
    return size;
}

public Node getRoot(){
    System.out.println("root: " + root.getData());
    return root;
}

public void insert(String s){
    root = insertHelper(root, s.toLowerCase());
    size++;
}
private Node insertHelper(Node n, String s){
    if(n == null){
        //root is null, make it a new node
        n = new Node(s);
    } else if(s.compareTo(n.getData()) < 0){
        //string is alphabetically less than root
        n.setLeft(insertHelper(n.getLeft(), s));
        n.getLeft().setParent(n);
    } else{
        //string is alphabetically greater than root
        n.setRight(insertHelper(n.getRight(), s));
        n.getRight().setParent(n);
    }
    return n;
}

public void delete(String s){
    deleteHelper(root, s.toLowerCase());
}
private void deleteHelper(Node n, String s){
    if(n == null){
        //nothing to delete
        return;
    }
    //found node to delete
    else if(s.equals(n.getData())){
        System.out.println("DELETED: " + n.getData());
        //check for left subtree
        //if null, replace node-to-be-deleted with
        //right subtree
        if(n.getLeft() == null){
            replace(n, n.getRight());
        } 
        //check for right subtree
        //if null, replace node-to-be-deleted with
        //left subtree
        else if(n.getRight() == null){
            replace(n, n.getLeft());
        } 
        //if it has two subtrees, find minimum value of the
        //right tree and swap the node-to-be-deleted's data with
        //the minimum node's data
        else{
            Node min = n.getRight();
            while(min.getLeft() != null){
                min = min.getLeft();
            }
            //replace with right and reset pointers
            if(min.getParent() != n){
                replace(min, min.getRight());
                min.setRight(n.getRight());
                min.getRight().setParent(min);
            } 
            //replace with left and reset pointers
            else{
                replace(n, min);
                min.setLeft(n.getLeft());
                min.getLeft().setParent(min);
            }
        }
    }
    //if it hasn't been found, recurse left
    else if(s.compareTo(n.getData()) < 0){
        deleteHelper(n.getLeft(), s);
    } 
    //then, recurse right
    else{
        deleteHelper(n.getRight(), s);
    }
}
private void replace(Node x, Node y){
    //if x is the root, set root to y
    if(x.getParent() == null){
        root = y;
    } 
    //if x is a left child, set it's parent's left child to y
    else if(x == x.getParent().getLeft()){
        x.getParent().setLeft(y);
    } 
    //if x is a right child, set it's parent's right child to y
    else{
        x.getParent().setRight(y);
    }
    //if y is not null, set y's parent to be x's parent
    if(y != null){
        y.setParent(x.getParent());
    }
}

public void destroy(){
    //wipe out the tree
    root = null;
    size = 0;
}

public boolean find(String s){
    return findHelper(root, s.toLowerCase());
}
public boolean findHelper(Node n, String s){
    if(n == null){
        System.out.println("Sorry, " + s + " is not in here.");
        return false;
    }  
    if(s.equals(n.getData())){
        System.out.println(s + " is in the tree.");
        return true;
    } else if(s.compareTo(n.getData()) < 0){
        return findHelper(n.getLeft(), s);
    } else{
        return findHelper(n.getRight(), s);
    }
}
}


public class SearchDriver {

/**
 * @param args
 */
public static void main(String[] args) {
    SearchDriver me = new SearchDriver();
    me.doIt();
}

public void doIt(){
    BinarySearchTree tree = new BinarySearchTree();

    tree.insert("marry");
    tree.insert("alpha");
    tree.insert("gamma");
    tree.insert("delta");
    tree.insert("epsilon");
    tree.insert("zeta");
    tree.insert("eta");
    tree.insert("theta");
    tree.insert("iota");
    tree.insert("kappa");
    tree.insert("lambda");
    tree.insert("beta");
    tree.insert("nu");
    tree.insert("xi");
    tree.insert("omicron");
    tree.insert("pi");
    tree.insert("rho");
    tree.insert("sigma");
    tree.insert("tau");
    tree.insert("upsilon");
    tree.insert("phi");
    tree.insert("chi");
    tree.insert("psi");
    tree.insert("omega");
    tree.printInOrder();

    tree.delete("psi");
    tree.printInOrder();

    tree.delete("marry");

    tree.printInOrder();
    tree.printPostOrder();
    }
}
4

2 回答 2

2

让我来帮助你：

  • 在IDE中构建程序
  • 在 main 方法的开头设置断点
  • 在调试器中启动您的程序
  • 在删除 root 的情况下逐步执行代码

如果您无法使用上面给出的建议解决此问题，请在此问题中评论您所坚持的具体内容。 如果您现在不花时间学习这些技能，它将在您的编程职业中永远困扰您。

于 2012-08-07T20:39:34.580 回答
1

问题在于：

if (min.getParent() != n) {
      replace(min, min.getRight());
      min.setRight(n.getRight());
      min.getRight().setParent(min);
}

这永远不会用 min 替换 n ，因此永远不会将 root 设置为其新值。

于 2012-08-07T20:41:05.780 回答