返回树的中序字符串

Question

编辑 这已通过使用本线程中建议的 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;
    }

Answer 1

Java 中的字符串是不可变的。您不是将新字符串连接到旧字符串，而是创建新字符串并使

string

变量指向它。结果是您有许多不相关的字符串，并且

string

变量在不同的时间点指向它们。

您需要将可变对象传递给您的函数，例如

StringBuilder

。该解决方案还有一个额外的优点，那就是效率更高，因为您可以避免不必要的对象分配。

Answer 2

如果您想通过字符串连接来做到这一点，那么您的第二个示例几乎可以工作 - 问题只是您丢弃了递归调用的结果。

/**
 * 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 的内部调整大小期间可能会复制多次（因此，如果可以的话）在实际转换之前估计最终大小，创建一个足够大的 StringBuilder）。

Answer 3

尝试使用 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将参数传递给方法的方式以及为什么字符串不可变性是一个问题你的原始代码。 问候， 索林。

Answer 4

线路

string += content;

将新的 String 对象影响到字符串变量。它不会改变原始 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);
}

Answer 5

节点类

public static class Node {

    int key;
    int nodeHeight;
    Node left;
    Node right;

    public Node(int key) {
        this.key = key;
        this.nodeHeight = 1; // Initial Height will always be one
    }

    public Node getMin() {
        //IF current node has missing left, that means this is the last item at left
        if (left == null)
            return this;
        else
            return left.getMin();// Rerun the same function on current node's left
    }
}

实施：

public class AVL {

    Node root;

    public AVL() {
    }

    String getInOrderString() {
       return getInOrderString(root);
    }

    private String getInOrderString(Node node) {
      if (node == null) return "";
      return getPreOrderString(node.left) + node.key + " " + getPreOrderString(node.right);
    }
}