バイナリ検索ツリーからノードを削除する

Question

deleteNodeメソッドを呼び出すと、バイナリ検索ツリープログラムは何も削除していないようです。 BSTは完全に構築されており、機能しないノード部分を削除するだけです。私は、次のように私deleteNodeメソッドを実装私BinarySearchTreeクラスで

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()); 

：私はこのように私のメインからそれを呼び出すこれはあなたの唯一の問題であるかどうかわから

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) 

つまり、2つの「and」操作には&の1つしかありません。

Answer 2

私はあなたが

ケース1処理していないと思う：削除ノードがちょうど1子

---

他を持っている：削除ノードが葉ノード

ケース2でありますもし部分がこのようなものでなければならない。

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方法は、削除するノードのINORDERの後継者を見つけることです。

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のコピーを作成します

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

。そのコピーを変更しても元のノードには影響しません。また、valueをコンストラクタに渡すだけなので、コピーにはleftまたはrightが設定されていない可能性があります。なぜコピーが必要だと思いますか？結局のところ、あなたはここで1を作成しないのいずれか：

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