Trie（字典树）是一种专门用来处理字符串集合的树形结构，它和普通二叉树最大的区别在于节点不保存完整键值，而是把键拆成字符分散到路径上。比如存储 cat、car、dog 三个单词，根节点下会有 c 和 d 两个子节点，c 下面又分出 a，a 下面再分出 t 和 r。这种设计让拥有相同前缀的单词共享同一段路径，因此在做前缀匹配、自动补全、词频统计等任务时非常高效。C# 的标准库并没有提供 Trie，但这并不影响我们在项目中自己实现一个轻量版本。
实现 Trie 的首要任务是确定节点结构。一个节点至少需要两个信息：指向子节点的引用集合，以及当前节点是否代表某个完整单词的结束。子节点集合可以用不同的容器来存，这也是影响性能的关键点。
一、设计TrieNode与字段选择
先给出一个最通用的节点定义。假设我们需要支持任意字符，那么子节点用一个字典来保存是比较省心的方案。字典的键是字符，值是下一个节点引用。
public class TrieNode
{
public Dictionary<char, TrieNode> Children { get; } = new Dictionary<char, TrieNode>();
public bool IsEndOfWord { get; set; }
}
这里把 Children 暴露为只读属性，避免外部误替换整个字典。IsEndOfWord 标记一个节点是否为某个单词的结尾，例如插入 cat 后，从根到 t 的路径上，t 节点的 IsEndOfWord 为 true，而 c 和 a 节点为 false。这样即使在同一个路径上存在多个单词，比如 cat 和 cats，也能通过结束标记区分。
如果使用场景明确为小写英文字母，比如英文单词前缀搜索，可以用长度为 26 的数组代替字典。数组下标由字符减去 a 得到，访问速度比字典快，且没有额外哈希开销。但数组会固定分配 26 个槽位，即使很多位置为空，也会造成一定内存浪费。对于中文、数字、符号混合的场景，字典更灵活。还有一种折中方案是用排序列表存储子节点，插入和查找做二分，但代码复杂度会上升。本文后续实现采用字典，保证通用性。
二、插入、查找与删除核心操作
插入操作从根节点开始，遍历待插入字符串的每个字符。如果当前字符不在子节点字典中，就创建新节点并加入；然后移动到该子节点继续处理下一个字符。整个字符串处理完后，将最后一个节点的 IsEndOfWord 置为 true。
public class Trie
{
private readonly TrieNode _root = new TrieNode();
public void Insert(string word)
{
if (string.IsNullOrEmpty(word)) return;
TrieNode node = _root;
foreach (char ch in word)
{
if (!node.Children.TryGetValue(ch, out TrieNode next))
{
next = new TrieNode();
node.Children[ch] = next;
}
node = next;
}
node.IsEndOfWord = true;
}
public bool Search(string word)
{
TrieNode node = FindNode(word);
return node != null && node.IsEndOfWord;
}
public bool StartsWith(string prefix)
{
return FindNode(prefix) != null;
}
private TrieNode FindNode(string s)
{
TrieNode node = _root;
foreach (char ch in s)
{
if (!node.Children.TryGetValue(ch, out node))
return null;
}
return node;
}
}
上面的 FindNode 方法被 Search 和 StartsWith 共用。Search 要求路径存在且末端节点标记为结束，而 StartsWith 只要求路径存在即可。二者时间复杂度都是 O(m)，m 是字符串长度。如果单词不存在，FindNode 会在中间提前返回 null。注意空字符串的处理：如果把空串作为有效单词插入，root 的 IsEndOfWord 会被置为 true，但这里我们在 Insert 中直接返回，避免歧义。实际项目是否允许空串需要根据业务决定。
删除操作比插入和查找复杂，因为需要避免删除一个仍是其他单词前缀的节点。例如删除 cat 时不能把 c、a、t 全部删除，因为 car 可能还在。删除时用递归，从最后一个字符开始回溯，如果某个节点没有子节点且不是单词结尾，就可以把它从父节点的字典中移除。
public bool Remove(string word)
{
return Remove(_root, word, 0);
}
private bool Remove(TrieNode node, string word, int index)
{
if (index == word.Length)
{
if (!node.IsEndOfWord) return false;
node.IsEndOfWord = false;
return node.Children.Count == 0;
}
char ch = word[index];
if (!node.Children.TryGetValue(ch, out TrieNode child))
return false;
bool shouldDeleteChild = Remove(child, word, index + 1);
if (shouldDeleteChild)
{
node.Children.Remove(ch);
return node.Children.Count == 0 && !node.IsEndOfWord;
}
return false;
}
这段代码从根节点开始递归下探，先找到单词末尾并把结束标记置为 false。如果末端节点没有子节点，就返回 true 通知上层删除自己；上层删除后，如果自己也没有子节点且不是另一个单词的结尾，继续返回 true，否则停止删除。这种回溯判断保证了不会误删共享前缀。需要注意的是，删除前最好先用 Search 判断单词是否存在，不过这里 Remove 内部已经做了检查。
这些基础操作构成 Trie 的核心能力。接下来我们看如何利用 Trie 做前缀搜索和自动补全，也就是输入一个前缀后找出所有以该前缀开头的单词。
三、前缀搜索与自动补全实现
前缀搜索要求返回集合中所有以指定前缀开头的单词。实现思路分两步：先调用 FindNode 定位到前缀的最后一个字符对应节点；如果该节点为 null，说明没有任何单词拥有这个前缀，直接返回空列表。否则从该节点开始进行深度优先遍历，收集所有 IsEndOfWord 为 true 的路径。
public List<string> GetWordsWithPrefix(string prefix)
{
var result = new List<string>();
TrieNode prefixNode = FindNode(prefix);
if (prefixNode == null) return result;
CollectWords(prefixNode, prefix, result);
return result;
}
private void CollectWords(TrieNode node, string currentPrefix, List<string> result)
{
if (node.IsEndOfWord)
result.Add(currentPrefix);
foreach (var pair in node.Children)
{
CollectWords(pair.Value, currentPrefix + pair.Key, result);
}
}
上面的 CollectWords 递归遍历子树，每次把子节点的字符追加到当前前缀后面。当遇到 IsEndOfWord 为 true 的节点，就把 currentPrefix 加入结果。注意遍历顺序取决于 Dictionary 的枚举顺序，在 .NET 中不是严格按字符排序的。如果需要排序输出，可以在返回前调用 result.Sort()，或者改用有序字典。对于大多数自动补全场景，一般还会结合词频进行排序，这里先返回全部匹配项。
如果要限制返回数量，避免前缀匹配过多导致性能问题，可以在 CollectWords 中增加一个计数参数，达到上限就停止递归。例如从海量词库中搜索前缀 a，可能返回成千上万个单词，全量收集会浪费内存。更好的做法是用一个优先级队列，按照词频或最近使用时间挑选前 N 个候选项。这个扩展留给读者根据业务实现。
自动补全还有一个常见需求是大小写不敏感。可以在 Insert 时统一转小写存储，并在 GetWordsWithPrefix 调用前也把前缀转小写。但这样会丢失原始大小写，如果展示需要保留原词，可以额外保存一份原始单词列表或映射。中文场景不存在大小写问题，但要注意中文按字符处理时，每个汉字是一个 char，字典也能正常工作。
四、内存与性能优化
Trie 虽然查询快，但内存占用往往比哈希集合要高，尤其是节点数量很大时。每个 TrieNode 对象本身有对象头开销，再加一个字典实例，空节点也会占不少内存。如果词库只有几十万条，普通实现可以接受；如果达到千万级别，就需要考虑优化。
一个典型的优化是使用数组替代字典，只支持固定字符集。例如纯英文小写字母，每个节点分配 26 个 TrieNode 引用，用 char - 'a' 定位。这样避免了字典的哈希桶和链表开销，访问速度也更快。缺点是空槽位浪费空间，对于稀疏的前缀树，大量槽位为 null。另一种折中是使用 List<TrieNode> 配合一个字符列表，按字符排序，插入时二分查找，内存比字典小，速度比数组略慢。
还有一类压缩结构叫基数树或 Patricia Trie，它将只有一个子节点的链压缩成一个边标签，能大幅减少节点数量。例如只有一个单词 hello 的情况下，普通 Trie 需要 5 个节点，压缩后只需要根节点和一条标记为 hello 的边。这种实现复杂度明显增加，但在键很长且共享前缀少时收益明显。C# 社区中也有一些开源实现，如果项目对内存敏感，可以评估后引入。
性能方面，插入和查找的每次字符操作会调用字典的 TryGetValue，这是 O(1) 均摊。但如果把 Trie 用于大规模文本索引，建议在构造前对词库做预处理，比如去除重复、按长度分层。也可以用内存池或结构体数组来减少托管堆分配，但会牺牲代码可读性。实际项目中，先保证功能正确，再通过基准测试定位瓶颈，比一开始就做高度优化更划算。
五、与哈希表的对比及适用边界
很多人会问：前缀搜索用哈希表遍历所有 key 不行吗？对于数据量小、前缀查询频率低的场景，完全可以。但哈希表无法利用前缀结构，每次匹配都要遍历全部键，时间复杂度 O(n * m)，n 是键数量。Trie 把复杂度降到 O(m + k)，k 是返回结果数量，这在 n 很大时优势明显。代价是内存占用更高，插入速度也比哈希表慢一点，因为要逐个字符分配节点。
如果你的需求只是判断某个单词是否存在于固定集合中，用 HashSet<string> 更简单更快；如果还需要支持根据前缀列出候选词，或者需要快速判断某个前缀是否存在，Trie 才更合适。像搜索引擎的搜索建议、IDE 的代码补全、输入法词库等，都是 Trie 的典型应用。
下面给一个简单的使用示例，把前面实现的 Trie 用于命令行提示：
var trie = new Trie();
trie.Insert("hello");
trie.Insert("help");
trie.Insert("world");
Console.WriteLine(trie.Search("hello")); // True
Console.WriteLine(trie.StartsWith("he")); // True
foreach (var word in trie.GetWordsWithPrefix("he"))
{
Console.WriteLine(word); // hello, help（顺序可能不同）
}
这段代码演示了最常用的三个操作。运行输出中 hello 和 help 的顺序取决于 Dictionary 的枚举顺序，如果需要稳定输出，记得排序。实际开发中建议把 Trie 封装成一个独立的服务类，配合缓存或词频统计，给上层提供更友好的 API。