字典樹的基本知識(shí)及使用C語言的相關(guān)實(shí)現(xiàn)

更新時(shí)間：2015年08月07日 11:39:42 作者：zinss26914

這篇文章主要介紹了字典樹的基本知識(shí)及使用C語言的相關(guān)實(shí)現(xiàn),這也是ACM等計(jì)算機(jī)考試和競賽題目的基本知識(shí),需要的朋友可以參考下

概念

如果我們有and,as,at,cn,com這些關(guān)鍵詞，那么trie樹（字典樹）是這樣的：

201587113000993.png (702×500)

從上面的圖中，我們或多或少的可以發(fā)現(xiàn)一些好玩的特性。

第一：根節(jié)點(diǎn)不包含字符，除根節(jié)點(diǎn)外的每一個(gè)子節(jié)點(diǎn)都包含一個(gè)字符。

第二：從根節(jié)點(diǎn)到某一節(jié)點(diǎn)，路徑上經(jīng)過的字符連接起來，就是該節(jié)點(diǎn)對(duì)應(yīng)的字符串。

第三：每個(gè)單詞的公共前綴作為一個(gè)字符節(jié)點(diǎn)保存。

使用范圍

既然學(xué)Trie樹，我們肯定要知道這玩意是用來干嘛的。

第一：詞頻統(tǒng)計(jì)。

可能有人要說了，詞頻統(tǒng)計(jì)簡單啊，一個(gè)hash或者一個(gè)堆就可以打完收工，但問題來了，如果內(nèi)存有限呢？還能這么

玩嗎？所以這里我們就可以用trie樹來壓縮下空間，因?yàn)楣睬熬Y都是用一個(gè)節(jié)點(diǎn)保存的。

第二: 前綴匹配

就拿上面的圖來說吧，如果我想獲取所有以"a"開頭的字符串，從圖中可以很明顯的看到是：and,as,at，如果不用trie樹，

你該怎么做呢？很顯然樸素的做法時(shí)間復(fù)雜度為O(N2) ，那么用Trie樹就不一樣了，它可以做到h，h為你檢索單詞的長度，

可以說這是秒殺的效果。

數(shù)據(jù)結(jié)構(gòu)定義

  #define MAX 26 // 字符集大小 
   
  typedef struct trieNode { 
    struct trieNode *next[MAX]; 
    int count; // 記錄該字符出現(xiàn)次數(shù) 
  } trieNode;

next數(shù)組表示每層有多少類的數(shù)，如果只是小寫字母，26即可

實(shí)現(xiàn)方法
搜索字典項(xiàng)目的方法：

從根節(jié)點(diǎn)開始一次搜索
獲取要查找關(guān)鍵詞的第一個(gè)字母，并根據(jù)該字母選擇對(duì)應(yīng)的子樹并轉(zhuǎn)到該子樹繼續(xù)進(jìn)行檢索
在相應(yīng)的子樹上，獲取要查找關(guān)鍵詞的第二個(gè)字母，并進(jìn)一步選擇對(duì)應(yīng)的子樹進(jìn)行檢索
迭代過程
在某個(gè)節(jié)點(diǎn)處，關(guān)鍵詞的所有字母已被取出，則讀取附在該結(jié)點(diǎn)上的信息，即完成查找

其他操作類似

實(shí)現(xiàn)模板

初始化根結(jié)點(diǎn)

  /** 
   * 初始化Trie樹根結(jié)點(diǎn) 
   */ 
  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 ++; 
    } 
  }

統(tǒng)計(jì)查找單詞數(shù)量

  /** 
   * 統(tǒng)計(jì)前綴出現(xiàn)次數(shù) 
   */ 
  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); 
  }

時(shí)間復(fù)雜度
插入、查找的時(shí)間復(fù)雜度均為O(n),n為字符串的長度

空間復(fù)雜度較高，O(26^n),典型空間換時(shí)間

參考題目

ac代碼：

  #include <stdio.h> 
  #include <stdlib.h> 
  #include <string.h> 
   
  #define MAX 26 // 字符集大小 
   
  typedef struct trieNode { 
    struct trieNode *next[MAX]; 
    int count; // 記錄該字符出現(xiàn)次數(shù) 
  } trieNode; 
   
   
  /** 
   * 初始化Trie樹根結(jié)點(diǎn) 
   */ 
  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 ++; 
    } 
  } 
   
  /** 
   * 統(tǒng)計(jì)前綴出現(xiàn)次數(shù) 
   */ 
  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; 
   
    // 初始化根結(jié)點(diǎn) 
    initTrie(&root); 
   
    while (gets(str) && str[0] != '\0') { 
      // 插入Trie樹 
      insert(str, root); 
    } 
   
    // 查找前綴出現(xiàn)次數(shù) 
    while (gets(str) && str[0] != '\0') { 
      printf("%d\n", count(str, root)); 
    } 
   
    delTrie(root); 
   
    return 0; 
  }