trie树的建立方法汇总

时间：2023-03-22 12:21:14

方法一：孩子兄弟表示法

即对于某一个点，记录他的第一个孩子以及他的同父亲的下一个儿子。

具体代码如下：

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#define MAXN 11000005

using namespace std;

struct letter{

    char d;

    int son,bro;

};//这里运用的是数组模拟指针

char line[];

int n,best=,gs=;

letter tr[MAXN];

void insert(char s[]){

    int len=strlen(s),now=;

    for (int i=;i<len;i++){

        if (tr[now].son==){//没有儿子直接添加

            tr[++gs].d=s[i];

            tr[gs].son=tr[gs].bro=;

            tr[now].son=gs;

            now=gs;

        }

        else{//有儿子

            now=tr[now].son;

            while (tr[now].d!=s[i] && tr[now].bro>) now=tr[now].bro;//更新到这个点的最后一个儿子

            if (tr[now].d!=s[i]){//添加

                tr[++gs].d=s[i];

                tr[gs].son=tr[gs].bro=;

                tr[now].bro=gs;

                now=gs;

            }

        }

    }

}

int main()

{

    gets(line);

    scanf(line,"%d",&n);

    tr[].son=tr[].bro=;

    for (int i=;i<=n;i++){

        gets(line);

        insert(line);

    }

    printf("%d\n",best);

    return ;

}

方法二：指针表示法

（未完待续。。。）

相关文章