首页 > 代码库 > trie树的建立方法汇总
trie树的建立方法汇总
方法一:孩子兄弟表示法
即对于某一个点,记录他的第一个孩子以及他的同父亲的下一个儿子。
具体代码如下:
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define MAXN 11000005 using namespace std; struct letter{ char d; int son,bro; };//这里运用的是数组模拟指针 char line[35005]; int n,best=0,gs=0; letter tr[MAXN]; void insert(char s[]){ int len=strlen(s),now=0; for (int i=0;i<len;i++){ if (tr[now].son==0){//没有儿子直接添加 tr[++gs].d=s[i]; tr[gs].son=tr[gs].bro=0; tr[now].son=gs; now=gs; } else{//有儿子 now=tr[now].son; while (tr[now].d!=s[i] && tr[now].bro>0) now=tr[now].bro;//更新到这个点的最后一个儿子 if (tr[now].d!=s[i]){//添加 tr[++gs].d=s[i]; tr[gs].son=tr[gs].bro=0; tr[now].bro=gs; now=gs; } } } } int main() { gets(line); scanf(line,"%d",&n); tr[0].son=tr[0].bro=0; for (int i=1;i<=n;i++){ gets(line); insert(line); } printf("%d\n",best); return 0; }
方法二:指针表示法
(未完待续。。。)
trie树的建立方法汇总
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。