數(shù)據(jù)結(jié)構(gòu)在各大開發(fā)語言中應(yīng)用廣泛吓笙，尤其是后端開發(fā)對數(shù)據(jù)的處理映屋，而大部分前端開發(fā)很少應(yīng)用到，或是應(yīng)用場景不允許等因素袱讹，但是了解數(shù)據(jù)結(jié)構(gòu)卻對程序開發(fā)都是有很大裨益的疲扎，那么接下來介紹Trie樹的前端實現(xiàn)。
Trie的簡介
Trie樹捷雕，簡稱“字典樹或前綴樹”，可以存儲字符串與值的對應(yīng)關(guān)系救巷，它與 Java 的 HashMap 功能相同，以 key-value 形式存儲浦译，Trie樹的key是單個字符棒假。
Trie的數(shù)據(jù)結(jié)構(gòu)特點
- 根節(jié)點不包含字符精盅，除根節(jié)點意外每個節(jié)點只包含一個字符。
- 從根節(jié)點到某一個節(jié)點渤弛，路徑上經(jīng)過的字符連接起來，為該節(jié)點對應(yīng)的字符串。
- 每個節(jié)點的所有子節(jié)點包含的字符串不相同鹰贵。
- 如果字符的種數(shù)為n，則每個結(jié)點的出度為n碉输，這也是空間換時間的體現(xiàn)，浪費了很多的空間亭珍。
- 插入查找的復(fù)雜度為O(n)敷钾，n為字符串長度
如圖，跟節(jié)點是root肄梨，沒有存儲任何字符阻荒，它的key為空，包含了一個數(shù)組存放子節(jié)點众羡。
Trie樹的數(shù)據(jù)結(jié)構(gòu)
Trie樹的操作
- 插入節(jié)點
向樹中存儲一個單詞侨赡，比如high，首先從root開始粱侣，遍歷子節(jié)點從high的第一個字符h開始比較羊壹，如果找到了對應(yīng)的子節(jié)點，則遞歸遍歷子節(jié)點的children繼續(xù)查找齐婴，并與單詞的下一個字符（i）比較油猫，直到最后一個字符h為止，如果能找到最后一個字符則說明已存在單詞前綴柠偶；如果過程中未找到則取出字符進行插入到當(dāng)前節(jié)點中情妖，直到單詞的最后一個字符。 - 查找節(jié)點
查找節(jié)點的過程嚣州，其實跟插入節(jié)點類似鲫售，也是遍歷+遞歸判斷樹節(jié)點查找單詞是否存在共螺，其滿足條件：單詞的最后一個字符所在節(jié)點是葉子節(jié)點该肴。 - 刪除節(jié)點
刪除一個單詞，一般在應(yīng)用中很少操作藐不，但也只需要刪除節(jié)點即可匀哄，先查找到節(jié)點判斷是否存在，如果存在雏蛮，則從單詞倒序遞歸判斷字符是否是葉子節(jié)點涎嚼，如果是則刪除，直到不是葉子節(jié)點結(jié)束挑秉。
原生JS代碼實現(xiàn)
一法梯、定義數(shù)據(jù)結(jié)構(gòu)
Trie有一個根節(jié)點root，它的key為null。
/**
* Trie
*/
function Trie() {
this.root = new TrieNode(null);
}
TrieNode有兩個屬性立哑，其中key代表一個字符夜惭，children數(shù)組表示子節(jié)點。
/**
* 節(jié)點
* @param {*} key
*/
function TrieNode(key) {
this.key = key; // 節(jié)點字符
this.children = []; // 子節(jié)點集合
}
二铛绰、實現(xiàn)Trie的插入诈茧、查找敢会、刪除鸥昏、輸出
為了更好的描述具體實現(xiàn)細節(jié)，以下先聲明列出我要擴展的方法類型互广。接下來將一步一步去講解和實現(xiàn)每個方法及細節(jié)惫皱。
Trie.prototype = {
// 插入單詞
insertData:(stringData)=>void,
insert:(stringData,node)=>void,
// 查找單詞
search:(queryData)=>boolean,
searchNext:(node,stringData)=>boolean, // 遞歸
// 刪除單詞
delete:(stringData)=>this,
delNext:(parent, index, stringData, delStr)=>boolean, // 遞歸
// 打印樹上的所有單詞
printData:()=>void,
printHelper:(node, data)=>void // 遞歸
}
插入單詞
1旅敷、從根節(jié)點開始遍歷樹節(jié)點颤霎，將節(jié)點的key的值與字符串第一個字符比較友酱；
2、如果找到了字符锤躁，則截取剩余子字符串和當(dāng)前節(jié)點繼續(xù)遞歸或详；
3、如果沒有找到字符椒振，則判斷當(dāng)前節(jié)點是否存在子節(jié)點澎迎，若不存在則直接插入，如果存在子節(jié)點辑莫，則遍歷子節(jié)點取出字符與當(dāng)前字符判斷排序位置罩引，最后在該位置插入節(jié)點袁铐；
4、直到字符串最后一個字符屉更，即可完成整個單詞的插入洒缀。
insertData: function (stringData) {
this.insert(stringData, this.root);
},
// 遞歸判斷插入
insert: function (stringData, node) {
if (stringData == '') {
return;
}
let children = node.children;
let haveData = null;
for (let i in children) {
if (children[i].key == stringData[0]) {
haveData = children[i];
}
}
if (haveData) {
this.insert(stringData.substring(1), haveData); //說明找到了對應(yīng)的節(jié)點
} else { //那如果沒有找到則插入
if (children.length == 0) { //當(dāng)前節(jié)點沒有子節(jié)點
let node = new TrieNode(stringData[0]);
children.push(node);
this.insert(stringData.substring(1), node); //將該字符節(jié)點插入節(jié)點的children中
} else { //當(dāng)前節(jié)點存在子節(jié)點，需要查找一個合適的位置去插入新節(jié)點
let validPosition = 0;
for (let j in children) {
if (children[j].key < stringData[0]) {
validPosition++;
}
}
let node = new TrieNode(stringData[0]);
children.splice(validPosition, 0, node);
this.insert(stringData.substring(1), node); //將該字符節(jié)點插入節(jié)點的children中
}
}
},
查找單詞萨脑，判斷是否存在
遍歷遞歸邏輯類似渤早，請查看代碼具體注釋鹊杖，需要注意的是調(diào)用遞歸函數(shù)時別忘了return 函數(shù)返回值扛芽。
// 查詢字符串
search: function (queryData) {
if (queryData == '' || this.root.children.length == 0) {
return false;
}
for (let i in this.root.children) {
if (this.searchNext(this.root.children[i], queryData)) {
return true;
}
}
return false;
},
// 遞歸查詢判斷
searchNext: function (node, stringData) {
// 若字符與節(jié)點key不相等，則不匹配
if (stringData[0] != node.key) {
return false;
} else { // 若與key相等登下，繼續(xù)判斷
let children = node.children;
if (children.length == 0 && stringData.length == 1) { // 葉子節(jié)點庐船，最后一個字符，則完全匹配
return true;
} else if (children.length > 0 && stringData.length > 1) { // 既不是葉子節(jié)點揩瞪，也不是最后一個字符，則繼續(xù)遞歸查找
for (let i in children) {
if (children[i].key == stringData[1]) {
return this.searchNext(children[i], stringData.substring(1)); // 記得return 遞歸函數(shù)壹将，否則獲取的返回值為undefined
}
}
} else { // C1：葉子節(jié)點毛嫉，C2：最后一個字符承粤；若只滿足其中一個條件，則不匹配
return false;
}
}
},
刪除單詞
遍歷遞歸邏輯類似辛臊，先判斷單詞是否存在彻舰，不存在則不做處理。與查找隔心、插入不同尚胞，刪除需先找到單詞辐真，然后從單詞字符串反向判斷節(jié)點是否是葉子節(jié)點（如high，那么從h耐床、g撩轰、i昧廷、h倒序遍歷判斷）木柬，如果是則刪除，直到單詞某個字符所處的節(jié)點是葉子節(jié)點為止恶复。
// 刪除字符串
delete: function (stringData) {
if (this.search(stringData)) { // 判斷是否存在該單詞（字符串）
for (let i in this.root.children) {
if (this.delNext(this.root, i, stringData, stringData)) {
return;
}
}
}
return this;
},
/**
* 先遞歸查找到字符串的葉子節(jié)點，然后從字符串的葉子節(jié)點逐級向根節(jié)點遞歸刪除葉子節(jié)點副硅，直到刪除字符串
* @param parent 父節(jié)點
* @param index 子節(jié)點在父節(jié)點children數(shù)組中的索引位置
* @param stringData 遞歸遍歷中的字符串
* @param delStr 調(diào)用delete方法時的原始字符串
*/
delNext: function (parent, index, stringData, delStr) {
//當(dāng)前節(jié)點對象
let node = parent.children[index];
// 若字符與節(jié)點key不相等恐疲，則不匹配
if (stringData[0] != node.key) {
return false;
} else { // 若與key相等套么，繼續(xù)判斷
let children = node.children;
if (children.length == 0 && stringData.length == 1) { // 葉子節(jié)點违诗，最后一個字符诸迟，則完全匹配
// 刪除葉子節(jié)點，利用父節(jié)點刪除子節(jié)點原理
parent.children.splice(index, 1);
// 字符串從尾部移除一個字符后壁公，繼續(xù)遍歷刪除方法
this.delete(delStr.substring(0, delStr.length - 1));
} else if (children.length > 0 && stringData.length > 1) { // 既不是葉子節(jié)點紊册，也不是最后一個字符快耿，則繼續(xù)遞歸查找
for (let i in children) {
if (children[i].key == stringData[1]) {
return this.delNext(node, i, stringData.substring(1), delStr); // 記得return 遞歸函數(shù)，否則獲取的返回值為undefined
}
}
}
}
},
輸出所有的單詞
從根節(jié)點開始遍歷掀亥，console.log輸出所有單詞搪花。遞歸單個節(jié)點直到葉子節(jié)點撮竿，輸出單詞，注意data.pop()髓需，遞歸完畢找到葉子節(jié)點后惑折，此操作目的返回原始遍歷節(jié)點繼續(xù)遍歷直到找到下一個單詞為止惨驶。
// 打印字符串
printData: function () {
for (let i in this.root.children) {
this.printHelper(this.root.children[i], [this.root.children[i].key]);
}
},
// 遞歸輸出字符串
printHelper: function (node, data) {
if (node.children.length == 0) {
console.log('>', data.join(''));
return;
}
for (let i in node.children) {
data.push(node.children[i].key);
this.printHelper(node.children[i], data);
data.pop(); // 注意，找打一個單詞后屋确，返回下一個初始節(jié)點繼續(xù)遍歷
}
}
三攻臀、調(diào)試運行
命令行執(zhí)行：node Trie.js刨啸，查看console輸出結(jié)果：
/**
* 測試
*/
let trie = new Trie();
trie.insertData('我愛你');
trie.insertData('我愛你中國');
trie.insertData('我愛你寶貝');
trie.insertData('我愛你中原');
trie.insertData('愛你一萬年');
trie.insertData('永遠愛你');
trie.insertData('愛你真的好難');
trie.printData();
// console：
// > 我愛你中原
// > 我愛你中國
// > 我愛你寶貝
// > 永遠愛你
// > 愛你一萬年
// > 愛你真的好難
// console.log(trie.search('我愛你')); // false
// console.log(trie.search('我愛你中國')); // true
// console.log(trie.search('我愛你寶寶')); // false
// console.log(trie.search('我愛你寶貝')); // true
console.log(JSON.stringify(trie.delete('愛你真的好難')));
// 查看輸出發(fā)現(xiàn)识脆，單詞已刪除
上面是原生JS實現(xiàn)灼捂，下面用TypeScript重寫
TypeScript 這門語言越來越流行了悉稠，像主流框架React的猛、Vue、Angular叛拷，都有很好的支持猫牡。重寫主要體現(xiàn)TS的面向?qū)ο筇匦裕谶@里主要用到了TS的接口及實現(xiàn)煌恢、類的繼承瑰抵、模塊器联、類型斷言等婿崭，話不多說了氓栈，直接上代碼：
Trie.ts文件
/**
* 接口類
*/
interface ITrie {
/**
* 插入單詞
* @param data
*/
insertData(data: string): void;
/**
* 刪除單詞
* @param data
*/
deleteData(data: string): Trie;
/**
* 查找單詞
* @param data
*/
searchData(data: string): boolean;
/**
* 輸出單詞列表
*/
printData(): void;
}
/**
* 基類
*/
class TrieBase {
/**
* 本類不能實例化對象授瘦，能被繼承
*/
protected constructor() { }
/**
* 占個位提完，去派生類中重寫
* @param stringData
*/
protected deleteData(stringData) {
return
}
/**
* 遞歸插入單詞
* @param stringData
* @param node
*/
protected insert(stringData, node) {
if (stringData == '') {
return;
}
let children = node.children;
let haveData = null;
for (let i in children) {
if (children[i].key == stringData[0]) {
haveData = children[i];
}
}
if (haveData) {
this.insert(stringData.substring(1), haveData); //說明找到了對應(yīng)的元素
} else { //那如果沒有找到
if (children.length == 0) {
//當(dāng)前沒有子元素，所以應(yīng)該判斷一下
let node = new TrieNode(stringData[0]);
children.push(node);
this.insert(stringData.substring(1), node); //對吧扳躬，此時應(yīng)該將該元素插入子元素中
} else { //當(dāng)前子元素的長度不為零，需要查找一個合適的位置去插入元素
let validPosition = 0;
for (let j in children) {
if (children[j].key < stringData[0]) {
validPosition++;
}
}
let node = new TrieNode(stringData[0]);
children.splice(validPosition, 0, node);
this.insert(stringData.substring(1), node); //對吧，此時應(yīng)該將該元素插入子元素中
}
}
}
/**
* 先遞歸查找到字符串的葉子節(jié)點担神，然后從字符串的葉子節(jié)點逐級向根節(jié)點遞歸刪除葉子節(jié)點妄讯，直到刪除字符串
* @param parent 父節(jié)點
* @param index 子節(jié)點在父節(jié)點children數(shù)組中的索引位置
* @param stringData 遞歸遍歷中的字符串
* @param delStr 調(diào)用deleteData方法時的原始字符串
*/
protected delNext(parent, index, stringData, delStr) {
//當(dāng)前節(jié)點對象
let node = parent.children[index];
// 若字符與節(jié)點key不相等亥贸，則不匹配
if (stringData[0] != node.key) {
return false;
} else { // 若與key相等炕置，繼續(xù)判斷
let children = node.children;
if (children.length == 0 && stringData.length == 1) { // 葉子節(jié)點，最后一個字符默垄，則完全匹配
// 刪除葉子節(jié)點口锭，利用父節(jié)點刪除子節(jié)點原理
parent.children.splice(index, 1);
// 字符串從尾部移除一個字符后鹃操，繼續(xù)遍歷刪除方法
this.deleteData(delStr.substring(0, delStr.length - 1));
} else if (children.length > 0 && stringData.length > 1) { // 既不是葉子節(jié)點，也不是最后一個字符恩伺，則繼續(xù)遞歸查找
for (let i in children) {
if (children[i].key == stringData[1]) {
return this.delNext(node, i, stringData.substring(1), delStr); // 記得return 遞歸函數(shù)莫其，否則獲取的返回值為undefined
}
}
}
}
}
/**
* 遞歸查找單詞
* @param node
* @param stringData
*/
protected searchNext(node, stringData) {
// 若字符與節(jié)點key不相等耸三，則不匹配
if (stringData[0] != node.key) {
return false;
} else { // 若與key相等仪壮，繼續(xù)判斷
let children = node.children;
if (children.length == 0 && stringData.length == 1) { // 葉子節(jié)點胳徽，最后一個字符养盗，則完全匹配
return true;
} else if (children.length > 0 && stringData.length > 1) { // 既不是葉子節(jié)點，也不是最后一個字符箫爷，則繼續(xù)遞歸查找
for (let i in children) {
if (children[i].key == stringData[1]) {
return this.searchNext(children[i], stringData.substring(1)); // 記得return 遞歸函數(shù)虎锚，否則獲取的返回值為undefined
}
}
} else { // C1：葉子節(jié)點窜护，C2：最后一個字符柱徙；若只滿足其中一個條件护侮，則不匹配
return false;
}
}
}
/**
* 遞歸打印單詞
* @param node
* @param data
*/
protected printHelper(node, data) {
if (node.children.length == 0) {
console.log('>', data.join(''));
return;
}
for (let i in node.children) {
data.push(node.children[i].key);
this.printHelper(node.children[i], data);
data.pop();
}
}
/**
* 類型保護概行，以免typescript報錯凳忙，或使用類型斷言
* @param node
*/
protected isTrieNode(node: TrieNode): node is TrieNode {
return (<TrieNode>node).key !== undefined;
}
}
/**
* 節(jié)點
* @param {*} key
*/
class TrieNode {
key: string;
children: [];
constructor(key) {
this.key = key; // 節(jié)點字符
this.children = []; // 子節(jié)點集合
}
}
/**
* Trie類
*/
class Trie extends TrieBase implements ITrie {
root: TrieNode;
constructor() {
super();
this.root = new TrieNode(null);
}
//插入單詞（字符串）
insertData(stringData): void {
this.insert(stringData, this.root);
}
//刪除單詞
deleteData(stringData): Trie {
if (this.searchData(stringData)) { // 判斷是否存在該單詞（字符串）
for (let i in this.root.children) {
if (this.delNext(this.root, i, stringData, stringData)) {
return;
}
}
}
return this;
}
//查找單詞（字符串）
searchData(queryData): boolean {
if (queryData == '' || this.root.children.length == 0) {
return false;
}
for (let i in this.root.children) {
if (this.searchNext(this.root.children[i], queryData)) {
return true;
}
}
return false;
}
//輸出所有單詞（字符串）
printData(): void {
for (let i in this.root.children) {
//為了讓代碼工作勤家，第二個參數(shù)，我使用了類型斷言柳恐，避免TS編譯報錯伐脖，找不到key屬性，也可以使用類型保護函數(shù)（從TrieBase類繼承過來的isTrieNode函數(shù)判斷）
this.printHelper(this.root.children[i], [(<TrieNode>this.root.children[i]).key]);
}
}
}
// 導(dǎo)出Trie模塊
export { Trie }
在其他模塊中使用Trie模塊
// 導(dǎo)入模塊
import {Trie} from 'Trie';
/**
* 使用
*/
let trieObj = new Trie();
trieObj.insertData('我愛你');
trieObj.insertData('我愛你中國');
trieObj.insertData('我愛你寶貝');
trieObj.insertData('我愛你中原');
trieObj.insertData('愛你一萬年');
trieObj.insertData('永遠愛你');
trieObj.insertData('愛你真的好難');
trieObj.printData();
// console：
// > 我愛你中原
// > 我愛你中國
// > 我愛你寶貝
// > 永遠愛你
// > 愛你一萬年
// > 愛你真的好難
console.log(trieObj.searchData('我愛你')); // false
console.log(trieObj.searchData('我愛你中國')); // true
console.log(trieObj.searchData('我愛你寶寶')); // false
console.log(trieObj.searchData('我愛你寶貝')); // true
console.log(JSON.stringify(trieObj.deleteData('愛你真的好難')));
運行TS
// 安裝
npm install -g typescript
// 編譯生成Trie.js
tsc Trie.ts
// 運行
node Trie.js
好了乐设，講完了讼庇，有點啰嗦莫怪，就寫這么多吧近尚，希望對你有所幫助蠕啄，如不正確的地方也請指正，有問題也可留言或私信郵件戈锻，歡迎交流歼跟。
