trie樹定義
Trie樹，又稱單詞查找樹或鍵樹，是一種樹形結構，是一種哈希樹的變種。典型套用是用於統計和排序大量的字元串（但不僅限於字元串），所以經常被搜尋引擎系統用於文本詞頻統計。它的優點是：最大限度地減少無謂的字元串比較，查詢效率比哈希表高。
結構示意圖
‍
‍
trie樹結構原理示意圖基本特性
它有3個基本特性：
1）根節點不包含字元，除根節點外每一個節點都只包含一個字元。
2）從根節點到某一節點，路徑上經過的字元連線起來，為該節點對應的字元串。
3）每個節點的所有子節點包含的字元都不相同。
示例代碼
Trie樹的類定義：
const int MaxKeySize = 25; //關鍵碼最大位數
typedef struct { //關鍵碼類型
char ch[MaxKeySize]; //關鍵碼存放數組
int currentSize; //關鍵碼當前位數
} KeyType;
class TrieNode { //Trie樹結點類定義
friend class Trie;
protected:
enum { branch, element } NodeType; //結點類型
union NodeType { //根據結點類型的兩種結構
struct { //分支結點
int num; //本結點關鍵碼個數
TrieNode *link[27]; //指針數組
} brch;
struct { //元素結點
KeyType key; //關鍵碼
recordNode *recptr; //指向數據對象指針
} elem;
}
}
class Trie { //Trie樹的類定義
private:
TrieNode *root, *current;
public:
RecordNode* Search ( const keyType & );
int Insert ( const KeyType & );
int Delete ( const KeyType & );
}
Trie樹的搜尋算法：
RecordNode* Trie::Search ( const KeyType & x ) {
k = x.key;
concatenate ( k, ‘b’ );
current = root;
int i = 0; //掃描初始化
while ( current != NULL && current→NodeType != element && i <= x. ch[i] ) {
current = current→brch.link[ord (x. ch[i])];
i = i++;
};
if ( current != NULL && current→NodeType == element && current→elem.key == x )
return current→recptr;
else
return NULL;
}
