BST：Javaで2人の子供がいるノードを削除する

Question

BSTでノードを削除するための再帰的アルゴリズムを実装しましたが、削除するノードに2つの子がある場合には正しく動作しないようです。ここでは、ノードを削除するために使用される方法のためのコードは次のとおりです。

public boolean delete(int val) 
{ 


    Node nodeToBeDeleted = find(val); 
    if(nodeToBeDeleted != null) 
    { 
     //case 1: node has no children 
     if(nodeToBeDeleted.leftChild == null && nodeToBeDeleted.rightChild == null) 
      deleteCase1(nodeToBeDeleted); 

     //case 3: node has two children 
     else if(nodeToBeDeleted.leftChild != null && nodeToBeDeleted.rightChild != null) 
     { 
      deleteCase3(nodeToBeDeleted); 
     } 

     //case 2: node has one child 
     else if(nodeToBeDeleted.leftChild != null) 
     { 
      //case 2 where left child should be deleted 
      deleteCase2(nodeToBeDeleted); 
     } 

     else if(nodeToBeDeleted.rightChild != null) 
     { 
      //case 2 where right child should be deleted 
      deleteCase2(nodeToBeDeleted); 
     } 

     return true; 
    } 
    else 
     return false; 
} 

そしてここdeleteCase1、deleteCase2とdeleteCase3方法：

private void deleteCase1(Node nodeToBeDeleted) 
{ 
     //check if node to be deleted is a left or a right child of the parent of the node to be deleted 
     if(nodeToBeDeleted.parent.leftChild == nodeToBeDeleted) 
     { 
      nodeToBeDeleted.parent.leftChild = null; 
     } 
     else if(nodeToBeDeleted.parent.rightChild == nodeToBeDeleted) 
     { 
      nodeToBeDeleted.parent.rightChild = null; 
     } 
} 

ここに方法を見つける：

public Node find(int val) 
{ 
    if(root != null) 
    { 
     return findNode(root, new Node(val)); 
    } 

    return null; 
} 

private Node findNode(Node search, Node node) 
{ 
    if(search == null) 
     return null; 

    if(search.data == node.data) 
    { 
     return search; 
    } 
    else 
    { 
     Node returnNode = findNode(search.leftChild, node); 

     if(returnNode == null) 
     { 
      returnNode = findNode(search.rightChild, node); 
     } 

     return returnNode; 
    } 
} 

minLeftTreversal方法：

を

private Node minLeftTreversal(Node node) 
{ 
    if(node.leftChild == null) 
     return node; 

    return minLeftTreversal(node.leftChild); 
} 

ツリーの構造は次のようになります。 enter image description here

アルゴリズムは75を削除すると機能しますが、25を削除しようとすると処理が中断します。

ありがとうございます！

Answer 1

public boolean delete(int val)で文が{と}

 //case 1: node has no children 
     if(nodeToBeDeleted.leftChild == null && nodeToBeDeleted.rightChild == null) 
     { // <---- ADD THIS 
      deleteCase1(nodeToBeDeleted); 
     } // <---- AND ADD THIS 
     //case 3: node has two children 
     else if(nodeToBeDeleted.leftChild != null && nodeToBeDeleted.rightChild != null) 
     { 
      deleteCase3(nodeToBeDeleted); 
     } 

が不足している場合はあなたの最初の