字典树的创建以及搜索

字典树的特点

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

2、为了表示一个单词是否出现，我们可以给单词的最后的字符加上标记

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

4、字典树的跟节点没有什么意义

字典树的操作

1、把单词插入到字典里面

2、在字典树中查找单词

建树

建树算法过程

去根节点下面找这个单词的第一个字符是否出现

如果没出现就创建新的字符节点，字符串中移除当前字符，再往下走

如果出现了，字符串中移除当前字符，就直接往下走

在单词找完后，在最后节点做标记，多次创建标记递增

function TrieNode(val) {
        this.val = val;
        this.children = [];
        this.count = 0;//标记
    }
    function insert(root, str) {
        if (str[0]){
            // 当前节点与字符不相等->创建新的节点
            if (!root.children[str[0]]){
                root.children[str[0]] = new TrieNode(str[0])
            }
            // 递归 传入当前树节点以及剩余节点
            insert(root.children[str[0]], str.slice(1))
        } else {
            // 没有单词，递归终止且记入标记
            root.count ++
        }
    }

    // 创建根节点
    let root = new TrieNode('')
    //往根节点插入节点
    insert(root,'and')
    insert(root,'any')
    insert(root, 'about')
    insert(root,'any')
    insert(root, 'dr')
    insert(root, 'drive')
    insert(root, 'driver')
    insert(root, 'doctor')
    insert(root,'end')
    insert(root,'egg')
    insert(root,'egg')
    console.log(root)

图示建树过程

图示建树结果

字典树查找

字典树查找算法过程

去根节点下面找这个单词的第一个字符是否出现

如果没出现直接返回false

如果出现了，就直接往下找

在单词找完后，如果标记大于1，表示单词出现过，返回true

否则返回false

 // 查找
    function find(root, str) {
        // 没查找完
        if (str[0]){
            // 当前节点存在->往下找
            if (root.children[str[0]]){
                return find(root.children[str[0]], str.slice(1))
            } else {
                // 当前节点不匹配
                return false
            }
        } else {
            //查找完了，末尾标记是否大于0
            return root.count > 0
        }
    }
    console.log(find(root,'and'))
    console.log(find(root,'abo'))
    console.log(find(root,'eggs'))
    console.log(find(root,'egg'))

查找过程

查找结果