如何 return 递归添加的 trie 的根？

Question

我正在尝试使用链表将字符串添加到以“$”作为终止符的 trie。但是，它只是 returns Trie 的最后一个节点，而不是 Trie 的根节点。这是我的代码：

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

完成后 returns 节点值为 $ 并且没有子节点或下一个节点。

Answer 1

原因是因为您在 return root 之前将 root 设置为 add 的 return 值。结果是您将从调用堆栈中获取 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 的 return 值。没有必要这样做。只需像您目前所做的那样调用 add，然后像这样分别调用 return 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')

如何 return 递归添加的 trie 的根？

How to return the root of a trie that is added to recursively?

java

recursion

trie