首页 > 代码库 > 字典树Trie
字典树Trie
字典树Trie
Trie,又称字典树,前缀树(prefix tree),是一种树形结构,用于保存大量的字符串。
它的优点是:利用字符串的公共前缀来节约存储空间。查找、插入复杂度为O(n),n为字符串长度。
它有3个基本性质:
1. 根节点不包含字符,除根节点外每一个节点都只包含一个字符。
2. 从根节点到某一节点,路径上经过的字符连接起来,为该节点对应的字符串。
3. 每个节点的所有子节点包含的字符都不相同。
假设有abc,abcd,abd, b, bcd,efg,hii这7个单词,可构建字典树如下:
查找一个字符串时,我们只需从根结点按字符串中字符出现顺序依次往下走。如果到最后字符串结束时,对应的结点标记为红色,则该字符串存在;否则不存在。
插入时也只需从根结点往下遍历,碰到已存在的字符结点就往下遍历,否则,建立新结点;最后标记最后一个字符的结点为红色即可。
实现代码:
#include<cstdio> #include<cstdlib> #include<algorithm> #define MAX 26 using namespace std; typedef struct TrieNode { int count; struct TrieNode *next[MAX]; }TrieNode; void InitTrie(TrieNode **root) { *root=NULL; } TrieNode* CreateNode() { int i; TrieNode *p; p=(TrieNode *)malloc(sizeof(TrieNode)); if(!p) { printf("No enough memory!\n"); exit(-1); } p->count=1; for(i=0;i<MAX;i++) p->next[i]=NULL; return p; } void InsertTrie(TrieNode **root,char *str) { int i=0,k=0; TrieNode *p=*root; if(p==NULL) { p=*root=CreateNode(); } for(i=0;str[i]!='\0';i++) { k=str[i]-'a';// 假设全部为小写字母 if(p->next[k]) p->next[k]->count++; else p->next[k]=CreateNode(); p=p->next[k]; } } bool Search(TrieNode **root,char *str) { int i,k; TrieNode *p=*root; for(i=0;str[i]!='\0';i++) { k=str[i]-'a'; if(p->next[k]==NULL) return false; else p=p->next[k]; } return true; } int main(int argc,char *argv[]) { int n; char str[MAX]; TrieNode *root; InitTrie(&root); scanf("%d",&n); getchar(); for(int i=0;i<n;i++) { scanf("%s",str); InsertTrie(&root,str); } printf("Please input the string you want to search:\n"); scanf("%s",str); if(Search(&root,str)) printf("Find it\n"); else printf("Can Not Find it\n"); return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。