CC++ & Algorithm

Trie的插入、查找与遍历

极难2
语言版本：通用
概述：深入学习字典树的核心操作：插入、精确查找、前缀查找以及树的深度优先遍历，并用代码实现一个完整的自动补全功能。

下面是你需要的扩展内容。我保留了原有内容的全部正确表述和示例，同时补充了更多生活化的例子、细节解释、常见错误和带中文注释的完整代码。

Trie的插入、查找与遍历——从联想输入到自动补全

字典树（Trie）是一种专门用来高效存储和查找字符串的数据结构。它的核心思想是把每个字符串拆成一个个字符，沿着一条树形路径存放，这样具有相同前缀的单词会共享前面的节点。今天我们要深入学习字典树的三个核心操作：精确查找、前缀查找和深度优先遍历，并用这些知识实现一个像手机输入法一样的自动补全功能。

生活中的联想场景

你是不是经常在手机上打字时，刚输入几个字母，输入法就弹出一串候选词？比如输入“scho”，立刻出现“school”、“scholar”、“schedule”等。这就是字典树的前缀查找加遍历在背后工作。再比如搜索引擎的搜索框，输入“今”就会弹出“今天天气”、“今天吃什么”等，也是同样的原理。

1. 精确查找 vs 前缀查找：一字之差，用途不同

精确查找（search）

精确查找要判断一个完整的单词是否存在于字典里。比如我们存了“apple”，查“app”应该返回false，因为“app”虽然是一个前缀，但不是一个完整的单词（除非你也存了“app”）。实现时要从根沿着字符走，走到单词最后一个字符后，还必须检查该节点的isEnd标记是否为true。

bool search(string word) {
    TrieNode* cur = root;
    for (char ch : word) {
        int idx = ch - 'a';
        if (cur->next[idx] == nullptr) return false; // 中途断了，单词不存在
        cur = cur->next[idx];
    }
    return cur->isEnd; // 必须检查结尾标记
}

生活类比：你在一本单词书里找“cat”这个单词。如果书里只有“catalog”，你翻到“cat”这一页，但页码显示是“catalog”的一部分，并没有独立成词，所以算没找到。

前缀查找（startsWith）

前缀查找只关心有没有以某个字符串开头的单词，不要求这个字符串本身是一个词。比如我们存了“application”，查“app”得到true（因为“application”以“app”开头）；查“appl”也是true。实现时走到前缀最后一个字符节点即可返回true，无需检查isEnd。

bool startsWith(string prefix) {
    TrieNode* cur = root;
    for (char ch : prefix) {
        int idx = ch - 'a';
        if (cur->next[idx] == nullptr) return false;
        cur = cur->next[idx];
    }
    return true; // 只要能走完，前缀就存在
}

生活类比：你在搜索栏输入“pro”，系统立刻列出所有以“pro”开头的词，比如“program”、“project”，但“pro”本身可能不是完整单词（除非你存了“pro”这个词）。

2. 深度优先遍历（DFS）：把所有单词“捞”出来

前缀查找只能告诉你“有没有”，但自动补全需要列出所有以该前缀开头的单词。怎么做？找到前缀最后一个节点后，以它为起点进行深度优先搜索（DFS），每遇到一个isEnd为true的节点，就把从根走到这里的字符串拼接起来，加入结果列表。

遍历时要按照字母顺序（a到z）访问子节点，这样输出的单词就是字典序排列的。

void collectAll(TrieNode* node, string prefix, vector<string>& result) {
    if (node == nullptr) return;
    if (node->isEnd) {
        result.push_back(prefix);   // 收集一个完整单词
    }
    for (int i = 0; i < 26; i++) {
        if (node->next[i] != nullptr) {
            char ch = 'a' + i;               // 把索引转回字母
            collectAll(node->next[i], prefix + ch, result);
        }
    }
}

生活类比：你在一棵大树（前缀树）上挂了很多写着单词的彩灯。你想找出所有以“ap”开头的彩灯，就先走到“ap”这个分叉点，然后举起手电筒沿着每条枝丫（字母）照下去，每发现一个写着完整单词的灯泡就记下它的位置（路径）。

3. 实现自动补全功能

把前缀查找和遍历组合起来，就是完整的自动补全：

vector<string> getWordsWithPrefix(string prefix) {
    TrieNode* cur = root;
    for (char ch : prefix) {
        int idx = ch - 'a';
        if (cur->next[idx] == nullptr) {
            return vector<string>();   // 前缀不存在，返回空列表
        }
        cur = cur->next[idx];
    }
    vector<string> result;
    collectAll(cur, prefix, result);
    return result;
}

运行示例：
插入单词“apple”、“app”、“application”、“apt”、“bat”、“ball”后，调用getWordsWithPrefix("ap")会返回：
app → apple → application → apt
（注意“apt”也以“ap”开头，按字母顺序排在“app”之后。）

