概念
如果我們有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; } 新聞熱點
疑難解答
圖片精選
