二叉搜索树 toString Java

Question

我已经为 BST 实现了 toString 方法，但看起来它可以工作但不稳定。例如对于这棵树 toString 工作正常：但对于这个，这是错误的

谁能帮忙，这是怎么回事？

@Override
    public String toString() {
        return "(" + toStringB(new StringBuilder(), root()).toString() + ")";
    }

    private StringBuilder toStringB(StringBuilder string, Node<E> node) {
        if (node != null) {
            string.append(node.getElement());
            if (left(node) != null) {
                toStringB(string.append(" ("), left(node));
            }
            if (right(node) != null) {
                toStringB(string.append(", "), right(node));
                string.append(')');
            }
        }
        return string;
    }

Answer 1

你的问题出在这里：

        if (left(node) != null) {
            toStringB(string.append(" ("), left(node));
        }
        if (right(node) != null) {
            toStringB(string.append(", "), right(node));
            string.append(')');
        }

如果你有一个左节点，但没有右节点，你将追加(left。如果你有一个没有左节点的右节点，你将追加 , right)。这会给您不正确匹配的括号和杂散逗号。

我想指出，您的 "works fine" 示例实际上也不正确：

(10 (7 (3 (2, 5), 9), 10, 30 (11 (10)))

让我们隐藏 7 和 30 下的节点：

(10 (7 (...), 10, 30 (...))

您的根节点 10 有 3 个子节点 7、10 和 30。这不是二叉树！

哦，还有不平衡的括号。

二叉搜索树 toString Java

Binary Search Tree toString Java

java

tostring

binary-search-tree