算法疑难(js实现)---11、字典树

一、总结

一句话总结：

本题字典树的的操作就是1、把单词插入到字典树里面去和2、在字典树中查找单词，都是递归，分析好思路，代码很好敲

function TrieNode(val){
    this.val=val;
    this.children=[];
    this.count=0;//标记，表示单词是否出现
}

//1、把单词插入到字典树里面去
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.count++;
    }
}
let root=new TrieNode('');
insert(root,'and');
insert(root,'about');
insert(root,'as');
insert(root,'boy');
insert(root,'by');
insert(root,'because');
insert(root,'as');
console.log(root);

//2、在字典树中查找单词
function find(root,str){
    //递归的终止条件：在子节点中没找到 或者 单词找完
    //递归的递推表达式：父节点到子节点，单词的首字母就被用掉了
    //递归的返回值：true或者false
    if(str[0]!==undefined){
        if(root.children[str[0]]===undefined) return false;
        else return find(root.children[str[0]],str.slice(1));
    }else{
        if(root.count>=1) return true;
        else return false;
    }
    //查找单词的第一个字符是否在根节点的子节点中，如果出现了，就接着往下找
    //如果没出现，直接return false
    //在单词找完后，如果标记大于1，表示单词出现过，就return true，
    //否则return false
}
console.log(find(root,'close'));//false
console.log(find(root,'an'));//false
console.log(find(root,'as'));//true
console.log(find(root,'boy'));//true

1、字典树是什么？

字典树又称单词查找树，Trie树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。

它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。

2、字典树优点？

字典树利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。

3、字典树的作用？

统计，排序和保存大量的字符串

4、字典树的特点？

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

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

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

二、字典树

博客对应课程的视频位置：11、字典树
https://www.fanrenyi.com/video/20/247

  1 <!DOCTYPE html>
  2 <html lang="en">
  3 <head>
  4     <meta charset="UTF-8">
  5     <title>字典树</title>
  6 </head>
  7 <body>
  8 <!--
  9 需求：
 10 创建一个字典树，在字典树中查找是否包含某个单词
 11 
 12 单词序列：
 13 and
 14 about
 15 as
 16 boy
 17 by
 18 because
 19 as
 20 
 21 查找：
 22 close   false
 23 an   false
 24 as   true
 25 boy  true
 26 
 27 字典树是什么
 28 字典树又称单词查找树，Trie树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。
 29 
 30 字典树的作用
 31 统计，排序和保存大量的字符串
 32 
 33 字典树的特点
 34 1、字典树的节点存储的是单词的字符（字母）
 35 2、为了表示一个单词是否出现，我们可以给单词的最后的字符加上标记
 36 3、字典树中表示一个单词用的是一条链
 37 4、字典树的根节点没有什么意义
 38 
 39 字典树的操作
 40 1、把单词插入到字典树里面去
 41 2、在字典树中查找单词
 42 
 43 
 44 
 45 1、把单词插入到字典树里面去
 46 算法步骤：
 47 去跟节点下面去找这个单词的第一个字符是否出现，
 48 如果没出现，就创建，然后走这条路，
 49 如果出现了，就直接走这条路
 50 （在这个过程里面，单词的第一个字符就被消耗掉了）
 51 
 52 算法：
 53 递归
 54 
 55 
 56 2、在字典树中查找单词
 57 算法：
 58 递归
 59 
 60 算法步骤：
 61 查找单词的第一个字符是否在根节点的子节点中，如果出现了，就接着往下找
 62 如果没出现，直接return false
 63 在单词找完后，如果标记大于1，表示单词出现过，就return true，
 64 否则return false
 65 
 66 
 67 -->
 68 <script>
 69     function TrieNode(val){
 70         this.val=val;
 71         this.children=[];
 72         this.count=0;//标记，表示单词是否出现
 73     }
 74 
 75     //1、把单词插入到字典树里面去
 76     function insert(root,str){
 77         //递归的终止条件：把单词所有的字符插完（打标记的操作）
 78         //递归的递推表达式：父节点到子节点，单词的首字母就被用掉了
 79         //递归的返回值：不需要
 80 
 81         if(str[0]!==undefined){
 82             //去跟节点下面去找这个单词的第一个字符是否出现，
 83             //如果没出现，就创建，然后走这条路，
 84             //如果出现了，就直接走这条路
 85             if(root.children[str[0]]===undefined){
 86                 root.children[str[0]]=new TrieNode(str[0]);
 87             }
 88             insert(root.children[str[0]],str.slice(1));
 89         }else{
 90             root.count++;
 91         }
 92     }
 93     let root=new TrieNode('');
 94     insert(root,'and');
 95     insert(root,'about');
 96     insert(root,'as');
 97     insert(root,'boy');
 98     insert(root,'by');
 99     insert(root,'because');
100     insert(root,'as');
101     console.log(root);
102 
103     //2、在字典树中查找单词
104     function find(root,str){
105         //递归的终止条件：在子节点中没找到 或者 单词找完
106         //递归的递推表达式：父节点到子节点，单词的首字母就被用掉了
107         //递归的返回值：true或者false
108         if(str[0]!==undefined){
109             if(root.children[str[0]]===undefined) return false;
110             else return find(root.children[str[0]],str.slice(1));
111         }else{
112             if(root.count>=1) return true;
113             else return false;
114         }
115         //查找单词的第一个字符是否在根节点的子节点中，如果出现了，就接着往下找
116         //如果没出现，直接return false
117         //在单词找完后，如果标记大于1，表示单词出现过，就return true，
118         //否则return false
119     }
120     console.log(find(root,'close'));//false
121     console.log(find(root,'an'));//false
122     console.log(find(root,'as'));//true
123     console.log(find(root,'boy'));//true
124 </script>
125 </body>
126 </html>