字典树（Trie树）

1. trie基础

(1) 是什么？

Trie，又称单词查找树或键树，是一种树形结构，是一种哈希树的变种。

(2) 性质

根节点不包含字符，除根节点外每一个节点都只包含一个字符
从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串
每个节点的所有子节点包含的字符都不相同

例如，单词序列a, to, tea, ted, ten, i, in, inn，对应的trie。

(3) 应用

用于统计和排序大量的字符串，但不仅限于字符串，所以经常被搜索引擎系统用于文本词频统计。

(4) 优点

最大限度地减少无谓的字符串比较
查询效率比哈希表高

2. 一个例子

 #include <stdio.h>

 #include <string.h>

 #include <stdlib.h>  

 #define MAX 256//ascii码有256个字符，故每棵树的子节点最多有256个

 #define MAXLEN 256//单词最长为256  

 typedef struct TrieNode

 {

     int count;

     struct TrieNode *next[MAX];

 }TrieNode;    

 //插入一个单词

 void Insert(char *word,TrieNode *root)  

 {

     int i;

     TrieNode *cur;

     if(word[]=='\0')

         return;

     cur=root;

     for(i=;word[i]!='\0';i++)

     {

         if(cur->next[word[i]]==NULL)

         {

             TrieNode *newNode = (TrieNode *)malloc(sizeof(TrieNode));

             memset(newNode,,sizeof(TrieNode));

             cur->next[word[i]]=newNode;

         }

         cur=cur->next[word[i]];

     }  

     cur->count++;

     return;

 }  

 //创建树输入每个单词，以回车结束，则单词被插入树中，碰到*停止树的创建

 void Construct(TrieNode *&root)

 {

      char inStr[MAXLEN];

      int size=;

      root = (TrieNode *)malloc(sizeof(TrieNode));

      memset(root,,sizeof(TrieNode));

      while()

      {

          scanf("%s",inStr);

          if(strcmp(inStr,"*")==)

              break;

          Insert(inStr,root);

      }

      return;

 }  

 //遍历整棵树

 void Traverse(TrieNode *curP)

 {

     static char theWord[MAXLEN];

     static int pos=;

     int i;

     if(curP==NULL)

         return;

     if(curP->count)

     {

         theWord[pos]='\0';

         printf("%s:%d\n",theWord,curP->count);

     }

     for(i=;i<MAX;i++)

     {

         theWord[pos++]=i;

 //从这句话可以看出在递归调用子节点前，子节点的值已经加入到单词中了

         Traverse(curP->next[i]);

         pos--;

     }

     return;

 }  

 //查找一个单词是不是在树中

 bool Find(TrieNode *root,char *word)

 {

     int i;

     TrieNode *cur;

     cur=root;

     for(i=;word[i]!='\0';i++)

     {

         if(cur->next[word[i]]==NULL)

         {

             return false;

         }

         cur=cur->next[word[i]];

     }  

     if(cur->count)

         return true;

     else

         return false;

 }  /* 何问起 hovertree.com */

 int main()

 {

     TrieNode *root;

     char str[MAXLEN];

     Construct(root);

     printf("\n");

     Traverse(root);

     printf("\n");

     while()

     {

         scanf("%s",str);

         if(strcmp(str,"*")==)

             break;

         printf("%s:%d\n",str,Find(root,str));

     }  

     return ;

 }

巴特西

字典树（Trie树）

最新文章

热门文章