二叉搜索树的 toString 方法

Question

请帮助我修复我的代码。

对于toString方法，字符串的格式应为

{currentData, leftSubtree, rightSubtree}

一棵空树应该return一组空括号{}。

对于我得到的 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

您的代码在递归调用自身之前添加 {，但不会在 return 上添加 }。这适用于两个递归调用。

此外，您的代码无条件附加 , {}，即使对于非空树也是如此。

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

格式为{currentData, leftSubtree, rightSubtree}
将空树格式化为 {}

不要让调用者的工作是在值周围添加 { }，因为这会重复逻辑（DRY：不要重复自己）。

预期输出还显示叶节点的格式应为 {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('}');
}

如果您将递归方法 return 改为 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('}');
}

二叉搜索树的 toString 方法

toString method for binary search tree

java

binary-search-tree