3

编辑这已通过使用此线程中建议的 StringBuilder 解决。谢谢 :D

你好,

我有一棵树,并试图按顺序返回内容的字符串。

我目前可以用这样的东西打印出树:

    public void inOrder() {
        if (left != null) left.inOrder();
        System.out.print(content + " ");
        if (right != null) right.inOrder();
    }

但我想要做的是返回字符串(而不是在递归时打印出每个节点的内容),我不知道该怎么做。我尝试了下面代码的许多变体,但它只返回它在递归中找到的最后一个元素。

 public String inOrder(String string) {
        if (left != null) left.inOrder(string);
        string += content;
        if (right != null) right.inOrder(string);

        return string;
    }
4

4 回答 4

5

字符串在java中是不可变的。您不是将新字符串连接到旧字符串,而是创建新字符串并使string变量指向它。结果是您string在不同的时间点有许多不相关的字符串和指向它们的变量点。

您需要将可变对象传递给您的函数,例如StringBuilder. 这个解决方案还有一个额外的优势,那就是它更高效,因为您避免了不必要的对象分配。

于 2011-02-22T11:06:16.873 回答
3

如果您想使用字符串连接来执行此操作,那么您的第二个示例几乎可以工作 - 问题只是您丢弃了递归调用的结果。

/**
 * creates an Inorder-string-view of this tree and appends it to the given string.
 * @return the new String.
 */
public String inOrder(String string) {
    if (left != null)
        string = left.inOrder(string);
    string += content;
    if (right != null)
        string = right.inOrder(string);
    return string;
}

但这(对于较大的树)效率很低,因为+=实际上每个都创建了一个新字符串,复制了string和的字符content- 因此每个内容字符串实际上被复制the number of later nodes(按顺序)次(+1)。稍微好一点的方法是:

public String inOrder() {
    String leftS; String rightS;
    if (left != null)
       leftS = left.inOrder();
    else
       leftS = "";
    if (right != null)
       rightS = right.inOrder();
    else
       rightS = "";
    return leftS + content + rightS;
}

或者更短一点:

public String inOrder {
   return
      (left != null ? left.inOrder() : "") +
      content +
      (right != null ? right.inOrder() : "");
}

现在每个内容字符串只复制它上面的节点数(+1),这对于“通常”(不是非常不平衡)的树来说要小得多。(这个变体也可以很容易地并行化。)

但实际上,StringBuilder 版本通常是首选版本,因为它只复制每个内容字符串一次(将其附加到 StringBuilder 时),并且可能在 StringBuilder 的内部调整大小期间复制更多次(所以如果你可以估计最终size 在实际转换之前,创建一个足够大的 StringBuilder)。

于 2011-02-22T14:10:33.050 回答
2

字符串在 Java 中是不可变的,当您向字符串添加内容时,会创建一个新对象。因此,更改在方法范围之外是不可见的。

尝试使用 StringBuilder 而不是 String:

public StringBuilder inOrder(StringBuilder string) {
        if (left != null) left.inOrder(string);
        string.append(content);
        if (right != null) right.inOrder(string);

        return string;
}

您可以在这里阅读:http ://www.javaworld.com/javaqa/2000-05/03-qa-0526-pass.html以了解 Java 将参数传递给方法的方式以及为什么字符串不变性是原始代码中的一个问题.

问候,索林。

于 2011-02-22T11:07:36.793 回答
0

Java 是按值传递的。此方法不能更改对传递给方法的对象的引用。你可以改变一个对象的内容,但你不能用字符串来做到这一点,因为它们是不可变的(它们的内容不能改变)。

线

string += content;

影响字符串变量的新字符串对象。它不会更改原始 String 对象的内容。

您需要将 StringBuilder 实例传递给您的方法,并附加到此 StringBuilder:

public String inOrder() {
    StringBuilder strinBuilder = new StringBuilder();
    postOrder(stringBuilder);
    return stringBuilder.toString();
}

private void postOrder(StringBuilder stringBuilder) {
    if (left != null) left.postOrder(stringBuilder);
    if (right != null) right.postOrder(stringBuilder);
}
于 2011-02-22T11:06:55.780 回答