Возврат строки порядка дерева

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

Строки являются неизменяемыми в 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 передает аргументы методам и почему неизменность строк является проблемой в вашем исходном коде.

С уважением, Сорин.

Answer 4

Java передается по значению. Ссылка на объект, переданный методу, не может быть изменена этим методом. Вы можете изменить содержимое объекта, но вы не можете сделать это со строками, потому что они неизменны (их содержимое не может измениться).

Линия

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);
}