метод toString для дерева двоичного поиска

Question

Пожалуйста, помогите мне исправить мой код.

Для метода toString, строка должна быть в формате

{currentData, leftSubtree, rightSubtree} 

Пустое дерево должен возвращать пустой набор скобок {}.

для теста JUnit я получаю:

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

Это мой код:

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(", {}"); 
} 

Спасибо !!

Answer 1

Ваш код добавляет { перед тем, как называть себя рекурсивно, но не возвращает } по возвращении. Это касается обоих вызовов рекурсии.

Кроме того, ваш код безоговорочно добавляет , {}, даже для непустых деревьев.

---

Вместо написать рекурсивный метод, чтобы сделать именно то, что вы сказали:

• Форматировать как {currentData, leftSubtree, rightSubtree}
• Формат пустое дерево, как {}

Не делайте это звонящих задайте, чтобы добавить {} вокруг значения, поскольку это будет дублировать логику (DRY: Do not Repeat Yourse Л.Ф.).

Ожидаемый результат также показывает, что листовой узел должен отформатировать как {value, {}, {}}, а не как {value}, что и делает ваш код с этими дополнительными if заявлениями.

Кроме того, не используйте StringBuffer, используйте StringBuilder, а рекурсивный метод может быть static.

@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('}'); 
} 

Если вы рекурсивный метод возвращает StringBuilder, ваш код может стать меньше, если вы, как конденсационные код. Не делает различий, функционально или с точки зрения производительности. Он лучше читает, если вы переворачиваете параметры.

@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('}'); 
}