字典树

需求

创建一个字典树，在字典树中查找是否包含某个单词

思考

什么是字典树？

在字典树中寻找单词时

会先根据第一个字符进行查找，如果没有第一个字符，直接返回false

如果有第一个字符，则会继续往下进行查找

字典树的作用：统计、排序和保存大量的字符串

如何定义查找边界？

字典树的节点存储的是单词的字符（字母）

为了表示一个单词是否出现，我们可以给单词的最后的字符加上标记（这样才能区分an与ant）

字典树中表示一个单词用的是一条链

字典树的根节点没有意义

字典树的操作

将单词插入到字典树中

function TrieNode(val){
    this.val = val;
    this.children = []; //用数组来存储子节点
    this.mark = 0; //纪录出现的次数
}
function insert(root,str){
    //算法：递归
    //递归的终止条件:单词所有字符插完
    //递归的递推表达式:父节点到子节点，截取单词第一位往后的部分
    //递归的返回值:不需要
    if(str[0]!==undefined){ //单词还没有遍历完
        if(root.children[str[0]]===undefined){ //没有子节点
            root.children[str[0]]=new TrieNode(str[0]);
        }
        insert(root.children[str[0]],str.slice(1));
    }else{
        root.mark++;
    }
}
let root = new TrieNode('');
insert(root,'and');
insert(root,'about');
insert(root,'by');
insert(root,'because');
insert(root,'as');
insert(root,'as');
console.log(root);

查找单词

function find(root, str) {
    if (str[0] !== undefined) {
        if (root.children[str[0]] === undefined) { //没找到，直接返回false
            return false
        } else {
            return find(root.children[str[0]], str.slice(1)); //递归查找
        }
    }else{  //递归结束
        if(root.mark>=1) return true
        else return false;
    }
}
console.log(find(root,'as')); //true
console.log(find(root,'bye'));  //false