字典树trie

又称单词查找树，Trie树，是一种树形结构，是一种哈希树的变种。典型应用是用于1.统计，2.排序，3.保存大量的字符串

优点：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高
基本操作：

• 插入
• 查找

• 删除

  如给出字符串”abc”,”ab”,”bd”,”dda”，根据该字符串序列构建一棵Trie树
  

例题：HDU 1671 Phone List
思路：边插入边查找是否出现公共前缀

定义

struct trie
{
    int data;//每个节点储存的信息
    struct trie *next[10];//分支，根据具体情况定义分支的数目
}
1
2
3
4
5

插入的代码实现

void creattrie(char a[])
{
    trie *L = &La;
   for (int i = 0; i < strlen(a); i++)
  {
        if (L->next[a[i]-'0'] == NULL)//此时的根节点没有该分支
    {
        trie *p=new trie;//动态分配一个节点
        init(p);
        L->next[a[i]-'0'] = p;//指向新开辟的节点
            p->data = 0;
        L = L->next[a[i] - '0'];//指向下一层
    }
    else
         L = L->next[a[i] - '0'];//指向下一层
  }
  p->data = 1;//字符串的最后一个字符，标记为1
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

查找的代码实现

int find(char c[])
{
    int len = strlen(c);
    trie *p = &La;
    for(int i=0; i<len; ++i)
    {
        int id = c[i]-'0';
        p = p->next[id];
        if(p == NULL)   //若为空集，表示不存以此为前缀的串
            return 0;
        if(p->data == 1)   //字符集中已有串是此串的前缀
            return 1;
    }
    return 1;   //此串是字符集中某串的前缀
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

删除的代码实现

通过递归向下删除
int deal(trie* T)
{
    int i;
    if (T == NULL)
        return 0;
    for (i = 0; i<10; i++)
    {
        if (T->next[i] != NULL)
            deal(T->next[i]);
    }
    if (T != &La)
        delete T;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16