数据结构在各大开发语言中应用广泛，尤其是后端开发对数据的处理，而大部分前端开发很少应用到，或是应用场景不允许等因素，但是了解数据结构却对程序开发都是有很大裨益的，那么接下来介绍Trie树的前端实现。
Trie的简介
Trie树，简称“字典树或前缀树”，可以存储字符串与值的对应关系，它与 Java 的 HashMap 功能相同，以 key-value 形式存储，Trie树的key是单个字符。
Trie的数据结构特点
- 根节点不包含字符，除根节点意外每个节点只包含一个字符。
- 从根节点到某一个节点，路径上经过的字符连接起来，为该节点对应的字符串。
- 每个节点的所有子节点包含的字符串不相同。
- 如果字符的种数为n，则每个结点的出度为n，这也是空间换时间的体现，浪费了很多的空间。
- 插入查找的复杂度为O(n)，n为字符串长度
如图，跟节点是root，没有存储任何字符，它的key为空，包含了一个数组存放子节点。
Trie树的数据结构
Trie树的操作
- 插入节点
向树中存储一个单词，比如high，首先从root开始，遍历子节点从high的第一个字符h开始比较，如果找到了对应的子节点，则递归遍历子节点的children继续查找，并与单词的下一个字符（i）比较，直到最后一个字符h为止，如果能找到最后一个字符则说明已存在单词前缀；如果过程中未找到则取出字符进行插入到当前节点中，直到单词的最后一个字符。 - 查找节点
查找节点的过程，其实跟插入节点类似，也是遍历+递归判断树节点查找单词是否存在，其满足条件：单词的最后一个字符所在节点是叶子节点。 - 删除节点
删除一个单词，一般在应用中很少操作，但也只需要删除节点即可，先查找到节点判断是否存在，如果存在，则从单词倒序递归判断字符是否是叶子节点，如果是则删除，直到不是叶子节点结束。
原生JS代码实现
一、定义数据结构
Trie有一个根节点root，它的key为null。
/**
* Trie
*/
function Trie() {
this.root = new TrieNode(null);
}
TrieNode有两个属性，其中key代表一个字符，children数组表示子节点。
/**
* 节点
* @param {*} key
*/
function TrieNode(key) {
this.key = key; // 节点字符
this.children = []; // 子节点集合
}
二、实现Trie的插入、查找、删除、输出
为了更好的描述具体实现细节，以下先声明列出我要扩展的方法类型。接下来将一步一步去讲解和实现每个方法及细节。
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、从根节点开始遍历树节点，将节点的key的值与字符串第一个字符比较；
2、如果找到了字符，则截取剩余子字符串和当前节点继续递归；
3、如果没有找到字符，则判断当前节点是否存在子节点，若不存在则直接插入，如果存在子节点，则遍历子节点取出字符与当前字符判断排序位置，最后在该位置插入节点；
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); //说明找到了对应的节点
} else { //那如果没有找到则插入
if (children.length == 0) { //当前节点没有子节点
let node = new TrieNode(stringData[0]);
children.push(node);
this.insert(stringData.substring(1), node); //将该字符节点插入节点的children中
} else { //当前节点存在子节点，需要查找一个合适的位置去插入新节点
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); //将该字符节点插入节点的children中
}
}
},
查找单词，判断是否存在
遍历递归逻辑类似，请查看代码具体注释，需要注意的是调用递归函数时别忘了return 函数返回值。
// 查询字符串
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) {
// 若字符与节点key不相等，则不匹配
if (stringData[0] != node.key) {
return false;
} else { // 若与key相等，继续判断
let children = node.children;
if (children.length == 0 && stringData.length == 1) { // 叶子节点，最后一个字符，则完全匹配
return true;
} else if (children.length > 0 && stringData.length > 1) { // 既不是叶子节点，也不是最后一个字符，则继续递归查找
for (let i in children) {
if (children[i].key == stringData[1]) {
return this.searchNext(children[i], stringData.substring(1)); // 记得return 递归函数，否则获取的返回值为undefined
}
}
} else { // C1：叶子节点，C2：最后一个字符；若只满足其中一个条件，则不匹配
return false;
}
}
},
删除单词
遍历递归逻辑类似，先判断单词是否存在，不存在则不做处理。与查找、插入不同，删除需先找到单词，然后从单词字符串反向判断节点是否是叶子节点（如high，那么从h、g、i、h倒序遍历判断），如果是则删除，直到单词某个字符所处的节点是叶子节点为止。
// 删除字符串
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;
},
/**
* 先递归查找到字符串的叶子节点，然后从字符串的叶子节点逐级向根节点递归删除叶子节点，直到删除字符串
* @param parent 父节点
* @param index 子节点在父节点children数组中的索引位置
* @param stringData 递归遍历中的字符串
* @param delStr 调用delete方法时的原始字符串
*/
delNext: function (parent, index, stringData, delStr) {
//当前节点对象
let node = parent.children[index];
// 若字符与节点key不相等，则不匹配
if (stringData[0] != node.key) {
return false;
} else { // 若与key相等，继续判断
let children = node.children;
if (children.length == 0 && stringData.length == 1) { // 叶子节点，最后一个字符，则完全匹配
// 删除叶子节点，利用父节点删除子节点原理
parent.children.splice(index, 1);
// 字符串从尾部移除一个字符后，继续遍历删除方法
this.delete(delStr.substring(0, delStr.length - 1));
} else if (children.length > 0 && stringData.length > 1) { // 既不是叶子节点，也不是最后一个字符，则继续递归查找
for (let i in children) {
if (children[i].key == stringData[1]) {
return this.delNext(node, i, stringData.substring(1), delStr); // 记得return 递归函数，否则获取的返回值为undefined
}
}
}
}
},
输出所有的单词
从根节点开始遍历，console.log输出所有单词。递归单个节点直到叶子节点，输出单词，注意data.pop()，递归完毕找到叶子节点后，此操作目的返回原始遍历节点继续遍历直到找到下一个单词为止。
// 打印字符串
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(); // 注意，找打一个单词后，返回下一个初始节点继续遍历
}
}
三、调试运行
命令行执行：node Trie.js，查看console输出结果：
/**
* 测试
*/
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('爱你真的好难')));
// 查看输出发现，单词已删除
上面是原生JS实现，下面用TypeScript重写
TypeScript 这门语言越来越流行了，像主流框架React、Vue、Angular，都有很好的支持。重写主要体现TS的面向对象特性，在这里主要用到了TS的接口及实现、类的继承、模块、类型断言等，话不多说了，直接上代码：
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); //说明找到了对应的元素
} else { //那如果没有找到
if (children.length == 0) {
//当前没有子元素，所以应该判断一下
let node = new TrieNode(stringData[0]);
children.push(node);
this.insert(stringData.substring(1), node); //对吧，此时应该将该元素插入子元素中
} else { //当前子元素的长度不为零，需要查找一个合适的位置去插入元素
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); //对吧，此时应该将该元素插入子元素中
}
}
}
/**
* 先递归查找到字符串的叶子节点，然后从字符串的叶子节点逐级向根节点递归删除叶子节点，直到删除字符串
* @param parent 父节点
* @param index 子节点在父节点children数组中的索引位置
* @param stringData 递归遍历中的字符串
* @param delStr 调用deleteData方法时的原始字符串
*/
protected delNext(parent, index, stringData, delStr) {
//当前节点对象
let node = parent.children[index];
// 若字符与节点key不相等，则不匹配
if (stringData[0] != node.key) {
return false;
} else { // 若与key相等，继续判断
let children = node.children;
if (children.length == 0 && stringData.length == 1) { // 叶子节点，最后一个字符，则完全匹配
// 删除叶子节点，利用父节点删除子节点原理
parent.children.splice(index, 1);
// 字符串从尾部移除一个字符后，继续遍历删除方法
this.deleteData(delStr.substring(0, delStr.length - 1));
} else if (children.length > 0 && stringData.length > 1) { // 既不是叶子节点，也不是最后一个字符，则继续递归查找
for (let i in children) {
if (children[i].key == stringData[1]) {
return this.delNext(node, i, stringData.substring(1), delStr); // 记得return 递归函数，否则获取的返回值为undefined
}
}
}
}
}
/**
* 递归查找单词
* @param node
* @param stringData
*/
protected searchNext(node, stringData) {
// 若字符与节点key不相等，则不匹配
if (stringData[0] != node.key) {
return false;
} else { // 若与key相等，继续判断
let children = node.children;
if (children.length == 0 && stringData.length == 1) { // 叶子节点，最后一个字符，则完全匹配
return true;
} else if (children.length > 0 && stringData.length > 1) { // 既不是叶子节点，也不是最后一个字符，则继续递归查找
for (let i in children) {
if (children[i].key == stringData[1]) {
return this.searchNext(children[i], stringData.substring(1)); // 记得return 递归函数，否则获取的返回值为undefined
}
}
} else { // C1：叶子节点，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;
}
}
/**
* 节点
* @param {*} key
*/
class TrieNode {
key: string;
children: [];
constructor(key) {
this.key = key; // 节点字符
this.children = []; // 子节点集合
}
}
/**
* 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) {
//为了让代码工作，第二个参数，我使用了类型断言，避免TS编译报错，找不到key属性，也可以使用类型保护函数（从TrieBase类继承过来的isTrieNode函数判断）
this.printHelper(this.root.children[i], [(<TrieNode>this.root.children[i]).key]);
}
}
}
// 导出Trie模块
export { Trie }
在其他模块中使用Trie模块
// 导入模块
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
好了，讲完了，有点啰嗦莫怪，就写这么多吧，希望对你有所帮助，如不正确的地方也请指正，有问题也可留言或私信邮件，欢迎交流。
