Удаление узла из дерева двоичного поиска

Question

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

Я понимаю, как удалить узел с одним ребенком или без детей, и я думаю, что мой код верен для этих методов. Моя проблема заключается в удалении узла с двумя детьми. Я не могу заставить это работать правильно. Любая помощь или совет приветствуются.

public void DeleteNode(int number) { 
     if (Root == null) 
     { 
      JOptionPane.showMessageDialog(null," Tree Empty, can not delete ", JOptionPane.WARNING_MESSAGE); 
       return; 
     } 
     Node child = Root; 
     Node parent = Root; 

     while (number != child.data) { 
      if (number < child.data) 
      { 
       parent = child; 
       child = child.left; 
      } 
      else if (number > child.data) 
      { 
       parent = child; 
       child = child.right; 
      } 
      if(child == null){ 
       JOptionPane.showMessageDialog(null," Number not found",JOptionPane.WARNING_MESSAGE); 
         return; 
      } 
     } 

     if(child.right == null && child.left == null) 
     { 
      hasNoChildren(child, parent); 
     } 
     else if(child.left != null && child.right != null) 
     { 
      hasTwoChildren(child, parent); 
     } 
     else if (child.right != null && child.left == null) 
     { 
      hasRightChild(child, parent); 
     } 
     else if (child.left != null && child.right == null) 
     { 
      hasLeftChild(child, parent); 
     } 
} 

Это мой метод удаления узла с двумя детьми

public void hasTwoChildren(Node child, Node parent) 
{ 
    Node temp = null; 
    if(child.data < parent.data){ 
     Node childorg = child; 
     temp = child; 
     child = child.left; 
     while(child.right != null){ 
      temp = child; 
      child = child.right; 
     } 
     childorg.data = child.data; 
     if (child.left != null && child.right == null) 
     { 
      hasLeftChild(child, temp); 
     }else{ 
      temp.right = null; 
     } 
    } 
    else 
    { 
     Node childorg = child; 
     temp = child; 
     child = child.right; 
     while(child.left != null){ 
      temp = child; 
      child = child.left; 
     } 
     childorg.data = child.data; 
     if (child.left != null && child.right == null) 
     { 
      hasRightChild(child, temp); 
     }else{ 
      temp.left = null; 
     } 
    } 
} 

Это мои методы удаления узла без детей или одного ребенка

public void hasNoChildren(Node child, Node parent) 
{ 
    if(child.data == Root.data) 
    { 
     Root = null; 
    } 
    else if(child.data < parent.data){ 
     parent.left = null; 
    }else{ 
     parent.right = null; 
    } 
} 
public void hasLeftChild(Node child, Node parent){ 
    if(child.data < parent.data){ 
      parent.left = child.left; 
    }else{ 
     parent.right = child.left; 
    } 
} 

public void hasRightChild(Node child, Node parent){ 
    if(child.data < parent.data){ 
      parent.left = child.right; 
    }else{ 
     parent.right = child.right; 
    } 
} 

Answer 1

Вы должны следовать delete by merging подход при удалении узла с left и right детей

Ваш hasTwoChildren() метод с delete by merging логикой

public void hasTwoChildren(Node child, Node parent) { 
    Node rightNode = child.right; 
    Node leftNode = child.left; 

    // Delete child 
    if (child.val < parent.val) 
     parent.left = leftNode; 
    else 
     parent.right = leftNode; 

    // Travel to the right most node of the leftNode 
    Node tmp = leftNode; 
    while (tmp.right != null) 
     tmp = tmp.right; 

    // set the rightNode 
    tmp.right = rightNode; 
} 

Answer 2

Вот полное бинарное дерево реализация удаления для всех возможных случаев:

public boolean delete(Node nodeToDelete) { 
    boolean succes = false; 
    Node nodeToRemove = findTheNodeToDelete(nodeToDelete); 
    if (nodeToRemove == null) { 
     return succes; 
    } 
    // case1; If the node has no children 
    if (nodeToRemove.left == null && nodeToRemove.right == null) { 
     if (nodeToRemove.parent.left.data == nodeToDelete.data) { 
      nodeToRemove.parent.left = null; 
      nodeToRemove = null; 
      succes = true; 
      return succes; 
     } else if (nodeToRemove.parent.right.data == nodeToDelete.data) { 
      nodeToRemove.parent.right = null; 
      nodeToRemove = null; 
      succes = true; 
      return succes; 

     } 
     // case 2: if it has only one children 
    } else if ((nodeToRemove.left == null && nodeToRemove.right != null) 
      || (nodeToRemove.right == null && nodeToRemove.left != null)) { 
     if (nodeToRemove.left != null) { 
      nodeToRemove.parent.left = nodeToDelete.left; 
      nodeToDelete = null; 
      succes = true; 
      return succes; 

     } else if (nodeToRemove.parent.right != null) { 
      nodeToRemove.parent.right = null; 
      nodeToRemove = null; 
      succes = true; 
      return succes; 
     } 
    } 
    // case 3 : 
    if (nodeToRemove.left != null && nodeToRemove.right != null) { 

     Node minLeftNode = findTheLeftMostNodeFromtheRightSubTree(nodeToRemove.right); 

     System.out.println("----" + minLeftNode.data); 

     // Now if the parent of the node is not null that means it is the 
     // root 
     // assign the left mode min as root and say 
     // min.right=notetoRemove.right; 

     // derefrence the min node /remove from the tree 
     minLeftNode.parent.left = null; 
     minLeftNode.parent = null; 
     Node parentofTheNodeToDelete = nodeToRemove.parent; 

     minLeftNode.parent = parentofTheNodeToDelete; 
     Node rightOfNodeToDelete = nodeToRemove.right; 
     Node leftofNodeToDelete = nodeToRemove.left; 

     if (parentofTheNodeToDelete == null) { 
      root = minLeftNode; 
     } else { 
      if (parentofTheNodeToDelete.right.data == nodeToDelete.data) { 
       parentofTheNodeToDelete.right = minLeftNode; 

      } else if (parentofTheNodeToDelete.left.data == nodeToDelete.data) { 
       parentofTheNodeToDelete.left = minLeftNode; 

      } 

     } 
     minLeftNode.right = rightOfNodeToDelete; 
     minLeftNode.left = leftofNodeToDelete; 
     nodeToRemove = null; 
    } 

    return succes; 
}