trie树（字典树）的部分简单实现

什么是trie树（字典树）？

trie树是一种用于快速检索的多叉树结构。和二叉查找树不同，在trie树中，每个结点上并非存储一个元素。

trie树把要查找的关键词看作一个字符序列。并根据构成关键词字符的先后顺序构造用于检索的树结构。在trie树上进行检索类似于查阅英语词典。一棵m度的trie树或者为空，或者由m

棵m度的trie树构成。例如，电子英文词典，为了方便用户快速检索英语单词，可以建立一棵trie树。例如词典由下面的单词构成：a、b、c、aa、ab、ac、ba、ca、aba、abc、baa

bab、bac、cab、abba、baba、caba、abaca、caaba.

下图形象的展示下trie树：

例如在上面图中的trie树中查找单词 aba的流程：

(1)在trie树上进行检索总是始于根结点。

(2)取得要查找关键词的第一个字母（例如 a ），并根据该字母选择对应的子树并转到该子树继续进行检索。

(3)在相应的子树上，取得要查找关键词的第二个字母（例如 b），并进一步选择对应的子树进行检索。

(4) ...

(5)在某个结点处，关键词的所有字母已被取出，则读取附在该结点上的信息，即完成查找。

我的实现代码如下：

 #include <iostream>

 #include <cstdlib>

 #include <cstdio>

 #define null NULL

 const int num_chars = ;

 /*普通的树结点*/

 template <typename Entry>

 class tree_node

 {

     public:

         Entry data;

         tree_node* first_child;

         tree_node* next_sibling;

         tree_node():first_child(null),next_sibling(null){}

         tree_node(const Entry& x):data(x),first_child(null),next_sibling(null){}

 };

 /*trie树,是一种用于快速检索的多叉树结构。*/

 //trie树的实现

 class trie

 {

     protected:

         class trie_node  //定义trie树的结点

         {

             char* data;

             trie_node* branch[num_chars]; //常量num_chars = 26

             trie_node();

         };

         trie_node* root; //根节点

     public:

         trie(); //无参数构造函数

         trie(trie& tr); //复制构造函数

         virtual ~trie(); //析构函数

         int trie_search(const char* word,char* entry) const; //查找操作

         int insert(const char* word,const char* entry); //插入操作

         int remove(const char* word,char* entry); //删除操作

 };

 //trie_node的构造函数

 trie::trie_node::trie_node()

 {

     data = null;

     for(int i=;i<num_chars;i++)

         branch[i] = null;

 }

 //trie的构造函数

 trie::trie()

 {

     root = null;

 }

 //trie的检索,查找在某个字符路径结点上的存放的值，并将其放在entry中。比如找对应"abc"的结点上的值并且存放在entry中。

 int trie::trie_search(const char* word,char* entry) const

 {

     int position = ;

     char char_code;

     trie_node* loaction = root;

     while(location != null && *word != null)

     {

         if(*word >= 'A' && *word < 'Z') char_code = *word - 'A';

         else if(*word >= 'a' && *word <= 'z') char_code = *word - 'a';

         else return ;

         location = location->branch[char_code];

         position++;

         word++;

     }

     if(location != null && location->data != null)

     {

         strcpy(entry,location->data);

         return ;

     }

     else return ;

 }

 //插入操作,此时是往指定的字符串的结点上存放指定的字符串。比如在"abc"位置上防"jeaven"。

 int trie::insert(const char* word,const char* entry)

 {

     int result = ;

     int position = ;

     if(root == NULL) root = new tire_node();

     char char_code;

     tire_node* location = root;

     while(location != null && *word != null)

     {

         if(*word >= 'a' && *word <= 'z') char_code = *word - 'a';

         else if(*word >= 'A' && *word <= 'Z') char_code = *word - 'A';

         else return ;

         if(location->branch[char_code] == null)

             location->branch[char_code] = new trie_node();

         location = location->branch[char_code];

         position++;

         word++;

     }

     if(location->branch[char_code] != null) result = ;

     else

     {

         location->data = new char[strlen(entry)+];

         strcpy(location->data,entry);

     }

     return result;

 }

  //删除操作，删除在某字符串路径上的结点存放的值，并且将其放到entry中

 int trie::remove(const char* word,char* entry)

 {

     if(root == null) return ;

     trie_node* cur = root;

     char char_code;

     while(*word != null)

     {

         if(*word >= 'a' && *word <= 'z') char_code = *word - 'a';

         else if(*word >= 'A' && *word <= 'Z') char_code = *word - 'A';

         else return ;

         if(cur->branch[char_code] != null) cur = cur->branch[char_code];

     }

     *entry = cur->data;

     delete cur;

     return ;

 }

参考：[1] https://www.cnblogs.com/konrad/p/7746030.html

[2] http://blog.csdn.net/guin_guo/article/details/48858339

巴特西

trie树（字典树）的部分简单实现

最新文章

热门文章