字典树的基本知识及使用C语言的相关实现

2020-01-26 14:59:42

字体：大中小

来源：转载

供稿：网友

概念

如果我们有and,as,at,cn,com这些关键词，那么trie树（字典树）是这样的：

201587113000993.png (702×500)

从上面的图中，我们或多或少的可以发现一些好玩的特性。

第一：根节点不包含字符，除根节点外的每一个子节点都包含一个字符。

第二：从根节点到某一节点，路径上经过的字符连接起来，就是该节点对应的字符串。

第三：每个单词的公共前缀作为一个字符节点保存。

使用范围

既然学Trie树，我们肯定要知道这玩意是用来干嘛的。

第一：词频统计。

可能有人要说了，词频统计简单啊，一个hash或者一个堆就可以打完收工，但问题来了，如果内存有限呢？还能这么

玩吗？所以这里我们就可以用trie树来压缩下空间，因为公共前缀都是用一个节点保存的。

第二: 前缀匹配

就拿上面的图来说吧，如果我想获取所有以"a"开头的字符串，从图中可以很明显的看到是：and,as,at，如果不用trie树，

你该怎么做呢？很显然朴素的做法时间复杂度为O(N2) ，那么用Trie树就不一样了，它可以做到h，h为你检索单词的长度，

可以说这是秒杀的效果。

数据结构定义

  #define MAX 26 // 字符集大小      typedef struct trieNode {     struct trieNode *next[MAX];     int count; // 记录该字符出现次数   } trieNode;

next数组表示每层有多少类的数，如果只是小写字母，26即可

实现方法
搜索字典项目的方法：

从根节点开始一次搜索
获取要查找关键词的第一个字母，并根据该字母选择对应的子树并转到该子树继续进行检索
在相应的子树上，获取要查找关键词的第二个字母，并进一步选择对应的子树进行检索
迭代过程
在某个节点处，关键词的所有字母已被取出，则读取附在该结点上的信息，即完成查找

其他操作类似

实现模板

初始化根结点

  /**    * 初始化Trie树根结点    */   void initTrie(trieNode **root)   {     int i;        *root = (trieNode *)malloc(sizeof(trieNode));     (*root)->count = 0;        for (i = 0; i < MAX; i ++) {       (*root)->next[i] = NULL;     }   }

插入单词到trie树

  /**    * Trie树插入操作    */   void insert(char *str, trieNode *root)   {     int i;        trieNode *p = root;        while (*str != '/0') {       if (p->next[*str - 'a'] == NULL) {         trieNode *tmp = (trieNode *)malloc(sizeof(trieNode));         for (i = 0; i < MAX; i ++) {           tmp->next[i] = NULL;         }         tmp->count = 1;         p->next[*str - 'a'] = tmp;         p = p->next[*str - 'a'];       } else {         p = p->next[*str - 'a'];         p->count ++;       }          str ++;     }   }

统计查找单词数量

  /**    * 统计前缀出现次数    */   int count(char *search, trieNode *root)   {     trieNode *p = root;        while (*search != '/0') {       if (p->next[*search - 'a'] == NULL) {         return 0;       } else {         p = p->next[*search - 'a'];         search ++;       }     }        return p->count;   }

清理trie树

  /**    * 清理trie树    */   void delTrie(trieNode *root)   {     int i;        for (i = 0; i < MAX; i ++) {       if (root->next[i] != NULL) {         delTrie(root->next[i]);       }     }        free(root);   }

时间复杂度
插入、查找的时间复杂度均为O(n),n为字符串的长度

空间复杂度较高，O(26^n),典型空间换时间

参考题目

ac代码：

  #include <stdio.h>   #include <stdlib.h>   #include <string.h>      #define MAX 26 // 字符集大小      typedef struct trieNode {     struct trieNode *next[MAX];     int count; // 记录该字符出现次数   } trieNode;         /**    * 初始化Trie树根结点    */   void initTrie(trieNode **root)   {     int i;        *root = (trieNode *)malloc(sizeof(trieNode));     (*root)->count = 0;        for (i = 0; i < MAX; i ++) {       (*root)->next[i] = NULL;     }   }      /**    * Trie树插入操作    */   void insert(char *str, trieNode *root)   {     int i;        trieNode *p = root;        while (*str != '/0') {       if (p->next[*str - 'a'] == NULL) {         trieNode *tmp = (trieNode *)malloc(sizeof(trieNode));         for (i = 0; i < MAX; i ++) {           tmp->next[i] = NULL;         }         tmp->count = 1;         p->next[*str - 'a'] = tmp;         p = p->next[*str - 'a'];       } else {         p = p->next[*str - 'a'];         p->count ++;       }          str ++;     }   }      /**    * 统计前缀出现次数    */   int count(char *search, trieNode *root)   {     trieNode *p = root;        while (*search != '/0') {       if (p->next[*search - 'a'] == NULL) {         return 0;       } else {         p = p->next[*search - 'a'];         search ++;       }     }        return p->count;   }      /**    * 清理trie树    */   void delTrie(trieNode *root)   {     int i;        for (i = 0; i < MAX; i ++) {       if (root->next[i] != NULL) {         delTrie(root->next[i]);       }     }        free(root);   }         int main(void)   {     char str[15];     trieNode *root;        // 初始化根结点     initTrie(&root);        while (gets(str) && str[0] != '/0') {       // 插入Trie树       insert(str, root);     }        // 查找前缀出现次数     while (gets(str) && str[0] != '/0') {       printf("%d/n", count(str, root));     }        delTrie(root);        return 0;   }

上一篇：字符串的组合算法问题的C语言实现攻略

下一篇：一些语言的按行读取文件的代码实现小结