字典树，又名Trier树，可以用于单词的查找和统计。

字典树的示例如下图所示，其中，若根节点为第0层，则第k层节点表示字典中单词前k个字符，从根节点至树中标黄节点的路径表示以该节点字符为末尾的单词，例如，too、tooth、tea、two等。 

字典树

字典树中的节点可用以下结构体表示:



    

  1. typedef struct TNode 
    2. 

  2. { 
    3. 

  3.     char value;//表示该节点存储的字符 
    4. 

  4.     int count;//表示以该节点字符为末尾的单词出现的次数 
    5. 

  5.     bool endFlag;//表示该节点是否是单词的末尾 
    6. 

  6.     TNode* childList[26];//表示下一个字符 
    7. 

  7. }TNode,*DTree; 
    8. 



 字典树的初始化和插入单词操作:




    

  1. //初始化字典树 
    2. 

  2. void Init(DTree &tree) 
    3. 

  3. { 
    4. 

  4.     int i; 
    5. 

  5.     tree=(DTree)malloc(sizeof(TNode)); 
    6. 

  6.     tree->value = ‘ ‘;//根节点的字符为空 
    7. 

  7.     tree->count = 0; 
    8. 

  8.     tree->endFlag = false; 
    9. 

  9.     for (i=0;i<26;i++) tree->childList[i] = NULL; 
    10. 

  10. } 
    11. 

  11.  
    12. 

  12. //将单词插入字典树中 
    13. 

  13. //从根节点开始从上至下，将单词字符从左至右逐步插入到字典树中 
    14. 

  14. void Insert(DTree tree,char string[],int len) 
    15. 

  15. { 
    16. 

  16.     int i,j; 
    17. 

  17.     TNode* node = tree; 
    18. 

  18.     for (i=0;i<len;i++) 
    19. 

  19.     { 
    20. 

  20.         //若节点存在，则直接访问下一个节点 
    21. 

  21.         //若该节点是单词最后一个字符，则将endFlag置为true，并将count加1 
    22. 

  22.         if (node->childList[string[i]-‘a’]!=NULL) 
    23. 

  23.         { 
    24. 

  24.             node = node->childList[string[i]-‘a’]; 
    25. 

  25.             if (i==len-1)  
    26. 

  26.             { 
    27. 

  27.                 node->endFlag = true; 
    28. 

  28.                 node->count++; 
    29. 

  29.             } 
    30. 

  30.         } 
    31. 

  31.         //若节点不存在，则新建节点并初始化 
    32. 

  32.         //若该节点是单词最后一个字符，则将endFlag置为true，否则置为false，并将count加1 
    33. 

  33.         else 
    34. 

  34.         { 
    35. 

  35.             node->childList[string[i]-‘a’] = (TNode*)malloc(sizeof(TNode)); 
    36. 

  36.             node = node->childList[string[i]-‘a’]; 
    37. 

  37.             node->value = string[i]; 
    38. 

  38.             for (j=0;j<26;j++) node->childList[j] = NULL; 
    39. 

  39.             node->endFlag = false; 
    40. 

  40.             if (i==len-1)  
    41. 

  41.             { 
    42. 

  42.                 node->endFlag = true; 
    43. 

  43.                 node->count++; 
    44. 

  44.             }            
    45. 

  45.         } 
    46. 

  46.     } 
    47. 

  47. } 
    48. 



字典树可用于计算某个文本中出现次数最多的前k个单词：遍历文本中的单词，将每个单词插入到字典树中，重复的单词实际不再添加，而是将原有单词末尾节点中的count加1，最后，字典树中根节点到所有endFlag为true的节点的路径为文本中出现的所有单词，节点中的count值为这些单词出现的次数，通过排序可以得到出现次数最多的前k个单词。