从二叉搜索树中删除节点

Question

当我调用deleteNode方法时，我的二叉搜索树程序似乎不会删除任何东西。 BST完美地构建，它只是删除不起作用的节点部分。我把它从我的主要是这样的：

System.out.println("Please enter a number you would like to delete from the tree"); 
    temp = reader.nextLine(); 
    try { 
     int numTemp = Integer.parseInt(temp); 
     TreeNode treeTemp = bst.deleteNode(numTemp, bst.getRoot()); 
     bst.setRoot(treeTemp); 
    } 
    catch(Throwable e){ 
     System.err.println(e); 
    } 
    bst.printInBST(bst.getRoot()); 

在我BinarySearchTree类我实现我的deleteNode方法如下：

public TreeNode deleteNode(int x, TreeNode temp){ 
    if(temp != null){ 
     if(x > (int)((Integer)temp.getValue())){ 
      temp.setLeft(deleteNode(new Integer(x), temp.getLeft())); 
     } 
     else if(x < (int)((Integer)temp.getValue())){ 
      temp.setRight(deleteNode(new Integer(x), temp.getRight())); 
     } 
     else if(temp.getLeft() != null & temp.getRight() != null){ 
      TreeNode temp2 = new TreeNode(temp.getRight().getValue()); 
      while(temp2.getLeft() != null){ 
       temp2 = temp2.getLeft(); 
      } 
      temp = temp2; 
      temp.setRight(remove(temp.getRight())); 
     } 
    } 
    return temp; 
} 
public TreeNode remove(TreeNode temp){ 
     if(temp.getLeft() != null){ 
      temp.setLeft(remove(temp.getLeft())); 
      return temp; 
     } 
     else { 
      return temp.getRight(); 
     } 
} 

Answer 1

不是100％肯定，如果这是你唯一的问题，而应该：

else if(temp.getLeft() != null & temp.getRight() != null) 

实际上是：

else if(temp.getLeft() != null && temp.getRight() != null) 

即你应该有两个“和”操作时只有一个&？

Answer 2

我想你是不是处理

情况1：在删除节点是叶节点

案例2：在删除节点只是1名儿童

---

的其他如果部分应该是这样的。

else if(temp.getLeft() != null && temp.getRight() != null) // Two children 
{ 
     temp.setValue(findMin(temp.getRight()).getValue()); 
     temp.setRight (deleteNode(temp.getValue(), temp.getRight()); 
} 
else 
    temp = (temp.getLeft() != null) ? temp.getLeft() : temp.getRight(); 

return temp; 

---

的findMin方法是找到节点的序后继要被删除。

private TreeNode findMin(TreeNode t) 
{ 
     if(t == null) 
      return null; 
     else if(t.getLeft() == null) 
      return t; 
     return findMin(t.getLeft()); 
} 

---

我希望这回答你的问题。

Answer 3

书写易读的代码使得错误更容易被发现 - 无论是由您自己或其他人。第一步是选择比temp，temp2和treeTemp更富表现力的变量名称。

而且，new Integer(x)确实不需要指定int类型的方法参数。简单地使用x代替它具有相同的效果，运行时速度更快，并且可以更轻松地找到重要的代码。

至于错误，我第一个看到的是：

TreeNode temp2 = new TreeNode(temp.getRight().getValue()); 

创建该树节点的副本。更改该副本不会影响原始节点。此外，副本可能没有left或right集，因为您只将value传递给构造函数。我想知道为什么认为你需要一个副本？毕竟，你不要在这里创建一个或者：

deleteNode(new Integer(x), temp.getRight()) 

接下来，Sashwat指出，如果删除的节点具有少于2个孩子，你的代码没有做任何事情，因为没有条件在deleteNode比赛。

Answer 4

public class BSTNode { 
    … 

    public boolean remove(int value, BSTNode parent) { 
     if (value < this.value) { 
       if (left != null) 
        return left.remove(value, this); 
       else 
        return false; 
     } else if (value > this.value) { 
       if (right != null) 
        return right.remove(value, this); 
       else 
        return false; 
     } else { 
       if (left != null && right != null) { 
        this.value = right.minValue(); 
        right.remove(this.value, this); 
       } else if (parent.left == this) { 
        parent.left = (left != null) ? left : right; 
       } else if (parent.right == this) { 
        parent.right = (left != null) ? left : right; 
       } 
       return true; 
     } 
    }