数据结构与算法插入排序（Insertion Sort）冒泡排序（Bubble Sort）选择排序（Selection Sort）快速排序（Quick Sort）希尔排序（Shell Sort）归并排序（Merge Sort）堆排序（Heap Sort）计数排序（Counting Sort）桶排序（Bucket Sort）基数排序（Radix Sort）栈(Stack)队列(Queue)链表( Linked List)集合(Set)哈希表/散列表（Hash Table）树（ Tree）_二叉树堆（Heap）字典树(Trie)图（Graph）
字典树(Trie)
Trie也可以叫做Prefix Tree（前缀树），也是一种搜索树。Trie分步骤存储数据，树中的每个节点代表一个步骤，trie常用于存储单词以便快速查找，比如实现单词的自动完成功能。 Trie中的每个节点都包含一个单词的字母，跟着树的分支可以可以拼写出一个完整的单词，每个节点还包含一个布尔值表示该节点是否是单词的最后一个字母。
Js的实现
1、字典树是一种树形结构，树形由root根节点和子节点组成
2、根节点是没有值的
3、从根节点的子节点开始，每个子节点存储一个字符，每个字符都不相同
4、从根节点到某节点，所形成的路径，将该路径中的所有节点的值连接起来，就是这个节点所对应的字符串
5、字典树可以用来搜索和统计，效率比hash高，是用空间换时间
6、查询和遍历都是从当前节点的子节点开始
class Treenode {
constructor(key,leaf){
this.key = key;
this.leaf = leaf;
this.count = 0;
if(!leaf){
this.children = [];
}
}
}
class Tree{
constructor(){
var root = new Treenode(null,false);
this.root = root;
}
run(strs){
var root = this.root;
for(let i=0;i<strs.length;i++){
this.insertNode(root,strs[i]);
}
}
//创建字典树
insertNode(node,str){
if(!node.leaf){
//当前节点的子节点中是否有字符串的第一个字符，从子节点中匹配
var child = node.children.find(function(child){
return child.key == str[0];
});
if(child){
//有多少单词通过这个节点,即由根至该节点组成的字符串模式出现的次数
child.count++;
//子节点中存在，则继续遍历下一个字符
this.insertNode(child,str.substring(1));
}else{
//子节点中没有，则插入该节点
if(str.length==1){
var child = new Treenode(str[0],true);
}else{
var child = new Treenode(str[0],false)
}
node.children.push(child);
this.insertNode(child,str.substring(1));
}
}
}
search(txt){
if(!txt){
return;
}
//从根节点开始查找匹配
var root = this.root;
var isIn = this.searchTxt(root,txt);
console.info(isIn);
}
searchTxt(node,txt){
if(!txt){
return false;
}
if(!node.leaf){
//判断子节点中是否有相等值
var child = node.children.find(function(child){
return child.key == txt[0];
});
if(!child){
//没有匹配到字符，说明不存在
return false;
}else if(child.leaf){
//说明已经是找到头了
return child;
}else {
if(txt.length==1){
//字符串已经匹配完，但是节点不是叶子节点，说明不存在
return false;
}
return this.searchTxt(child,txt.substring(1));
}
}else{
//查到了叶子节点，判断当前节点的值是否相等
if(node.key == txt[0]){
return node;
}else{
return false;
}
}
}
getRoot(){
return this.root;
}
}
var strs=['hello','hi','hello','hellen','red','read'];
var tree = new Tree();
tree.run(strs);
tree.search('hel');//false