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

概念

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

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

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

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

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

使用范围

既然学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;
  }