二叉查找树的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

代码在递归调用自身之前添加｛，但在返回时不添加｝。这适用于两个递归调用。

此外，您的代码无条件地追加< code >，{}，即使对于非空树也是如此。

相反，编写你的递归方法来完全按照你说的做：

< li >格式为< code>{currentData，leftSubtree，rightSubtree} < li >将空树格式化为< code>{}

不要让调用者在值周围添加< code>{ }，因为这将重复逻辑(DRY:不要重复)。

预期的输出还显示，叶节点应该格式化为< code>{value，{}，{}}，而不是< code>{value}，这是您的代码对那些额外的< code>if语句所做的。

还有，不要用< code>StringBuffer，用< code>StringBuilder，递归方法可以是< code>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('}');
}

如果您让递归方法返回< code>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('}');
}