前缀树（Trie）详解：C#实现高效字符串检索（小白也能看懂的Trie入门教程）

如上图所示，单词 "how"、"hi"、"him" 在 Trie 中共享了部分节点（比如 'h'），这样不仅结构清晰，还能快速判断某个前缀是否存在。

为什么使用 Trie？

• ✅ 高效前缀匹配：判断一个字符串是否以某前缀开头，时间复杂度为 O(m)，m 是前缀长度。
• ✅ 自动补全：输入 “app”，可以快速列出所有以 “app” 开头的单词（如 apple, app）。
• ✅ 词频统计：记录每个单词出现的次数。
• ✅ 节省内存（相比哈希表）：当大量字符串有共同前缀时，Trie 更省空间。

这些特性使 Trie 成为搜索引擎、输入法、路由系统等场景的理想选择。接下来，我们就用 C# 来实现一个基础版的 Trie。

C# 实现 Trie 节点类

首先，我们需要定义 Trie 的节点。每个节点包含：

• 一个字典（Dictionary），用于存储子节点（键为字符，值为子节点）
• 一个布尔值，标记当前节点是否为某个单词的结尾

public class TrieNode{    // 子节点：字符 -> TrieNode    public Dictionary<char, TrieNode> Children { get; set; }        // 是否为单词结尾    public bool IsEndOfWord { get; set; }    public TrieNode()    {        Children = new Dictionary<char, TrieNode>();        IsEndOfWord = false;    }}

构建 Trie 类：插入与搜索

有了节点，我们就可以构建完整的 Trie 类，支持插入（Insert）和搜索（Search）操作。

public class Trie{    private TrieNode root;    public Trie()    {        root = new TrieNode();    }    // 插入一个单词    public void Insert(string word)    {        TrieNode current = root;        foreach (char c in word)        {            if (!current.Children.ContainsKey(c))            {                current.Children[c] = new TrieNode();            }            current = current.Children[c];        }        current.IsEndOfWord = true; // 标记单词结束    }    // 搜索完整单词是否存在    public bool Search(string word)    {        TrieNode node = FindNode(word);        return node != null && node.IsEndOfWord;    }    // 判断是否存在以 prefix 开头的单词    public bool StartsWith(string prefix)    {        return FindNode(prefix) != null;    }    // 辅助方法：查找前缀对应的节点    private TrieNode FindNode(string prefix)    {        TrieNode current = root;        foreach (char c in prefix)        {            if (!current.Children.ContainsKey(c))                return null;            current = current.Children[c];        }        return current;    }}

使用示例

现在我们来测试一下这个 Trie：

class Program{    static void Main()    {        Trie trie = new Trie();        trie.Insert("apple");        trie.Insert("app");        trie.Insert("apply");        Console.WriteLine(trie.Search("app"));      // 输出: True        Console.WriteLine(trie.Search("appl"));     // 输出: False（不是完整单词）        Console.WriteLine(trie.StartsWith("app"));  // 输出: True        Console.WriteLine(trie.StartsWith("xyz"));  // 输出: False    }}

总结

通过本教程，你已经掌握了 前缀树（Trie）的基本原理和 C# 实现方法。Trie 是处理字符串检索问题的强大工具，特别适合需要频繁前缀匹配的场景。虽然本例只实现了基础功能，但你可以在此基础上扩展，比如添加删除操作、统计词频、实现自动补全等。

记住，理解数据结构的核心在于动手实践。不妨自己写一遍代码，再尝试加入新功能，加深对 C#数据结构 的理解！

掌握 Trie，让你的字符串处理更高效！