toString-Methode für binäre Suchbaum

Question

Bitte helfen Sie mir meinen Code zu beheben.

Für die toString Verfahren wird die Zeichenfolge sollte als

{currentData, leftSubtree, rightSubtree} 

Ein leerer Baum formatiert werden soll eine leere Menge von Brackets {} zurückzukehren.

für die JUnit-Test Ich erhalte:

Expected: {5, {0, {-5, {}, {}}, {3, {}, {}}}, {10, {7, {}, {}}, {13, {}, {}}}} 
Actual: {5, {0, {-5, {}, {3, {}, {}, {10, {7, {}, {13, {}, {}, {}} 

Dies ist mein Code:

public String toString() { 
    StringBuffer string = new StringBuffer("{"); 
    toString(root, string); 
    string.append("}"); 
    return string.toString(); 
} 

private void toString(BSTNode<T> node, StringBuffer string) { 

    if (node != null) { 
     string.append(node.getData()); 
     if (node.getLeft() != null) { 
      string.append(", " + "{"); 
      toString(node.getLeft(), string); 
     } 
     if (node.getRight() != null) { 
      string.append(", " + "{"); 
      toString(node.getRight(), string); 
     } 
    } 
    string.append(", {}"); 
} 

Dank !!

Answer 1

Ihr Code fügt { hinzu, bevor er sich rekursiv aufruft, fügt jedoch } bei der Rückkehr nicht hinzu. Dies gilt für beide Rekursionsaufrufe.

Außerdem hängt Ihr Code unbedingt , {} an, auch für nicht leere Bäume.

---

Stattdessen schreiben Sie Ihre rekursive Methode genau das zu tun, was Sie gesagt:

• Format als {currentData, leftSubtree, rightSubtree}
• Format leeren Baum als {}

Sie es nicht die Anrufer machen Job, um die {} um den Wert hinzuzufügen, denn das wird die Logik duplizieren (DRY: nicht wiederholen Yourse lf).

Die erwartete Ausgabe zeigt auch, dass ein Blattknoten als {value, {}, {}} formatiert werden sollte, nicht als {value}, was Ihr Code mit diesen zusätzlichen if Anweisungen tut.

Verwenden Sie auch nicht StringBuffer, verwenden Sie StringBuilder, und die rekursive Methode kann static sein.

@Override 
public String toString() { 
    StringBuilder string = new StringBuilder(); 
    toString(this.root, string); 
    return string.toString(); 
} 
private static <T> void toString(BSTNode<T> node, StringBuilder string) { 
    string.append('{'); 
    if (node != null) { 
     string.append(node.getData()); 
     string.append(", "); 
     toString(node.getLeft(), string); 
     string.append(", "); 
     toString(node.getRight(), string); 
    } 
    string.append('}'); 
} 

Wenn Sie die rekursive Methode machen die StringBuilder zurückkehren, können Sie den Code kleiner werden, wenn Sie Ihren Code wie kondensieren. Es macht keinen Unterschied, funktional oder leistungsmäßig. Es liest besser, wenn Sie die Parameter umdrehen.

@Override 
public String toString() { 
    return toString(new StringBuilder(), this.root).toString(); 
} 
private static <T> StringBuilder toString(StringBuilder string, BSTNode<T> node) { 
    string.append('{'); 
    if (node != null) { 
     string.append(node.getData()); 
     toString(string.append(", "), node.getLeft()); 
     toString(string.append(", "), node.getRight()); 
    } 
    return string.append('}'); 
}