Используете рекурсивный метод для возврата строки inorder в java? - PullRequest
Новая
       38

Используете рекурсивный метод для возврата строки inorder в java?

0 голосов
/ 30 января 2020

Я хочу сделать упорядоченную трансверсаль двоичного дерева. Я сделал этот метод: 

public String inorder()
    {
        String inorder = "";
        return recrInorder(this.root, inorder);
    }

тогда у меня есть вспомогательный метод: 

private String recrInorder(Node curr,String string)
    {
        if(curr == null)
        {
            return "";
        }
        //Go through left
        recrInorder(curr.getLeft(), string);
        string = string + curr.getData() + ", ";
        //Go through right
        recrInorder(curr.getRight(), string);
        return string;
    }

Это будет печатать только root, я хочу, чтобы весь список был напечатан.

Ответы [ 3 ]

2 голосов
/ 30 января 2020 
public String inorder() {
    return recrInorder(this.root);
}

private String recrInorder(Node curr) {
    if (curr == null) return "";
    return recrInorder(curr.getLeft()) + curr.getData() + ", " + rectInorder(curr.getRight());
}
2 голосов
/ 30 января 2020

В Java параметры передаются по значению для ссылки на объект, поэтому присвоение нового значения вашему входному параметру с именем string не изменит его значение вне этой функции.

Вам необходимо изменить свой код следующим образом это 

private String recrInorder(Node curr,String string)
{
    if(curr == null)
    {
        return string; // preserve previously calculated value
    }
    //Go through left
    string = recrInorder(curr.getLeft(), string);
    string = string + curr.getData() + ", ";
    //Go through right
    string = recrInorder(curr.getRight(), string);
    return string;
}
0 голосов
/ 30 января 2020

При наличии отношений parent, left child и right child обход дерева зависит от того, когда вы visit родительский и получили доступ к строковому значению.

Учитывая root дерева вызовите его следующим образом: 

    String s =  traverse(root, "");
    System.out.println(s);

    public static String traverse(Node n, String s) {
        if (n == null) {
            return s;
        }
        // s += n.value;  // uncomment this assignment for preorder traversal
        s = traverse(n.left,s);
        // s += n.value;  // uncomment this assignment for inorder traversal
        s = traverse(n.right,s);
        // s += n.value;  // uncomment this assignment for postorder traversal
        return s;
    }

Таким образом, в вашем методе вы можете передать флаг или enum и указать назначение на основе этого значения, тем самым адаптируя ваш метод на любой обход.

...