21xrx.com
2025-07-05 16:16:16 Saturday
文章检索 我的文章 写文章
C++实现字典树:原理和应用
2023-06-28 10:23:00 深夜i     22     0
C++ 字典树 原理 应用

字典树(Trie Tree),也成为单词查找树或键树,是一类特殊的多叉树数据结构,用于实现快速中定查找与统计大量字符串的数据结构。字典树是一种树型数据结构,通常在统计和排序大量字符串(但不仅限于字符串)时,效率优于其他数据结构。

字典树主要应用于字符串匹配、统计前缀词频以及字符串排序。它的核心是将字符串中的每个字符作为树节点,每个单词构成的路径上标记相应的节点,并以特殊的叶子节点表示单词结束。这样通过遍历树的路径,可以输出所有匹配查询条件的单词,同时统计每个单词出现的次数。

使用C++实现字典树非常简单。先定义字典树节点的数据结构,包含一个字符类型和指向其他子节点的指针数组。然后定义字典树类,包含建立字典树的函数(Insert),匹配单词的查找函数(Search)、统计单词前缀词频的函数(PrefixCount)、输出所有单词的函数(Print)等。

下面给出一个简单的C++实现代码:

const int MAX_N = 26;
struct TrieNode {
  char val;
  int count;
  TrieNode* child[MAX_N];
  TrieNode(char v) : val(v), count(0) {memset(child, NULL, sizeof(child));}
};
class TrieTree {
private:
  TrieNode* root;
public:
  TrieTree() {root = new TrieNode('*');}
  void Insert(const char* word) {
    TrieNode* cur = root;
    while (*word) {
      int idx = *word - 'a';
      if (cur->child[idx] == NULL)
        cur->child[idx] = new TrieNode(*word);
      cur = cur->child[idx];
      word++;
    }
    cur->count++;
  }
  bool Search(const char* word) {
    TrieNode* cur = root;
    while (*word) {
      int idx = *word - 'a';
      if (cur->child[idx] == NULL)
        return false;
      cur = cur->child[idx];
      word++;
    }
    return (cur != NULL && cur->count > 0);
  }
  int PrefixCount(const char* prefix) {
    TrieNode* cur = root;
    while (*prefix) {
      int idx = *prefix - 'a';
      if (cur->child[idx] == NULL)
        return 0;
      cur = cur->child[idx];
      prefix++;
    }
    return (cur != NULL ? cur->count : 0);
  }
  void PrintWords(TrieNode* node, string prefix) {
    if (node == NULL)
      return;
    if (node->count > 0)
      cout << prefix << " : " << node->count << endl;
    for (int i = 0; i < MAX_N; i++) {
      if (node->child[i] != NULL)
        PrintWords(node->child[i], prefix + node->child[i]->val);
    }
  }
  void Print() {
    PrintWords(root, "");
  }
};

字典树因其高效的查询与统计能力在许多场景中得到了广泛的应用。比如,搜索引擎中的关键词匹配,输入法中的词库,DNA序列在生物信息学中的序列比对,以及字符串排序等场景中都使用到了字典树。通过理解字典树的基本原理并掌握C++的实现,我们可以更加灵活地应用该数据结构来解决实际的问题。

  
  

评论区