Trie,又稱字典樹、單詞查找樹,是一種樹形結構，用于保存大量的字符串。它的優(yōu)點是：利用字符串的公共前綴來節(jié)約存儲空間。
相對來說,Trie樹是一種比較簡單的數據結構.理解起來比較簡單,正所謂簡單的東西也得付出代價.故Trie樹也有它的缺點,Trie樹的內存消耗非常大.當然,或許用左兒子右兄弟的方法建樹的話,可能會好點.
其基本性質可以歸納為：
1. 根節(jié)點不包含字符，除根節(jié)點外每一個節(jié)點都只包含一個字符。
2. 從根節(jié)點到某一節(jié)點，路徑上經過的字符連接起來，為該節(jié)點對應的字符串。
3. 每個節(jié)點的所有子節(jié)點包含的字符都不相同。
其基本操作有:查找 插入和刪除,當然刪除操作比較少見.我在這里只是實現(xiàn)了對整個樹的刪除操作,至于單個word的刪除操作也很簡單.
搜索字典項目的方法為：
(1) 從根結點開始一次搜索；
(2) 取得要查找關鍵詞的第一個字母，并根據該字母選擇對應的子樹并轉到該子樹繼續(xù)進行檢索；
(3) 在相應的子樹上，取得要查找關鍵詞的第二個字母,并進一步選擇對應的子樹進行檢索。
(4) 迭代過程……
(5) 在某個結點處，關鍵詞的所有字母已被取出，則讀取附在該結點上的信息，即完成查找。
其他操作類似處理.
1
/**//*
2
Name: Trie樹的基本實現(xiàn)
3Author: MaiK
4
Description: Trie樹的基本實現(xiàn) ,包括查找 插入和刪除操作*/
5
#include<algorithm>
6#include<iostream>
7using namespace std;
8
9const int sonnum=26,base='a';
10struct Trie
11
{
12 int num;//to remember how many word can reach here,that is to say,prefix
13 bool terminal;//If terminal==true ,the current point has no following point
14 struct Trie *son[sonnum];//the following point
15};
16Trie *NewTrie()// create a new node
17{
18 Trie *temp=new Trie;
19 temp->num=1;temp->terminal=false;
20 for(int i=0;i<sonnum;++i)temp->son[i]=NULL;
21 return temp;
22}
23void Insert(Trie *pnt,char *s,int len)// insert a new word to Trie tree
24{
25 Trie *temp=pnt;
26 for(int i=0;i<len;++i)
27
{
28 if(temp->son[s[i]-base]==NULL)temp->son[s[i]-base]=NewTrie();
29 else temp->son[s[i]-base]->num++;
30 temp=temp->son[s[i]-base];
31
}
32 temp->terminal=true;
33}
34void Delete(Trie *pnt)// delete the whole tree
35{
36 if(pnt!=NULL)
37 {
38 for(int i=0;i<sonnum;++i)if(pnt->son[i]!=NULL)Delete(pnt->son[i]);
39 delete pnt;
40 pnt=NULL;
41 }
42}
43Trie* Find(Trie *pnt,char *s,int len)//trie to find the current word
44{
45 Trie *temp=pnt;
46 for(int i=0;i<len;++i)
47 if(temp->son[s[i]-base]!=NULL)temp=temp->son[s[i]-base];
48 else return NULL;
49 return temp;
50}