树tree
树，对于前端来讲，算是比较复杂的数据结构了。它是我们了解图的前提。图可以用来表示对象之间的关系，并且这个对象可以是任意类型，只要对象之间有固定的关系，就可以用树的形式来表示。
虽然从数据结构上讲，树有很多种形式：
- 有序树
- 无序树
- 二叉树
- 满二叉树
- 完全二叉树
- 哈夫曼树
- 等等
我们仅仅用一个例子来简单的了解一下树这个数据结构。
字典树 trie tree
这个例子，我们将创建一个单词查找树trie tree，并用所有国家的列表对其进行预填充。然后，用户可以输入他们国家的名称，我们的组件将作为一个预先输入，并向用户显示可用的选项。
是的，你没有看错，这个功能类似于我们在常用的前端框架中的tree组件。我猜测原理是一样的，甚至这个例子比有的框架实现的更加优秀。
我们可以思考一下为什么我们需要字典树？如果我们百度一下字典树，我们会有如下结论：
字典树又称单词查找树，Trie树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。
换句话说，字典树就是一个优化的查找树，它的键是字符串。
举个例子，假设我们有个数组：
代码语言：javascript复制var friends = ['ross','rachel','adam','amy','joey'];
然后我们把它转化成一个字典树，就变成了下面这个样子：
从这个图上可以看到，从根节点开始，我们根据输入的字符串一步一步的构建了这棵树。单词被分解为单个字符，然后重复的节点不会被重新插入，而是被重用以构建树的其余部分。
添加
我们可以简单实现一个添加方法
代码语言：javascript复制export class Trie {
tree = {}
constructor() {}
add(input) {
// 设置根节点
var currentNode = this.tree
// 初始化下一个节点
var nextNode = null
// 拆分输入的字符串 adma --> a & dma
var curChar = input.slice(0,1)
input = input.slice(1)
//找到第一个字符的节点，然后接着拆分
while(currentNode[curChar] && curChar){
currentNode = currentNode[curChar]
curChar=input.slice(0,1)
input=input.slice(1)
}
// 当下个字符可用 则添加新的分支
while(curChar){
// 下一个节点
nextNode ={}
// 当前节点的当前字符
currentNode[curChar]=nextNode
// 迭代下一个
currentNode=nextNode
// 准备下一次迭代
curChar=input.slice(0,1)
input=input.slice(1)
}
}
}
上面的代码其实做了两件事：
- 确定树已构建到哪个级别。
- 将剩余部分添加为一个新子树。
我们添加一个admin字符串打印一下：
代码语言：javascript复制let t = new Trie()
t.add('admin')
t.add('addon')
console.log(t.tree)
/*
{
a:{
d:{
m:{
i:{
n:{}
}
},
d:{
o:{
n:{}
}
}
}
}
}
*/
我们会发现前面相同的两个字符是公共部分，后面的是m和d是两个不同的分支。
查找
有了添加方法，我们再来实现一个查找方法：
代码语言：javascript复制// 查找
search(input) {
let currentNode = this.tree
let curChar = input.slice(0,1)
input = input.slice(1)
// 根据当前的字符 提取子节点
while(currentNode[curChar] && curChar){
currentNode = currentNode[curChar]
curChar = input.slice(0,1)
input = input.slice(1)
}
// 如果到达结尾处也没有找到子节点
if(curChar && !currentNode(curChar)){
return {}
}
return currentNode
}
我们用之前的数据做个测试，然后就可以看到下面的结果。
加点提示信息呗
有时候我们需要在界面上展示一些提示信息，比如这种效果：
当然，这里只是举个例子。
这个也简单，我们只需要在新增节点的时候讲节点信息保存到一个对象中即可。
代码语言：javascript复制 // 新增
add(input) {
// 设置根节点
var currentNode = this.tree
// 初始化下一个节点
var nextNode = null
// 拆分输入的字符串 adma --> a & dma
var curChar = input.slice(0, 1)
console.log(curChar)
input = input.slice(1)
//找到第一个字符的节点，然后接着拆分
while (currentNode[curChar] && curChar) {
currentNode = currentNode[curChar]
// 保存提示信息
currentNode.remainder.push(input)
curChar = input.slice(0, 1)
input = input.slice(1)
}
// 当下个字符可用 则添加新的分支
while (curChar) {
// 下一个节点
nextNode = {
// 增加提示信息
remainder:[input]
}
// 当前节点的当前字符
currentNode[curChar] = nextNode
// 迭代下一个
currentNode = nextNode
// 准备下一次迭代
curChar = input.slice(0, 1)
input = input.slice(1)
}
}
思考
我们平时所用的组件中的树，是一种结构化的树，其原理和这个字典树有很多相似之处。
但是实现上，项目中前端生成树结构通常喜欢使用递归，这里使用的是用while创建引用的方式。
找时间可以比较一些这两者之间的区别。
