前缀树
功能：以树的形式存放单词组
例：
in
inter
input
apple
append
红色表示一个单词的结束
代码
先给出代码，运行了解一下前缀树的用处：
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
typedef struct Tree
{
int count;
struct Tree *child[26];
}Node,*Trie_node;
Node *CreateTrie()
{
Node *node = (Node*)malloc(sizeof(Node));
memset(node, 0, sizeof(Node));
return node;
}
void insert_node(Trie_node root,char *str)
{
if(root == NULL||*str == '\0')
return;
Node *t = root;
char *p = str;
while(*p!='\0')
{
if(t->child[*p-'a']==NULL)
{
Node *tmp = CreateTrie();
t->child[*p-'a'] = tmp;
}
t = t->child[*p-'a'];
p++;
}
t->count++;
}
void search_str(Trie_node root,char *str)
{
if(NULL==root || *str=='\0')
{
printf("trie is empty or str is null\n");
return;
}
Node *t = root;
char *p = str;
while(*p!='\0')
{
if(t->child[*p-'a'] != NULL)
{
t = t->child[*p-'a'];
p++;
}
else
{
break;
}
}
if(*p == '\0')
{
if(t->count == 0)
{
printf("该字符串不在trie树中，但该串是某个单词的前缀\n");
}
else
{
printf("该字符串在该trie树中\n");
}
}
else
{
printf("该字符串不在trie树中\n");
}
}
void del(Trie_node root) //释放整个字典树占的堆空间
{
int i;
for(i=0;i<26;i++)
{
if(root->child[i]!=NULL)
del(root->child[i]);
}
free(root);
}
int main()
{
int i, n, h;
char str[20];
printf("请输入要创建数的大小：\n");
scanf("%d",&n);
printf("请输入要存的单词：\n");
Trie_node root=NULL;
root=CreateTrie();
if(root==NULL)
printf("创建trie树失败\n");
for(i=0;i<n;i++)
{
scanf("%s",str);
insert_node(root,str);
}
printf("tree建立完成\n");
printf("请输入要查询的单词的个数：\n");
scanf("%d",&h);
i = 0;
while(i<h)
{
printf("请输入要查询的单词：\n");
scanf("%s",str);
search_str(root,str);
i++;
printf("\n");
}
del(root);
return 0;
}
下面我们讲解如何构建前缀树
我认为前缀树就像链表一样，每一个节点存一个字母和一个用来判断该字母是否是单词的最后一个字母的东西（可以是int count,count等于不同时表示不同的情况），显然这个链表不是单链表，那就意味着一个节点可能需要被多个节点连接，那我们在一个节点里就需要多个连接下一个节点的指针，而且需要判断下一个字母去哪一个分支节点，要解决上面两个问题我们可以用以下方式定义结构体：
typedef struct Tree
{
int count;
struct Tree *child[26];
}Node,*Trie_node;
可以看到我们在结构体里面定义了一个struct Tree *child[26] 这个数组存的是指针，child[0]，child[1],…,child[26]都是指针，它们可以指向下一个节点，那么如何让它知道下一个要判断的字母在哪一个节点里或者不在呢，这就是定义数组大小为26的目的了，我们用下标找出下一个字母所在的节点。
创建节点
Node *CreateTrie()
{
Node *node = (Node*)malloc(sizeof(Node));
memset(node, 0, sizeof(Node));
return node;
}
memset(node, 0, sizeof(Node));这行代码将节点所分配到的所有内存一次性初始化为0。
你可能会问那字母存在哪儿呢？下面告诉你。
将单词放入节点
void insert_node(Trie_node root,char *str)
{
if(root == NULL||*str == '\0')
return;
Node *t = root;
char *p = str;
while(*p!='\0')
{
if(t->child[*p-'a']==NULL)
{
Node *tmp = CreateTrie();
t->child[*p-'a'] = tmp;
}
t = t->child[*p-'a'];
p++;
}
t->count++;
}
child[p-‘a’]是为了更好找到指向不同字母所在的节点的指针。比如，a就在child[0]所指的节点，b就在child[1]所指的节点。其实我们并没有死板的存字母，而是用p-'a’的方式存字母。所以child数组不仅存了字母还用来指向下一个节点。
查询
void search_str(Trie_node root,char *str)
{
if(NULL==root || *str=='\0')
{
printf("trie is empty or str is null\n");
return;
}
Node *t = root;
char *p = str;
while(*p!='\0')
{
if(t->child[*p-'a'] != NULL)
{
t = t->child[*p-'a'];
p++;
}
else
{
break;
}
}
if(*p == '\0')
{
if(t->count == 0)
{
printf("该字符串不在trie树中，但该串是某个单词的前缀\n");
}
else
{
printf("该字符串在该trie树中\n");
}
}
else
{
printf("该字符串不在trie树中\n");
}
}
释放内存
void del(Trie_node root)
{
int i;
for(i=0;i<26;i++)
{
if(root->child[i]!=NULL)
del(root->child[i]);
}
free(root);
}
主函数
int main()
{
int i, n, h;
char str[20];
printf("请输入要创建数的大小：\n");
scanf("%d",&n);
printf("请输入要存的单词：\n");
Trie_node root=NULL;
root=CreateTrie();
if(root==NULL)
printf("创建trie树失败\n");
for(i=0;i<n;i++)
{
scanf("%s",str);
insert_node(root,str);
}
printf("tree建立完成\n");
printf("请输入要查询的单词的个数：\n");
scanf("%d",&h);
i = 0;
while(i<h)
{
printf("请输入要查询的单词：\n");
scanf("%s",str);
search_str(root,str);
i++;
printf("\n");
}
del(root);
return 0;
}