6-06 2,853 views
字典树，又名Trier树，可以用于单词的查找和统计。
字典树的示例如下图所示，其中，若根节点为第0层，则第k层节点表示字典中单词前k个字符，从根节点至树中标黄节点的路径表示以该节点字符为末尾的单词，例如，too、tooth、tea、two等。
字典树中的节点可用以下结构体表示:
|
1 2 3 4 5 6 7 |
typedef struct TNode { char value;//表示该节点存储的字符 int count;//表示以该节点字符为末尾的单词出现的次数 bool endFlag;//表示该节点是否是单词的末尾 TNode* childList[26];//表示下一个字符 }TNode,*DTree; |
字典树的初始化和插入单词操作:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 |
//初始化字典树 void Init(DTree &tree) { int i; tree=(DTree)malloc(sizeof(TNode)); tree->value = ' ';//根节点的字符为空 tree->count = 0; tree->endFlag = false; for (i=0;i<26;i++) tree->childList[i] = NULL; } //将单词插入字典树中 //从根节点开始从上至下，将单词字符从左至右逐步插入到字典树中 void Insert(DTree tree,char string[],int len) { int i,j; TNode* node = tree; for (i=0;i<len;i++) { //若节点存在，则直接访问下一个节点 //若该节点是单词最后一个字符，则将endFlag置为true，并将count加1 if (node->childList[string[i]-'a']!=NULL) { node = node->childList[string[i]-'a']; if (i==len-1) { node->endFlag = true; node->count++; } } //若节点不存在，则新建节点并初始化 //若该节点是单词最后一个字符，则将endFlag置为true，否则置为false，并将count加1 else { node->childList[string[i]-'a'] = (TNode*)malloc(sizeof(TNode)); node = node->childList[string[i]-'a']; node->value = string[i]; for (j=0;j<26;j++) node->childList[j] = NULL; node->endFlag = false; if (i==len-1) { node->endFlag = true; node->count++; } } } } |
字典树可用于计算某个文本中出现次数最多的前k个单词：遍历文本中的单词，将每个单词插入到字典树中，重复的单词实际不再添加，而是将原有单词末尾节点中的count加1，最后，字典树中根节点到所有endFlag为true的节点的路径为文本中出现的所有单词，节点中的count值为这些单词出现的次数，通过排序可以得到出现次数最多的前k个单词。