字典树，又名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个单词。