- 中文名
- 字典树
- 外文名
- trie tree
- 别 名
- 单词查找树
- 类 型
- 树形结构
- 基本操作
- 查找、插入和删除
它有3个基本性质：
其基本操作有：查找、插入和删除,当然删除操作比较少见。
说拜搜索字员辣寻典项目旋奔习的方法为：
(3) 在相应的子树上，取得要查找关键词的第二个字母,并进一步选择对应的子树进行检索。
(4) 朵狼迭代少求阀过程……
(5) 在某个结点处，关键词的所有字母已被取出，则读取附在该结点上的信息，即完成查找。
其他操多主永多作类似处理
在这道题中，我们可以用数组枚举，用哈希，用字典树，先把熟词建一棵树，然后读入文章进行比较，这种方法效率是比较高的。
对所有串建立字典树，对于两个串的最长公共前缀的长度即他们所在的结点的公共祖先个数，于是，问题就转化为当时公共祖先问题。
class Trie:
# 初始化
def __init__(self):
self.root = {}
self.end = "#"
# 添加单词
def add(self, word: str):
node = self.root
for char in word:
node = node.setdefault(char, {})
node[self.end] = None
# 搜索单词是否存在
def search(self, word):
node = self.root
for char in word:
if char not in node:
return False
node = node[char]
return self.end in node
packagecom.suning.search.test.tree.trie;
public class Trie
{
private int SIZE=26;
private TrieNode root;//字典树的根
Trie() //初始化字典树
{
root=new TrieNode();
}
private class TrieNode //字典树节点
{
private int num;//有多少单词通过这个节点,即由根至该节点组成的字符串模式出现的次数
private TrieNode[] son;//所有的儿子节点
private boolean isEnd;//是不是最后一个节点
private char val;//节点的值
private boolean haveSon;
TrieNode()
{
num=1;
son=new TrieNode[SIZE];
isEnd=false;
haveSon=false;
}
}
//建立字典树
public void insert(String str) //在字典树中插入一个单词
{
if(str==null||str.length()==0)
{
return;
}
TrieNode node=root;
char[]letters=str.toCharArray();
for(int i=0,len=str.length(); i<len; i++)
{
int pos=letters[i]-'a';
if(node.son[pos]==null)
{
node.haveSon = true;
node.son[pos]=new TrieNode();
node.son[pos].val=letters[i];
}
else
{
node.son[pos].num++;
}
node=node.son[pos];
}
node.isEnd=true;
}
//计算单词前缀的数量
public int countPrefix(Stringprefix)
{
if(prefix==null||prefix.length()==0)
{
return-1;
}
TrieNode node=root;
char[]letters=prefix.toCharArray();
for(inti=0,len=prefix.length(); i<len; i++)
{
int pos=letters[i]-'a';
if(node.son[pos]==null)
{
return 0;
}
else
{
node=node.son[pos];
}
}
return node.num;
}
//打印指定前缀的单词
public String hasPrefix(String prefix)
{
if (prefix == null || prefix.length() == 0)
{
return null;
}
TrieNode node = root;
char[] letters = prefix.toCharArray();
for (int i = 0, len = prefix.length(); i < len; i++)
{
int pos = letters[i] - 'a';
if (node.son[pos] == null)
{
return null;
}
else
{
node = node.son[pos];
}
}
preTraverse(node, prefix);
return null;
}
// 遍历经过此节点的单词.
public void preTraverse(TrieNode node, String prefix)
{
if (node.haveSon)
{
for (TrieNode child : node.son)
{
if (child!=null)
{
preTraverse(child, prefix+child.val);
}
}
return;
}
System.out.println(prefix);
}
//在字典树中查找一个完全匹配的单词.
public boolean has(Stringstr)
{
if(str==null||str.length()==0)
{
return false;
}
TrieNode node=root;
char[]letters=str.toCharArray();
for(inti=0,len=str.length(); i<len; i++)
{
intpos=letters[i]-'a';
if(node.son[pos]!=null)
{
node=node.son[pos];
}
else
{
return false;
}
}
return node.isEnd;
}
//前序遍历字典树.
public void preTraverse(TrieNodenode)
{
if(node!=null)
{
System.out.print(node.val+"-");
for(TrieNodechild:node.son)
{
preTraverse(child);
}
}
}
public TrieNode getRoot()
{
return this.root;
}
public static void main(String[]args)
{
Trietree=newTrie();
String[]strs= {"banana","band","bee","absolute","acm",};
String[]prefix= {"ba","b","band","abc",};
for(Stringstr:strs)
{
tree.insert(str);
}
System.out.println(tree.has("abc"));
tree.preTraverse(tree.getRoot());
System.out.println();
//tree.printAllWords();
for(Stringpre:prefix)
{
int num=tree.countPrefix(pre);
System.out.println(pre+""+num);
}
}
}
#define MAX 26//字符集大小
typedef struct TrieNode
{
int nCount;//记录该字符出现次数
struct TrieNode* next[MAX];
}TrieNode;
TrieNode Memory[1000000];
int allocp=0;
/*初始化*/
void InitTrieRoot(TrieNode* *pRoot)
{
*pRoot=NULL;
}
/*创建新结点*/
TrieNode* CreateTrieNode()
{
int i;
TrieNode *p;
p=&Memory[allocp++];
p->nCount=1;
for(i=0;i<MAX;i++)
{
p->next[i]=NULL;
}
return p;
}
/*插入*/
void InsertTrie(TrieNode* *pRoot,char *s)
{
int i,k;
TrieNode*p;
if(!(p=*pRoot))
{
p=*pRoot=CreateTrieNode();
}
i=0;
while(s[i])
{
k=s[i++]-'a';//确定branch
if(!p->next[k])
p->next[k]=CreateTrieNode();
else
p->next[k]->nCount++;
p=p->next[k];
}
}
//查找
int SearchTrie(TrieNode* *pRoot,char *s)
{
TrieNode *p;
int i,k;
if(!(p=*pRoot))
{
return0;
}
i=0;
while(s[i])
{
k=s[i++]-'a';
if(p->next[k]==NULL) return 0;
p=p->next[k];
}
return p->nCount;
}
#include <cstring>
#include <iostream>
#include <conio.h>
using namespace std;
namespace trie
{
template <class T, size_t CHILD_MAX>
/*
Parameter T: Type of reserved data.
Parameter CHILD_MAX: Size of the array of pointers to childnode.
*/
struct nod
{
T reserved;
nod<T, CHILD_MAX> *child[CHILD_MAX];
nod()
{
memset(this, 0, sizeof *this);
}
~nod()
{
for (unsigned i = 0; i < CHILD_MAX; i++)
delete child[i];
}
void Traversal(char *str, unsigned index)
{
unsigned i;
for (i = 0; i < index; i++)
cout << str[i];
cout << '\t' << reserved << endl;
for (i = 0; i < CHILD_MAX; i++)
{
if (child[i])
{
str[index] = i;
child[i]->Traversal(str, index + 1);
}
}
return;
}
};
template <class T, size_t CHILD_MAX = 127>
/*
Parameter T: Type of reserved data.
Parameter CHILD_MAX: Size of the array of pointers to childnode.
*/
class trie
{
private:
nod<T, CHILD_MAX> root;
public:
nod<T, CHILD_MAX> *AddStr(char *str);
nod<T, CHILD_MAX> *FindStr(char *str);
bool DeleteStr(char *str);
void Traversal()
{
char str[100];
root.Traversal(str, 0);
}
};
template <class T, size_t CHILD_MAX>
nod<T, CHILD_MAX> * trie<T, CHILD_MAX>::AddStr(char *str)
{
nod<T, CHILD_MAX> *now = &root;
do
{
if (now->child[*str] == NULL)
now->child[*str] = new nod<T, CHILD_MAX>;
now = now->child[*str];
}
while (*(++str) != '\0');
return now;
}
template <class T, size_t CHILD_MAX>
nod<T, CHILD_MAX> *trie<T, CHILD_MAX>::FindStr(char *str)
{
nod<T, CHILD_MAX> *now = &root;
do
{
if (now->child[*str] == NULL)
return NULL;
now = now->child[*str];
}
while (*(++str) != '\0');
return now;
}
template <class T, size_t CHILD_MAX>
bool trie<T, CHILD_MAX>::DeleteStr(char *str)
{
nod<T, CHILD_MAX> **nods = new nod<T, CHILD_MAX> *[strlen(str)];
int snods = 1;
nod<T, CHILD_MAX> *now = &root;
nods[0] = &root;
do
{
if (now->child[*str] == NULL)
return false;
nods[snods++] = now = now->child[*str];
}
while (*(++str) != '\0');
snods--;
while (snods > 0)
{
for (unsigned i = 0; i < CHILD_MAX; i++)
if (nods[snods]->child[i] != NULL)
return true;
delete nods[snods];
nods[--snods]->child[*(--str)] = NULL;
}
return true;
}
} // namespace trie
int main()
{
//TestProgram
trie::trie<int> tree;
while (1)
{
cout << "1 for add a string" << endl;
cout << "2 for find a string" << endl;
cout << "3 for delete a string" << endl;
cout << "4 for traversal" << endl;
cout << "5 for exit" << endl;
char str[100];
switch (getch())
{
case '1':
cout << "Input a string: ";
cin.getline(str, 100);
cout << "This string has existed for " << tree.AddStr(str)->reserved++ << " times." << endl;
break;
case '2':
cout << "Input a string: ";
cin.getline(str, 100);
trie::nod<int, 127> *find;
find = tree.FindStr(str);
if (!find)
cout << "No found." << endl;
else
cout << "This string has existed for " << find->reserved << " times." << endl;
break;
case '3':
cout << "Input a string: ";
cin.getline(str, 100);
cout << "The action is " << (tree.DeleteStr(str) ? "Successful." : "Unsuccessful.") << endl;
break;
case '4':
cout << "Traversal the tree: " << endl;
tree.Traversal();
break;
case '5':
cout << "Exit." << endl;
return 0;
}
}
return 0;
}