4. 常见错误与避坑指南

  • 忘记标记结尾：插入单词后忘了把最后一个节点的isEnd设为true，结果精确查找永远返回false。
    ✅ 在insert最后写上cur->isEnd = true;
  • 精确查找忘检查isEnd：直接返回true，把前缀当成了单词。
    ✅ 记住：只有走完路径且节点标记为结尾才算找到。
  • 遍历时没有考虑字符顺序：如果子节点存储无序（比如Python字典不排序），输出单词可能乱序。
    ✅ 对子节点按字母排序后再递归。
  • 递归时传字符串造成大量拷贝：在collectAll中每层都拼接一个新字符串，当单词很长时效率低。
    ✅ 可以用一个char数组或列表暂存，到达叶子时一次性拼接（但教学代码为了清晰可暂时忽略）。
  • 内存泄漏：C++中new了节点却没有删除。虽然本文不深究，但实际项目中要用析构函数或智能指针释放内存。

5. 完整可运行代码（带中文注释）

下面给出C++和Python的完整代码，每一行变量定义都加了中文注释，方便理解。

C++版

#include <iostream>
#include <vector>
#include <string>
using namespace std;

struct TrieNode {
    TrieNode* next[26];    // 子节点指针数组，对应26个小写字母
    bool isEnd;            // 标记是否为一个单词的结尾
    TrieNode() {
        for (int i = 0; i < 26; i++) next[i] = nullptr;
        isEnd = false;
    }
};

class Trie {
private:
    TrieNode* root;  // 根节点，不存储字符

    // 辅助函数：深度优先遍历，收集所有单词
    void collectAll(TrieNode* node, string prefix, vector<string>& result) {
        if (node == nullptr) return;
        if (node->isEnd) {
            result.push_back(prefix);   // 遇到结尾标记，把当前路径加入结果
        }
        for (int i = 0; i < 26; i++) {
            if (node->next[i] != nullptr) {
                char ch = 'a' + i;               // 根据索引还原字符
                collectAll(node->next[i], prefix + ch, result);
            }
        }
    }

public:
    Trie() {
        root = new TrieNode();
    }

    // 插入一个单词
    void insert(string word) {
        TrieNode* cur = root;  // 从根开始
        for (char ch : word) {
            int idx = ch - 'a';               // 字符转索引（0-25）
            if (cur->next[idx] == nullptr) {
                cur->next[idx] = new TrieNode();  // 空则新建节点
            }
            cur = cur->next[idx];  // 移动到子节点
        }
        cur->isEnd = true;  // 标记单词结尾
    }

    // 精确查找：判断单词是否完整存在
    bool search(string word) {
        TrieNode* cur = root;
        for (char ch : word) {
            int idx = ch - 'a';
            if (cur->next[idx] == nullptr) return false;  // 路径中断，单词不存在
            cur = cur->next[idx];
        }
        return cur->isEnd;  // 必须走到结尾标记
    }

    // 前缀查找：判断是否存在以prefix开头的单词
    bool startsWith(string prefix) {
        TrieNode* cur = root;
        for (char ch : prefix) {
            int idx = ch - 'a';
            if (cur->next[idx] == nullptr) return false;  // 前缀不存在
            cur = cur->next[idx];
        }
        return true;  // 只要能走完，前缀就存在（不检查结尾标记）
    }

    // 自动补全：获取所有以prefix开头的单词
    vector<string> getWordsWithPrefix(string prefix) {
        TrieNode* cur = root;
        for (char ch : prefix) {
            int idx = ch - 'a';
            if (cur->next[idx] == nullptr) {
                return vector<string>();  // 前缀不存在，返回空列表
            }
            cur = cur->next[idx];
        }
        vector<string> result;  // 存储结果
        collectAll(cur, prefix, result);  // 从prefix结尾节点开始DFS
        return result;
    }
};

int main() {
    Trie trie;
    trie.insert("apple");
    trie.insert("app");
    trie.insert("application");
    trie.insert("apt");
    trie.insert("bat");
    trie.insert("ball");

    cout << "查找前缀 'app': " << trie.startsWith("app") << endl;  // 输出1
    cout << "查找前缀 'apx': " << trie.startsWith("apx") << endl;  // 输出0

    vector<string> words = trie.getWordsWithPrefix("ap");
    cout << "所有以'ap'开头的单词:" << endl;
    for (string w : words) {
        cout << w << endl;  // 输出：app, apple, application, apt
    }

    return 0;
}

Python版

