Как вернуть корень дерева, которое добавляется в рекурсивно? - PullRequest
Новая
       36

Как вернуть корень дерева, которое добавляется в рекурсивно?

0 голосов
/ 03 февраля 2019

Я пытаюсь использовать связанный список, чтобы добавить строку в три с '$' в качестве завершающего символа.Однако он возвращает только последний узел дерева, а не корень дерева.Это мой код: 

public class DictionaryDLB{

    private Node root;

    private class Node{
        public char value;
        public Node next;
        public Node child;

        public Node() {}
        public Node(char value){
            this.value = value;
            this.next = null;
            this.child = null;
        }
    }
    public void add(String word){
        root = add(root, word, 0);
    }

    private Node add(Node root, String key, int d){
        char c;
        if (d != key.length()) c = key.charAt(d);
        else c = '$';
        if (root == null) root = new Node(c);
        if (d == key.length()) { return root; }
        if (c != root.value) root = add(root.next, key, d);
        return root = add(root.child, key, d+1);
    }

после завершения возвращает узел со значением $ и не имеет дочерних или следующих узлов.

1 Ответ

0 голосов
/ 03 февраля 2019

Причина в том, что вы устанавливаете root на возвращаемое значение add, прежде чем вернуть root.В результате вы получите последний экземпляр root из стека вызовов.Например, допустим, я позвонил add("hi").Вот как будет выглядеть стек вызовов функций, если предположить, что root запускается как null, 

add("hi")
root = add(root, "hi", 0)
    root = new Node('h')
    return root = add(root.child, "hi", 1)
        root = new Node('i')
        return root = add(root.child, "hi", 2)
            root = new Node('$')
            return root //Node('$')
        return root //Node('$')
    return root //Node('$')
root = root //Node('$')

Обратите внимание, что в вызовы функции передается узел со значением '$'.Причина в том, что вы устанавливаете root на возвращаемое значение add в нижней части вашего метода.Там нет необходимости делать это.Просто позвоните add, как вы делаете в данный момент, и верните root отдельно, например, так: 

private Node add(Node root, String key, int d){
    char c;
    if (d != key.length()) c = key.charAt(d);
    else c = '$';
    if (root == null) root = new Node(c);
    if (d == key.length()) { return root; }
    if (c != root.value) root.next = add(root.next, key, d);
    else root.child = add(root.child, key, d+1);
    return root;
}

Теперь вам нужно установить результат add либо в root.next, либо в root.child.Причина этого заключается в том, что узел, созданный при вызове add, должен быть передан обратно, чтобы установить следующий или дочерний указатели.Чтобы лучше проиллюстрировать это, давайте повторно запустим пример трассировки стека для add("hi"). 

add("hi")
root = add(root, "hi", 0)
    root = new Node('h')
    root.child = add(root.child, "hi", 1)
        root = new Node('i')
        root.child = add(root.child, "hi", 2)
            root = new Node('$')
            return root //Node('$')
        root.child = root //Node('$')
        return root //Node('i')
    root.child = root //Node('i')
    return root //Node('h')
root = root //Node('h')
...