Trie,又稱字典樹、單詞查找樹,是一種樹形結(jié)構(gòu)，用于保存大量的字符串。它的優(yōu)點(diǎn)是：利用字符串的公共前綴來節(jié)約存儲(chǔ)空間。
相對(duì)來說,Trie樹是一種比較簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu).理解起來比較簡(jiǎn)單,正所謂簡(jiǎn)單的東西也得付出代價(jià).故Trie樹也有它的缺點(diǎn),Trie樹的內(nèi)存消耗非常大.當(dāng)然,或許用左兒子右兄弟的方法建樹的話,可能會(huì)好點(diǎn).
其基本性質(zhì)可以歸納為：
1. 根節(jié)點(diǎn)不包含字符，除根節(jié)點(diǎn)外每一個(gè)節(jié)點(diǎn)都只包含一個(gè)字符。
2. 從根節(jié)點(diǎn)到某一節(jié)點(diǎn)，路徑上經(jīng)過的字符連接起來，為該節(jié)點(diǎn)對(duì)應(yīng)的字符串。
3. 每個(gè)節(jié)點(diǎn)的所有子節(jié)點(diǎn)包含的字符都不相同。
其基本操作有:查找 插入和刪除,當(dāng)然刪除操作比較少見.我在這里只是實(shí)現(xiàn)了對(duì)整個(gè)樹的刪除操作,至于單個(gè)word的刪除操作也很簡(jiǎn)單.
搜索字典項(xiàng)目的方法為：
(1) 從根結(jié)點(diǎn)開始一次搜索；
(2) 取得要查找關(guān)鍵詞的第一個(gè)字母，并根據(jù)該字母選擇對(duì)應(yīng)的子樹并轉(zhuǎn)到該子樹繼續(xù)進(jìn)行檢索；
(3) 在相應(yīng)的子樹上，取得要查找關(guān)鍵詞的第二個(gè)字母,并進(jìn)一步選擇對(duì)應(yīng)的子樹進(jìn)行檢索。
(4) 迭代過程……
(5) 在某個(gè)結(jié)點(diǎn)處，關(guān)鍵詞的所有字母已被取出，則讀取附在該結(jié)點(diǎn)上的信息，即完成查找。
其他操作類似處理.
/**//*
Name: Trie樹的基本實(shí)現(xiàn)
Author: MaiK
Description: Trie樹的基本實(shí)現(xiàn) ,包括查找 插入和刪除操作*/
#include<algorithm>
#include<iostream>
using namespace std;
const int sonnum=26,base='a';
struct Trie
{
int num;//to remember how many word can reach here,that is to say,prefix
bool terminal;//If terminal==true ,the current point has no following point
struct Trie *son[sonnum];//the following point
};
Trie *NewTrie()// create a new node
{
Trie *temp=new Trie;
temp->num=1;temp->terminal=false;
for(int i=0;i<sonnum;++i)temp->son[i]=NULL;
return temp;
}
void Insert(Trie *pnt,char *s,int len)// insert a new word to Trie tree
{
Trie *temp=pnt;
for(int i=0;i<len;++i)
{
if(temp->son[s[i]-base]==NULL)temp->son[s[i]-base]=NewTrie();
else temp->son[s[i]-base]->num++;
temp=temp->son[s[i]-base];
}
temp->terminal=true;
}
void Delete(Trie *pnt)// delete the whole tree
{
if(pnt!=NULL)
{
for(int i=0;i<sonnum;++i)if(pnt->son[i]!=NULL)Delete(pnt->son[i]);
delete pnt;
pnt=NULL;
}
}
Trie* Find(Trie *pnt,char *s,int len)//trie to find the current word
{
Trie *temp=pnt;
for(int i=0;i<len;++i)
if(temp->son[s[i]-base]!=NULL)temp=temp->son[s[i]-base];
else return NULL;
return temp;
}
轉(zhuǎn)自：http://hi.baidu.com/luyade1987/blog/item/2667811631106657f2de320a.html