Trie数据结构中next()函数工作原理及节点关联疑问

你的理解方向是对的，核心要明确Trie节点的层级关系：

• 每个Node的links数组存储的是当前节点的子节点，对应26个小写字母的位置。
• 调用put(c, new Node())时，是把新创建的Node作为当前节点对应字符c的子节点，存入links数组的对应位置。
• 调用next(c)时，返回的就是这个预先存入的子节点，随后把遍历用的node变量指向这个子节点——这一步就完成了从“当前节点”到“下一层子节点”的移动，也就是你说的“成为下一个节点”。

结合insert函数的执行流程来看会更清晰，比如插入单词"abc"：

1. 初始node = root（根节点，是空的父节点）。
2. 处理字符'a'：
   • 根节点的links['a'-'a']为空，所以调用put('a', new Node())，给根节点添加一个对应'a'的子节点。
   • 执行node = node.next('a')，此时node变成了刚才创建的那个子节点，也就是根节点的下一层节点。
3. 处理字符'b'：
   • 当前node是根节点的'a'子节点，它的links['b'-'a']为空，所以put('b', new Node())，给它添加对应'b'的子节点。
   • 执行node = node.next('b')，node移动到这个新的子节点，进入下一层。
4. 处理字符'c'同理，最终形成一条root → a节点 → b节点 → c节点的路径，完美对应单词"abc"的字符顺序。

本质上，put负责构建节点间的父子关系，next负责沿着这个关系向下遍历，两者配合完成Trie的构建和前缀查询。

完整Java实现代码 #

class Node {

    private Node[] links = new Node[26];

    // 检查当前节点是否包含指定字符对应的子节点
    public boolean contains(char c) {
        return links[c - 'a'] != null;
    }

    // 为指定字符插入新的子节点
    public void put(char c, Node node) {
        links[c - 'a'] = node;
    }

    // 获取指定字符对应的子节点
    public Node next(char c) {
        return links[c - 'a'];
    }
}

class Trie {

    private Node root;

    public Trie() {
        root = new Node();
    }

    // 插入单词到Trie中
    public void insert(String word) {
        Node node = root;
        for (char c : word.toCharArray()) {
            if (!node.contains(c)) {
                node.put(c, new Node());
            }
            node = node.next(c);
        }
    }

    // 检查Trie中是否包含指定前缀
    public boolean startsWith(String prefix) {
        Node node = root;
        for (char c : prefix.toCharArray()) {
            if (!node.contains(c)) {
                return false;
            }
            node = node.next(c);
        }
        return true;
    }
}

内容的提问来源于stack exchange，提问作者SoManyAngels