Найти метод Ancestor для дерева двоичного поиска не работает

Question

Я написал метод поиска родителя узла в C# (c-sharp), но мой код работает некорректно. Исключения: System.NullReferenceException выбрасывается, когда я пытаюсь удалить узел, родитель которого имеет значение null.

public TreeNode FindParent(int value, ref TreeNode parent) 
    { 
     TreeNode currentNode = root; 

     if (currentNode == null) 
     { 
      return null; 
     } 

     while (currentNode.value != value) 
     { 
      if (value < currentNode.value) 
      { 
       parent = currentNode; 
       currentNode = currentNode.leftChild; 

      } 
      if (value > currentNode.value) 
      { 
       parent = currentNode; 
       currentNode = currentNode.rightChild; 
      } 
     } 
     return currentNode; 

    } 


    public void Delete(int value) 
    { 
     TreeNode parent = null; 
     TreeNode nodeToDelete = FindParent(value, ref parent); 

     if (nodeToDelete == null) 
     { 
      throw new Exception("Unable to delete node: " + value.ToString()); 
     } 



      //CASE 1: Nod has 0 children. 
     if (nodeToDelete.leftChild == null && nodeToDelete.rightChild == null) 
     { 

       if (parent.leftChild == nodeToDelete) 
       { 
        parent.leftChild = null; 
       } 

       if (parent.rightChild == nodeToDelete) 
       { 
        parent.rightChild = null; 
       } 
       count--; 
       return; 

      } 
      //CASE 2: Nod has 1 left || 1 right barn 
      if (nodeToDelete.leftChild == null && nodeToDelete.rightChild != null) 
      { 
       nodeToDelete.rightChild = parent.rightChild; 
       nodeToDelete = null;  
       count--; 
       return; 

      } 

      if (nodeToDelete.leftChild != null && nodeToDelete.rightChild == null) 
      { 
       nodeToDelete.leftChild = parent.leftChild; 
       nodeToDelete = null; 
       count--; 
       return; 

      } 

      //CASE 3: Nod has 2 children 
      if (nodeToDelete.rightChild != null && nodeToDelete.leftChild != null) 
      { 
       TreeNode successor = LeftMostNodeOnRight(nodeToDelete, ref parent); 
       TreeNode temp = new TreeNode(successor.value); 
       if (parent.leftChild == successor) 
       { 
        parent.leftChild = successor.rightChild; 
       } 
       else 
       { 
        parent.rightChild = successor.rightChild; nodeToDelete.value = temp.value; 
       } 
       count--; 
       return; 

      } 

    } 

Answer 1

, так как вы используете рекурсию, вам не нужен родительский узел для удаления узла в бинарном дереве поиска, здесь метод удаления, где вы передаете в междунар и корень

private BinaryTreeNode remove (int value, TreeNode t){ 

    if(t==null) 
     return t; // not found; do nothing 

    if(value < t.value){ 
     t.left = remove(x,y,t.left); 
    } 
    else if (value > t.value){ 
     t.right = remove(x,y,t.right); 
    } 
    else if(t.left!=null && t.right != null) // two children 
    { 
     t.info = findMin(t.right).info; 
     remove(t.info.getLastName(),y,t.right); 
    } 
    else{       // one child 
     if (t.left != null) { 
       t = t.left; 
     }  
     else{ 
      t = t.right; 
     } 
    } 
    return t; 

} 

Edit ----------- findMin (найти минимальный узел в бинарном дереве поиска)

private BinaryTreeNode findMin (BinaryTreeNode t){ // recursive 
     if(t == null) 
      return null; 
     else if (t.left == null) 
      return t; 
     return findMin(t.left); 
    } 

Так вы берете мин значение из правого поддерева, и сделать его родителем т. Информация. Следуйте этим диаграммам. Мы удаляем узел 25 двумя детьми.