trie树（字典树）

1. trie树，又名字典树，顾名思义。它是能够用来作字符串查找的数据结构。它的查找效率比散列表还要高。

trie树的建树：

比方有字符串”ab” ,“adb”,“adc” 能够建立字典树如图：

trie树（字典树）

树的根节点head不存储信息，它有26个next指针，分别相应着字符a,b,c等。插入字符串ab时，next[‘a’-‘a’]即next[0]为空，这是申请一个结点放在next[0]的位置，插入字符串db时。next[‘d’-‘a’]即next[3]为空，这时申请一个结点tmp放在next[3]的位置，接下来,tmp的后向结点tmp->next[‘a’-‘a’]即tmp->next[0]为空，在申请一个结点放在tmp->next[0]的位置。插入字符串dc时，检查head->next[3]不为空，然后检查tmp->next[2]为空。这时申请一个结点放在tmp->next[2]的位置。

字典树的建树过程就是字符串不断插入的过程。

字典树的查找能够依照例如以下步骤进行：比方查找字符串”dc”,先检查head->next[3]是否为空，假设为空返回。若不为空。再检查下个结点的next[2]是否为空。假设为空返回

2. 字典树的应用

（1）用于查字符串的字典树：

用于查找字符串的字典树，输的结点结构体能够定义为：

struct node
{
bool isword;
node *next[26];
};

当中isword用于推断从根节点到此结点是否构成一个单词，next数组用于指示26个结点指针，这里假定全部单词都使用小写英文字母来表示。

# include <iostream>
# include <cstdlib>
# include <cstring>
using namespace std;
struct node
{
bool isword;
node *next[26];
};

node *head=NULL;
void insert(char s[])
{
node *p=head;
int len=strlen(s);
int i=0;
for(i=0;i<len;i++)
{
	if(p->next[s[i]-'a']==NULL)
	{
	node *tmp=(node *)malloc(sizeof(node));
	tmp->isword=false;
	int j=0;
	for(j=0;j<26;j++)
		tmp->next[j]=NULL;
	p->next[s[i]-'a']=tmp;
	p=tmp;
	}
	else
		p=p->next[s[i]-'a'];
}
p->isword=true;
}

int find(char *s)
{
node *p=head;
if(p==NULL)
	return 0;
while(p!=NULL&&*s!='

trie树（字典树）

相关推荐