從二叉搜索樹中刪除節點

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; 
     } 
    }