class TrieNode:
    def __init__(self):
        self.children = {}      # 子节点字典，键为字符，值为节点
        self.is_end = False     # 是否为单词结尾

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word: str) -> None:
        cur = self.root  # 从根节点开始
        for ch in word:
            if ch not in cur.children:
                cur.children[ch] = TrieNode()  # 新建节点
            cur = cur.children[ch]  # 移动到子节点
        cur.is_end = True  # 标记结尾

    def search(self, word: str) -> bool:
        cur = self.root
        for ch in word:
            if ch not in cur.children:
                return False  # 路径断了
            cur = cur.children[ch]
        return cur.is_end  # 检查结尾标记

    def startsWith(self, prefix: str) -> bool:
        cur = self.root
        for ch in prefix:
            if ch not in cur.children:
                return False
            cur = cur.children[ch]
        return True  # 不检查结尾

    # 辅助递归函数
    def _collect(self, node: TrieNode, prefix: str, result: list):
        # node: 当前节点, prefix: 已构建的前缀字符串, result: 收集结果列表
        if node is None:
            return
        if node.is_end:
            result.append(prefix)  # 找到一个单词
        # 按字母顺序遍历子节点（字典的键自动保持插入顺序，但为了字典序需要排序）
        for ch in sorted(node.children.keys()):  # 排序保证输出有序
            self._collect(node.children[ch], prefix + ch, result)

    def getWordsWithPrefix(self, prefix: str) -> list:
        cur = self.root
        for ch in prefix:
            if ch not in cur.children:
                return []  # 前缀不存在
            cur = cur.children[ch]
        result = []
        self._collect(cur, prefix, result)
        return result

if __name__ == "__main__":
    trie = Trie()
    trie.insert("apple")
    trie.insert("app")
    trie.insert("application")
    trie.insert("apt")
    trie.insert("bat")
    trie.insert("ball")

    print("前缀 'app' 存在:", trie.startsWith("app"))  # True
    print("前缀 'apx' 存在:", trie.startsWith("apx"))  # False

    words = trie.getWordsWithPrefix("ap")
    print("所有以'ap'开头的单词:")
    for w in words:
        print(w)  # app, apple, application, apt

6. 相关知识点指引

掌握了字典树的插入、查找与遍历之后，你可以继续学习：

  • 词频统计：在节点中增加一个计数器，统计单词经过该节点的次数，可用于自动补全时按热度排序。
  • 删除操作：递归删除单词，注意如果节点是其他单词的前缀，只能清除标记不能删除节点。
  • 压缩字典树（Patricia Trie / Radix Tree）：合并只有一个子节点的路径，减少内存占用。
  • 01-Trie：用二进制位构建字典树，专门用于解决异或最大值问题（比如“最大异或对”）。
  • AC自动机：在Trie上加入失败指针，实现多模式串匹配（同时查找多个单词）。

这些技术广泛应用于搜索引擎、拼写检查、路由表查找、基因序列分析等领域。字典树虽然简单，但它是很多高级字符串算法的基石。现在你已经能独立实现一个自动补全功能了，不妨试试用它来做一个自己的“智能输入法”小项目吧！

例题精讲

1单选题

关于Trie（字典树）的插入操作，以下说法正确的是？

A插入一个长度为n的字符串，时间复杂度为O(n * log|Σ|)，其中|Σ|是字符集大小
B插入操作需要将字符串的每个字符依次插入，如果路径不存在则创建新节点，时间复杂度为O(n)
C插入操作需要递归遍历整个树，时间复杂度为O(n^2)
D插入操作最好情况时间复杂度为O(1)，最坏为O(n)
2单选题

在Trie中，精确查找字符串"abc"与查找前缀"ab"的区别是？

A精确查找需要判断路径完全匹配且最后一个节点的isEnd为true；前缀查找只需判断路径是否存在
B两者都需要判断isEnd，没有区别
C前缀查找需要比精确查找多遍历一层
D精确查找只需判断路径是否存在，前缀查找需要判断isEnd
3判断题

在Trie中，每个节点通常存储一个字符，根节点不存储字符。

4填空题
实现Trie插入函数。假设节点结构如下：
struct TrieNode {
    TrieNode* children[26];
    bool isEnd;
    TrieNode() {
        isEnd = false;
        for (int i = 0; i < 26; i++) children[i] = nullptr;
    }
};
void insert(TrieNode* root, string word) {
    TrieNode* node = root;
    for (char ch : word) {
        int idx = ch - 'a';
        if (node->children[idx] == nullptr) {
            node->children[idx] = ___ // 填空1
        }
        node = node->children[idx];
    }
    ___ // 填空2
}
5填空题
实现Trie的深度优先遍历，收集所有以给定前缀开头的单词（自动补全）。
void dfs(TrieNode* node, string current, vector<string>& result) {
    if (node == nullptr) return;
    if (node->isEnd) {
        result.push_back(current);
    }
    for (int i = 0; i < 26; i++) {
        if (node->children[i] != nullptr) {
            char nextChar = 'a' + i;
            dfs(node->children[i], ___ , result); // 填空
        }
    }
}
vector<string> autoComplete(TrieNode* root, string prefix) {
    TrieNode* node = root;
    vector<string> result;
    for (char ch : prefix) {
        int idx = ch - 'a';
        if (node->children[idx] == nullptr) return result;
        node = node->children[idx];
    }
    dfs(node, prefix, result);
    return result;
}