Entfernen Sie ein Blatt aus einem BinaryTree

Question

Mein Code unten wird einen Baum mit zwei Kindern oder einem Kind entfernen. Aber ein Blatt (ein Baum mit null Kindern) kann ich nicht zu knacken scheinen. Meine BSTNode<E> enthält auch eine .parent, die ihre Eltern identifiziert. Ich bin mir nicht sicher, ob das bei dieser Implementierung helfen würde oder nicht.

@Override 
public E delete(E target) { 
    return delete(this.root, target); 
} 

private E delete(BSTNode<E> localRoot, E target) { 
    // ... Trying to delete an item that's not in the tree? 
    if (localRoot == null) { 
     return null; 
    } 

    int compareResult = c.compare(target, localRoot.data); 

    // Traverse the tree... 
    if (compareResult < 0) { 
     return delete(localRoot.left, target); 
    } else if (compareResult > 0) { 
     return delete(localRoot.right, target); 
    } else { 
     // Found the item! Oh boy here we go! 
     E retVal = localRoot.data; 

     /* 
     * Both left and right exist under the targeted node. 
     * Find the largest child under the right side of the node. 
     * Set the largest data to the 'deleted' node, then delete that node. 
     */ 
     if (localRoot.left != null && localRoot.right != null) { 
      /* 
      * Two children, find the smallest and assign it. 
      */ 
      localRoot.data = localRoot.right.data; 
      localRoot.right = findLargestChild(localRoot.right); 
     } else if (localRoot.left != null) { 
      localRoot.data = localRoot.left.data; 
      localRoot.left = findSmallestChild(localRoot.left); 
     } else if (localRoot.right != null) { 
      localRoot.data = localRoot.right.data; 
      localRoot.right = findLargestChild(localRoot.right); 
     } else { 
      /* 
      * TODO: 
      * Remove a leaf. 
      */ 
      System.out.println("Removing leaf..." + localRoot.data.toString()); 
      localRoot = null; 
     } 

     return retVal; 
    } 
} 

Answer 1

Mit localRoot.parent ich löschen konnte (null) das Kind von den localRoot ‚s Eltern. Das fühlt sich rückwärts an, aber es gibt JUnit Tests ...

private E delete(BSTNode<E> localRoot, E target) { 
    // ... Trying to delete an item that's not in the tree? 
    if (localRoot == null) { 
     return null; 
    } 

    int compareResult = c.compare(target, localRoot.data); 

    // Traverse the tree... 
    if (compareResult < 0) { 
     return delete(localRoot.left, target); 
    } else if (compareResult > 0) { 
     return delete(localRoot.right, target); 
    } else { 
     // Found the item! Oh boy here we go! 
     E retVal = localRoot.data; 

     if (localRoot.right != null) { 
      /* 
      * Assign the largest value to the tree. 
      */ 
      localRoot.data = localRoot.right.data; 
      localRoot.right = findLargestChild(localRoot.right); 
     } else if (localRoot.left != null) { 
      /* 
      * Since the largest value didn't exist, assign the smallest. 
      */ 
      localRoot.data = localRoot.left.data; 
      localRoot.left = findSmallestChild(localRoot.left); 
     } else { 
      /* 
      * Remove a leaf. 
      */ 
      System.out.println("Removing leaf or left..." + localRoot.data.toString()); 
      if (c.compare(target, localRoot.parent.left.data) == 0) { 
       localRoot.parent.left = null; 
      } else { 
       localRoot.parent.right = null; 
      } 
     } 

     return retVal; 
    } 
}