字典树Trie Tree

发表于 更新于 分类于 ，

模版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
struct trie
{
    int next[26];   //指向子节点节点的下标，默认值为0则表示没有子节点，并用0-25代表'a'-'z'
    int isEnd;   //是否为一个单词的结尾
}tree[500005];
int inc;   //最后一个分配的字典树下标，用于分配新的节点下标

int insert(string s)   //插入单词
{
    int p=0;   //临时指针，指向子节点，初始指向0，即树的根
    for (int i=0;i<s.size();i++)   //遍历单词的每一个字符
    {
        if (tree[p].next[s[i]-97]) p=tree[p].next[s[i]-97];    //如果当前节点存在字母为s[i]的子节点，则将p指向该子节点
        else   //如果不存在，则创建该节点
        {
            inc++;   //分配新的下标
            tree[p].next[s[i]-97]=inc;   //将当前节点字母为s[i]的子节点指向新节点
            p=inc;   //将临时指针指向新节点
        }
    }
    if (tree[p].isEnd) return 1;   //遍历完单词后，指针p将指向单词最后一个字符所在的节点，判断该节点的单词末尾标记是否为1，如果是则说明之前添加过该单词了，返回1。
    else tree[p].isEnd=1;   //否则说明之前没添加过该单词，将其的单词末尾标记置为1，然后返回0。
    return 0;
}

int check(string s)   //检查单词是否存在
{
    int p=0;   //临时指针，指向子节点，初始指向0，即树的根
    for (int i=0;i<s.size();i++)   //遍历单词的每一个字符
    {
        if (!tree[p].next[s[i]-97]) return 0;   //如果当前节点不存在字母为s[i]的子节点，则表示该单词不存在，返回0
        p=tree[p].next[s[i]-97];   //将临时指针指向字母为s[i]的子节点
    }
    if (tree[p].isEnd) return 1;   //遍历完单词后，指针p将指向单词最后一个字符所在的节点，判断该节点的单词末尾标记是否为1，如果是则说明该单词存在，返回1，否则返回0。
    return 0;
}

解释

字典树，是一种空间换时间的数据结构，又称Trie树、前缀树，是一种树形结构，典型用于统计、排序、和保存大量字符串。利用字符串的公共前缀来减少查询时间，最大限度地减少不需要的字符串比较，查询效率比哈希树高。

根节点不包含字符，除根节点外每一个节点都只包含一个字符。
从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。

定义结构体：该结构体用来存储树的每一个节点，每个节点都包括了指向子节点的指针，以及当前节点是否为单词的结尾。
用数组线性存储树，所以指针记录的是子节点的数组下标值。
inc记录的是当前的数组下标已经分配到多少了，用于分配新的节点。

1
2
3
4
5
6
struct trie
{
    int next[26];   //指向子节点节点的下标，默认值为0则表示没有子节点，并用0-25代表'a'-'z'
    int isEnd;   //是否为一个单词的结尾
}tree[500005];
int inc;   //最后一个分配的字典树下标，用于分配新的节点下标

插入单词：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int insert(string s)   //插入单词
{
    int p=0;   //临时指针，指向子节点，初始指向0，即树的根
    for (int i=0;i<s.size();i++)   //遍历单词的每一个字符
    {
        if (tree[p].next[s[i]-97]) p=tree[p].next[s[i]-97];    //如果当前节点存在字母为s[i]的子节点，则将p指向该子节点
        else   //如果不存在，则创建该节点
        {
            inc++;   //分配新的下标
            tree[p].next[s[i]-97]=inc;   //将当前节点字母为s[i]的子节点指向新节点
            p=inc;   //将临时指针指向新节点
        }
    }
    if (tree[p].isEnd) return 1;   //遍历完单词后，指针p将指向单词最后一个字符所在的节点，判断该节点的单词末尾标记是否为1，如果是则说明之前添加过该单词了，返回1。
    else tree[p].isEnd=1;   //否则说明之前没添加过该单词，将其的单词末尾标记置为1，然后返回0。
    return 0;
}

检查单词是否存在：

1
2
3
4
5
6
7
8
9
10
11
int check(string s)   //检查单词是否存在
{
    int p=0;   //临时指针，指向子节点，初始指向0，即树的根
    for (int i=0;i<s.size();i++)   //遍历单词的每一个字符
    {
        if (!tree[p].next[s[i]-97]) return 0;   //如果当前节点不存在字母为s[i]的子节点，则表示该单词不存在，返回0
        p=tree[p].next[s[i]-97];   //将临时指针指向字母为s[i]的子节点
    }
    if (tree[p].isEnd) return 1;   //遍历完单词后，指针p将指向单词最后一个字符所在的节点，判断该节点的单词末尾标记是否为1，如果是则说明该单词存在，返回1，否则返回0。
    return 0;
}