692534154人阅读 评论(233333333) 收藏 举报

定义：Trie树是一种哈希树的变种，又称字典树，单词查找树或者前缀树，用于保存大量的字符串，是一种用于快速检索的多叉树结构(如英文字母的字典树是一个26叉树，数字的字典树是一个10叉树)。

例如：假设词典由下面的单词构成：
a
、
b
、
c
、
aa
、
ab
、
ac
、
ba
、
ca
、
aba
、
abc
、
baa
、
bab
、
bac
、
cab
、
abba
、
baba
、
caba
、
abaca
、
caaba

其对应的Trie树如下图所示：

思想：利用字符串的公共前缀来节约存储空间。

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

优点：利用字符串的公共前缀来节约存储空间,最大限度地减少无谓的字符串比较，查询效率比哈希表高。

 缺点：如果存在大量字符串且这些字符串基本没有公共前缀，则相应的trie树将非常消耗内存。

三个基本性质：

1. 根结点不包含字符，除根结点外每一个结点都只包含一个字符。

2. 从根结点到某一结点，路径上经过的字符连接起来，为该结点对应的字符串。

3. 每个结点的所有子结点包含的字符都不相同。

代码：

[cpp] 
view plain
copy

  1. // Trie.cpp : 定义控制台应用程序的入口点。  
  2. //Trie 称为字典树，单词查找树或者前缀树  
  3. #include “stdafx.h”  
  4. #include <iostream>  
  5. #include <assert.h>  
  6. using namespace std;  
  7.   
  8. const int MAX_NUM = 26;  
  9. //Trie 树的结点类型  
  10. struct Node  
  11. {  
  12.       bool COMPLETED ;//COMPLETED为 true时表示目前产生的一个字符串  
  13.       char ch ;  
  14.       struct Node * child[ MAX_NUM]; //26-tree->a, b ,c, …..z  
  15. };  
  16. //Trie 树类型  
  17. class Trie  
  18. {  
  19. public :  
  20.       Trie();  
  21.      ~ Trie();  
  22.       Node* CreateNewNode (char ch);// 创建一个新结点  
  23.       void InitTrie ();//初始化 Trie树  
  24.       int CharToindex (char ch);// 找到字母对应的数组下标  
  25.       int Find (const char chars [], int len);// 找到长度为 len的字符串  
  26.       void Insert (const char chars [], int len);// 插入长度为 len的字符串  
  27.       void Delete ();//删除整棵树  
  28.   
  29. private :  
  30.       void DeleteTree (Node *& root);  
  31.       Node* root ; //根结点  
  32. };  
  33.   
  34.   
  35. Trie::Trie ()  
  36. {  
  37.     root = NULL ;  
  38. }  
  39.   
  40. Trie::~Trie ()  
  41. {  
  42.   
  43. }  
  44.   
  45. Node* Trie ::CreateNewNode( char ch )//创建一个新的结点  
  46. {      
  47.       Node *new_node = new Node;  
  48.       new_node->ch = ch;  
  49.       new_node->COMPLETED = false;  
  50.   
  51.       for(int i=0; i<MAX_NUM ; i++)  
  52.      {  
  53.         new_node->child [i] = NULL;  
  54.      }           
  55.       return new_node ;  
  56. }  
  57.   
  58. void Trie ::InitTrie() //构建一棵空树  
  59. {      
  60.       root = CreateNewNode (‘ ‘);  
  61. }  
  62.   
  63. int Trie ::CharToindex( char ch )  
  64. {  
  65.       return ch – ‘a’;  
  66. }  
  67.   
  68. int Trie ::Find( const char chars[], int len )  
  69. {  
  70.       if (root == NULL)  
  71.      {  
  72.            cout<<” 树为空！”<< endl;  
  73.            return 0;  
  74.      }  
  75.   
  76.       Node* ptr = root;  
  77.       int i = 0;  
  78.       while(i < len)  
  79.      {  
  80.            if(ptr ->child[ CharToindex(chars [i])] == NULL)  
  81.           {  
  82.                break;  
  83.           }  
  84.            ptr = ptr ->child[ CharToindex(chars [i])];  
  85.            i++;  
  86.      }  
  87.       return (i == len) && ( ptr->COMPLETED == true);  
  88. }  
  89.   
  90. void Trie ::Insert( const char chars[], int len ) //向 Trie树中插入长度为len的字符串  
  91. {  
  92.       Node* ptr = root;  
  93.        
  94.       for(int i = 0; i < len ; i++)  
  95.      {  
  96.            if(ptr ->child[ CharToindex(chars [i])] == NULL)  
  97.           {  
  98.                ptr->child [CharToindex( chars[i ])] = CreateNewNode (chars[ i]);  
  99.           }  
  100.            ptr = ptr ->child[ CharToindex(chars [i])];  
  101.      }  
  102.       ptr->COMPLETED = true;  
  103. }  
  104.   
  105. void Trie ::Delete() //利用递归删除整棵树  
  106. {  
  107.    DeleteTree(root );  
  108. }  
  109.   
  110. void Trie ::DeleteTree( Node *&Root )//利用递归删除整棵树 注意此处应该加上应用  
  111. {  
  112.       if (Root == NULL) //递归出口  
  113.      {  
  114.            return;  
  115.      }  
  116.        
  117.       for (int i=0; i<MAX_NUM ; i++)  
  118.      {  
  119.            if (Root ->child[ i] != NULL )  
  120.           {  
  121.                DeleteTree(Root ->child[ i]);  
  122.           }  
  123.      }  
  124. //   if(Root->ch == ‘ ‘)  
  125. //   {  
  126. //        cout<<“zha'”<<endl;  
  127. //   }  
  128.       delete Root ;  
  129.       Root = NULL ;         
  130. }  
  131.   
  132. int _tmain (int argc, _TCHAR * argv[])  
  133. {  
  134.       char *a = “ten”;  
  135.       char *b = “tea”;  
  136.       Trie trie ;  
  137.       trie.InitTrie ();  
  138.       trie.Insert (a, 3);  
  139.       trie.Insert (b, 3);  
  140.       cout<<trie .Find( a,3)<<endl ;  
  141.       trie.Delete ();  
  142.     cout<<trie .Find( b,3)<<endl ;  
  143.   
  144.       system(“pause” );  
  145.       return 0;  
  146. }