原理 先看個例子，存儲字符串abc、ab、abm、abcde、pm可以利用以下方式存儲 上邊就是Trie樹的基本原理：利用字串的公共前綴來節省存儲空間，最大限度的減少無謂的字串比較。 應用 Trie樹又稱單詞查找樹，典型的應用是用於統計，排序和保存大量的字符串（不僅用於字符串），所以經常被搜索引擎系統用於文本詞頻的統計。 設計 trie，又稱前綴樹或字典樹，是一種有序樹，用於保存關聯數組，其中的鍵通常是字符串。與二叉查找樹不同，鍵不是直接保存在節點中，而是由節點在樹中的位置決定。一個節點的所有子孫都有相同的前綴，也就是這個節點對應的字符串，而根節點對應空字符串。一般情況下，不是所有的節點都有對應的值，只有葉子節點和部分內部節點所對應的鍵才有相關的值。 結點可以設計成這樣： class trieNode { public: trieNode() : terminableSize(0), nodeSize(0) { for(int i = 0; i < Size; ++i) children[i] = NULL; } ~trieNode() { for(int i = 0; i < Size; ++i) { delete children[i]; children[i] = NULL; } } public: int terminableSize; //存儲以此結點為結尾的字串的個數 int nodeSize; //記錄此結點孩子的個數 trieNode* children[Size]; //該數組記錄指向孩子的指針 }; 樹設計成這樣： template<int Size, class Type> class trie { public: typedef trieNode<Size> Node; typedef trieNode<Size>* pNode; trie() : root(new Node) {} template<class Iterator> void insert(Iterator beg, Iterator end); void insert(const char *str); template<class Iterator> bool find(Iterator beg, Iterator end); bool find(const char *str); template<class Iterator> bool downNodeAlone(Iterator beg); template<class Iterator> bool erase(Iterator beg, Iterator end); bool erase(const char *str); int sizeAll(pNode); int sizeNoneRedundant(pNode); public: pNode root; private: Type index; }; index字串索引利用（char % 26） 得到，這樣'a' % 26 = 19, 'b' % 26 = 20 實現 插入 以插入abc、ab為例 ] 刪除 刪除結點，首先查找此字串是否在樹中，如果在樹中，再查找此結點以下的部分是不是都是只有一個孩子，並且每個結點只有葉子結點是結束結點，如果不是繼續往下重復上邊過程。 統計字串個數 分兩種情況 計算重復的字串的個數：是結束結點，此時加的是terminabel的個數 計算不重復的字串的個數：是結束結點，此時加的是1(當terminabel>0）的個數 #include <iostream> #include <cstring> using namespace std; template<int Size> class trieNode { public: trieNode() : terminableSize(0), nodeSize(0) { for(int i = 0; i < Size; ++i) children[i] = NULL; } ~trieNode() { for(int i = 0; i < Size; ++i) { delete children[i]; children[i] = NULL; } } public: int terminableSize; int nodeSize; trieNode* children[Size]; }; template<int Size, class Type> class trie { public: typedef trieNode<Size> Node; typedef trieNode<Size>* pNode; trie() : root(new Node) {} template<class Iterator> void insert(Iterator beg, Iterator end); void insert(const char *str); template<class Iterator> bool find(Iterator beg, Iterator end); bool find(const char *str); template<class Iterator> bool downNodeAlone(Iterator beg); template<class Iterator> bool erase(Iterator beg, Iterator end); bool erase(const char *str); int sizeAll(pNode); int sizeNoneRedundant(pNode); public: pNode root; private: Type index; }; template<int Size, class Type> template<class Iterator> void trie<Size, Type>::insert(Iterator beg, Iterator end) { pNode cur = root; pNode pre; for(; beg != end; ++beg) { if(!cur->children[index[*beg]]) { cur->children[index[*beg]] = new(Node); ++cur->nodeSize; } pre = cur; cur = cur->children[index[*beg]]; } ++pre->terminableSize; } template<int Size, class Type> void trie<Size, Type>::insert(const char *str) { return insert(str, str + strlen(str)); } template<int Size, class Type> template<class Iterator> bool trie<Size, Type>::find(Iterator beg, Iterator end) { pNode cur = root; pNode pre; for(; beg != end; ++beg) { if(!cur->children[index[*beg]]) { return false; break; } pre = cur; cur = cur->children[index[*beg]]; } if(pre->terminableSize > 0) return true; return false; } template<int Size, class Type> bool trie<Size, Type>::find(const char *str) { return find(str, str + strlen(str)); } template<int Size, class Type> template<class Iterator> bool trie<Size, Type>::downNodeAlone(Iterator beg) { pNode cur = root; int terminableSum = 0; while(cur->nodeSize != 0) { terminableSum += cur->terminableSize; if(cur->nodeSize > 1) return false; else //cur->nodeSize = 1 { for(int i = 0; i < Size; ++i) { if(cur->children[i]) cur = cur->children[i]; } } } if(terminableSum == 1) return true; return false; } template<int Size, class Type> template<class Iterator> bool trie<Size, Type>::erase(Iterator beg, Iterator end) { if(find(beg, end)) { pNode cur = root; pNode pre; for(; beg != end; ++beg) { if(downNodeAlone(cur)) { delete cur; return true; } pre = cur; cur = cur->children[index[*beg]]; } if(pre->terminableSize > 0) --pre->terminableSize; return true; } return false; } template<int Size, class Type> bool trie<Size, Type>::erase(const char *str) { if(find(str)) { erase(str, str + strlen(str)); return true; } return false; } template<int Size, class Type> int trie<Size, Type>::sizeAll(pNode ptr) { if(ptr == NULL) return 0; int rev = ptr->terminableSize; for(int i = 0; i < Size; ++i) rev += sizeAll(ptr->children[i]); return rev; } template<int Size, class Type> int trie<Size, Type>::sizeNoneRedundant(pNode ptr) { if(ptr == NULL) return 0; int rev = 0; if(ptr->terminableSize > 0) rev = 1; if(ptr->nodeSize != 0) { for(int i = 0; i < Size; ++i) rev += sizeNoneRedundant(ptr->children[i]); } return rev; } template<int Size> class Index { public: int operator[](char vchar) { return vchar % Size; } }; int main() { trie<26, Index<26> > t; t.insert("hello"); t.insert("hello"); t.insert("h"); t.insert("h"); t.insert("he"); t.insert("hel"); cout << "SizeALL:" << t.sizeAll(t.root) << endl; cout << "SizeALL:" << t.sizeNoneRedundant(t.root) << endl; t.erase("h"); cout << "SizeALL:" << t.sizeAll(t.root) << endl; cout << "SizeALL:" << t.sizeNoneRedundant(t.root) << endl; }
