1.总结，也称为单词搜索树，Trie树，是一种树结构，是hash树的变体。该应用程序通常用于统计、排序和保存大量字符串(但不限于字符串)，因此它经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀节省存储空间，最大限度地减少不必要的字符串比较，比哈希表具有更高的查询效率。Trie树结构的优点如下：1)子节点数量不受限制；2)用户自定义输入序列化突破了特定语言和应用的限制，成为通用框架；3)可以限制最大令牌序列长度；4)根据设定的阈值输出重复的字符串；5)提供单串频率搜索功能；6)速度快，两分钟就能完成1998年1月《人民日报》(19056行)的复串抽取。2.属性它有三个基本属性：1)根节点不包含字符，除根节点外的每个节点只包含一个字符。2)从根节点到一个节点，通过路径的字符被连接起来，形成对应于该节点的字符串。3)每个节点的所有子节点包含不同的字符。3.基本操作基本操作包括：搜索、插入和删除，但删除操作很少。我这里只实现了整棵树的删除操作，单个单词的删除操作也很简单。4.实现方法搜索字典项的方法如下：(1)从根节点开始搜索；(2)获取待搜索关键词的第一个字母，根据该字母选择对应的子树，并前往该子树继续搜索；(3)在对应的子树中，获取待搜索关键词的第二个字母，进一步选择对应的子树进行搜索。(4)迭代过程.(5)在某个节点，如果关键字的所有字母都已取出，则读取该节点所附的信息，即搜索完成。其他操作类似于处理5。特里原则——特里的核心思想是以空间换时间。字符串的公共前缀被用来降低查询时间的成本，从而提高效率。6.代码复制的代码如下：const int branchNum=26//声明常量int I；struct Trie _ node { boolisStr//记录此处是否形成字符串。trie _ node * next[BranchNum]；//指向每个子树的指针，下标0-25代表26个字符trie _ node(): isstr(false){ memset(next，null，sizeof(next))；}};class Trie { public : Trie()；void insert(const char * word)；boolsearch(char * word)；voiddeleteTrie(Trie _ node * root)；//虚空之地(Trie _ node * root)；//new add private : Trie _ node * root；};Trie : Trie(){ root=new Trie _ node()；} void Trie :3360 InserT(const char * word){ Trie _ node * location=root；while(* word){ if(location-next[* word-' a ']==null)//如果不存在，则建立{ Trie _ node * tmp=new Trie _ node()；location-next[* word-' a ']=tmp；} location=location-next[* word-' a ']；//插入的每一步都相当于一个新的字符串经过，指针要下移一个字；} location-isStr=true；//到达末尾并标记一个字符串} booltrie :3360 search(char * word){ trie _ node * location=root；while(* word location){ location=location-next[* word-' a ']；字；}返回(位置！=NULL位置-isStr)；} void Trie : delete Trie(Trie _ node * root){ for(I=0；i branchNumi ) { if(root-next[i]！=NULL){ DeleteTrie(root-next[I])；} } deleteroot} void main()//simple test { Trie t；t . insert(' a ')；t.insert('放弃')；char * c='放弃'；t .插入(c)；t . insert(' abashed ')；if(t . search(' abashed '){ printf(' true n ')；//}}已被插入。有时候，我们会遇到字符串的排序。如果采用一些经典的排序算法，时间复杂度一般为O(n*lgn)，但如果采用Trie树，时间复杂度仅为O(n)。Trie树，也称为字典树，可以从字面上理解。这棵树的结构就像一本英语词典，相邻的单词有相同的前缀。其时间复杂度低的原因是采用了以空间换时间的策略。

下图是一个用于对字符串进行排序的Trie树(这里我们假设所有字符串都是小写字母)。每个节点有26个分支，每个分支代表一个字母，节点在从根节点到这个节点的途中存储由字符组成的字符串。将每个字符串插入到trie树中，当它到达一个特定的结束节点时，在这个节点上标记它，比如插入' afb '，其中第一个字母是A，然后第二个字母是F，然后第三个字母是B，然后第三个字母是B，由于字符串的最后一个字符是' '，它结束并且不再向下，然后标记afb.count这个节点。

实现代码如下（克、风险投资都编译通过):复制代码代码如下： #包含iostream #包含string.husing命名空间标准#定义全国矿工联合会类节点{ public: int count//记录该处字符串个数node * char _ arr[NUM]；//分支char * current _ str//记录到达此处的路径上的所有字母组成的字符串node()；};类trie { public : Node * root trie()；void insert(char * str)；无效输出（节点*节点，字符**字符串，整数计数);};//程序未考虑删除动态内存int main(){ char * * str=new char *[12]；str[0]=' zbdfasd '；str[1]=' zb CFD '；str[2]=' zcdfsafaf '；str[3]=' abcdaf '；str[4]=' defdasfa '；str[5]=' fedfasfd '；str[6]=' DFD FSA '；str[7]=' dad FD '；str[8]=' DFD fasf '；str[9]=' ABC fdfa '；str[10]=' fbcdfd '；str[11]=' abcdaf '；//建立单词查找树树Trie * Trie=new Trie()；for(int I=0；12I)三插入(字符串[I])；int count=0；trie-output(trie-root，str，count)；for(int I=0；12I)cout str[I]endl；返回0;} node : node(){ count=0；for(int I=0；NUMI)char _ arr[I]=空；current_str=新字符[100];current _ str[0]=' 0 '；} trie : trie(){ root=new Node()；} void trie :3360 InserT(char * str){ int I=0；节点*父=根/将字符串[i]插入到单词查找树树中while(str[i]！='') { //如果包含字符串[i]的分支存在，则新建此分支if(parent-char _ arr[str[I]-' a ']==NULL){ parent-char _ arr[str[I]-' a ']=new Node()；//将父节点中的字符串添加到当前节点的字符串中strcat(parent-char _ arr[str[I]-' a ']-current _ str，parent-current _ str)；char str _ tmp[2]；str _ tmp[0]=str[I]；str _ tmp[1]=' 0 '；//将字符串[i]添加到当前节点的字符串中str cat(parent-char _ arr[str[I]-' a ']-current _ str，str _ tmp)；parent=parent-char _ arr[str[I]-' a ']；} else { parent=parent-char _ arr[str[I]-' a ']；}我；}家长人数；}//采用前序遍历void trie :输出(Node * Node，char** str，int count){ if(node！=空){如果(节点数！=0){ for(int I=0；我节点数；I)str[count]=node-current _ str；} for(int I=0；i NUMi ) { output(node-char_arr[i]，str，count)；} }}