鍵樹又稱為數(shù)字查找樹（Digital Search Tree)或Trie樹(trie為retrieve中間4個(gè)字符)，其結(jié)構(gòu)受啟發(fā)于一部大型字典的“書邊標(biāo)目”。字典中標(biāo)出首字母是A,B,C,....Z的單詞所在頁(yè),再對(duì)各部分標(biāo)出第二字母為A,B,C,...Z的單詞所在的頁(yè), ....等等。
1：鍵樹的定義
鍵樹是一種特殊的查找樹，它的某個(gè)節(jié)點(diǎn)不是包含一個(gè)或多個(gè)關(guān)鍵字，而是只包含組成關(guān)鍵字的一部分（字符或數(shù)字），比如：如果關(guān)鍵字是數(shù)值，則節(jié)點(diǎn)中只包含一個(gè)數(shù)位；如果關(guān)鍵字是單詞，則節(jié)點(diǎn)中只包含一個(gè)字母字符。
2：鍵樹的存儲(chǔ)
鍵樹的存儲(chǔ)通常有兩種方式：
（1）雙鏈樹表示
如果以樹的孩子兄弟表示，則每個(gè)節(jié)點(diǎn)包含3個(gè)域。
A: symbol域: 存儲(chǔ)關(guān)鍵字的一個(gè)字符
B: son域: 存儲(chǔ)指向第一棵子樹的根的指針,葉子節(jié)點(diǎn)的son域指向該關(guān)鍵字記錄的指針
C: brother域: 存儲(chǔ)指向右兄弟的指針.
這時(shí)的鍵樹又稱為雙鏈樹.
//雙鏈樹的存儲(chǔ)表示
typedef struct DULNode{
char symbol; //結(jié)點(diǎn)字符域
struct DULNode *son, *brother; //son指向子樹根結(jié)點(diǎn),brother指向右兄弟結(jié)點(diǎn).
}DULNode ,*DLTree;
(2) 多重鏈表表示
如果以樹的多重鏈表表示鍵樹, 則樹的每個(gè)結(jié)點(diǎn)中應(yīng)包含d個(gè)(d為關(guān)鍵字符的基,如:字符集由英文大寫字母構(gòu)成時(shí),則d=26+1=27)指針域，此時(shí)的鍵樹又稱為Trie樹。如果從鍵樹中某個(gè)結(jié)點(diǎn)到葉子結(jié)點(diǎn)的路徑上每個(gè)結(jié)點(diǎn)都只有一個(gè)孩子，則可以將該路徑上的所有結(jié)點(diǎn)壓縮為一個(gè)“葉子結(jié)點(diǎn)”，且在該葉子結(jié)點(diǎn)中存儲(chǔ)關(guān)鍵字及指向記錄的指針等信息。
以上數(shù)據(jù)結(jié)構(gòu)很容易讓人聯(lián)想到電話號(hào)碼，如果關(guān)鍵字的取值為[0，9]，則很容易用來(lái)處理像電話號(hào)碼這類的數(shù)據(jù)。如果目前固定電話的長(zhǎng)度算8位的話，那查找的的時(shí)間復(fù)雜度為常數(shù)8。
計(jì)費(fèi)系統(tǒng)中的用戶資料在計(jì)費(fèi)過(guò)程中使用非常頻繁，如果id作為關(guān)鍵字的鍵樹算法的話，將大大的提高查詢速度。
下面是它的實(shí)現(xiàn)代碼
鍵樹的實(shí)現(xiàn)代碼