Java binäre Suchbaum löschen rekursive Rückkehr entfernt Element

Question

Dies ist mein Code im Moment. Ich weiß nicht, wie ich das entfernte Element zurückgeben soll. Im Moment gibt es die neue Wurzel des Baumes zurück. Können Sie bitte einige Hinweise geben? Vielen Dank.

public SomeDataType remove(String key) { 
    Node removed = remove(root, key); 
    if (removed != null){ 
     return removed.data; 
    } 
    return null; 
} 
// TO DO: RETURN REMOVED NODE 
private Node remove(Node n, String key) { 
    if (n == null) { 
     return null; 
    } 
    else if (n.data.getKey().compareTo(key) < 0){ 
     n.right = remove(n.right, key); 
    } 
    else if (n.data.getKey().compareTo(key) > 0){ 
     n.left = remove(n.left, key); 
    } 
    else{ 
     if (n.right != null){ 
      SomeDataType successor = leftMost(n.right).data; 
      n.data = successor; 
      n.right = remove(n.right, successor.getKey()); 
     } 
     else{ 
      n = n.left; 
     } 
    } 
    return n; 
} 
private Node leftMost(Node n) { 
    if (n.left == null){ 
     return n; 
    } 
    else{ 
     return leftMost(n.left); 
    } 
} 

Answer 1

In Ihrer Wrapper-Methode erstellen Sie eine Variable zu halten Schlüssel und dann zurück.

public SomeDataType remove(String key) { 
    E data = key //E is a generic data type 
    Node removed = remove(root, key); 
    if (removed != null){ 
     return data; 
    } 
    return null;