首页 > 代码库 > Trie树
Trie树
Trie树也称字典树，因为其效率很高，所以在在字符串查找、前缀匹配等中应用很广泛，其高效率是以空间为代价的。利用串构建一个字典树，这个字典树保存了串的公共前缀信息，因此可以降低查询操作的复杂度。
下面以单词为例，插入、查找和删除实现
#define MaxN 26typedef struct TrieNode{ bool isStr; //标记是否构成单词 struct TrieNode *next[MaxN];}Trie;void InsertWords(Trie *root, const char *s){ if(root == NULL || *s == ‘\0‘) return; Trie *p = root; while(*s != ‘\0‘) { if(p->next[*s-‘a‘]==NULL) { Trie *temp = new Trie(); for(int i = 0; i< MaxN; i++) { temp->next[i] = NULL; } temp->isStr = false; p->next[*s-‘a‘] = temp; p = p->next[*s-‘a‘]; } else { p = p->next[*s-‘a‘]; } s++; } p->isStr = true;}int SearchWord(Trie *root, const char *s){ Trie *p = root; while(p != NULL && *s != ‘\0‘) { p = p->next[*s-‘a‘]; s++; } return (p != NULL && p->isStr == true);}void delTrie(Trie *root){ for(int i = 0; i < MaxN; i++) { if(root->next[i] != NULL) delTrie(root->next[i]); } delete root;}
Trie树
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。