构造
- Tire树又称前缀树，或字典树，个别用来保留字符集以及查问词句
- Tire树由根节点开始，根节点保留value为null，以及批示子节点的数组children
- 根节点当前，每个节点保留一个单词，由children关联，这样从根节点开始向下遍历，就能够查到残缺的词句
- 而具备雷同前缀的词句，会通过同一个父节点
一道题
给定一个data set，以及一个level，输入对应的格局，如：
level = ['province', 'city', 'name']；data = [ { 'province': '广东', 'city': '广州', 'name': '小明' }, { 'province': '广东', 'city': '深圳', 'name': '小李' }, { 'province': '广东', 'city': '广州', 'name': '小红' }, { 'province': '广西', 'city': '玉林', 'name': '小蓝' }];// 输入[ { "value": "广东", "children":[ { "value": "广州", "children": [ { "value": "小明" }, { "value": "小红" } ] }, { "value": "深圳", "children":[ { "value": "小李" } ] } ] }, { "value": "广西", "children":[ { "value": "玉林", "children": [ { "value": "小蓝" } ] } ] }]能够看到，最终转换的格局就是具备雷同前缀的放到一个对象上面，先实现Tire相干的类：
class TrieNode { constructor(value) { this.value = value; this.children = []; } findChild(value) { for (let child of this.children) { if(child.value === value) return child; } return false; } addChild(node) { this.children.push(node); }}- 树上的每个节点，保留value以及子节点数组children
- 同时提供findChild办法，因为树的构造，同一个父节点下的子节点，value都不雷同，找到则返回子节点，没找到则return false
- 最初提供退出子节点的办法
class TrieTree { constructor(arr = []) { this.root = new TrieNode(null); if (arr.length) { this.insert(arr); } } insert(valueArr) { // 塞入关系链 let node = this.root; for (let value of valueArr) { const findNode = node.findChild(value); if (findNode) node = findNode; // 如果曾经有相干子节点，间接指向子节点 else { // 如果没有，则新建子节点，并将指针指向子节点 const insertNode = new TrieNode(value); node.addChild(insertNode); node = insertNode; } } } print() { const ret = this.getPrintChildren(this.root); // 递归形式输入 console.log(ret) console.log(JSON.stringify(ret)); } getPrintChildren(node) { const ret = []; for (let childNode of node.children) { // 遍历子节点 const retNode = { value: childNode.value }; // 结构以后节点的value值 if (childNode.children.length) { // 如果以后节点有子节点，再递归并赋值给children属性 retNode.children = (this.getPrintChildren(childNode)); } ret.push(retNode) } return ret; }}- Trie树保留一个根节点，根节点上value为null
- 提供insert办法，insert接管的参数是一个数组，代表一条关系链，前面的元素是后面元素的后辈
- 通过遍历关系链，将每个元素转化成TrieNode，而后增加进对应节点的children中
- 最初递归getPrintChildren，能够将整课Trie树转化成须要输入的格局，只需从根元素开始，遍历子元素，并递归子元素的子元素，直到没有子元素，失去一个ret对象，最初通过print办法输入
const trieTree = new TrieTree(); // 新建一棵树for (let item of data) { const insertData = []; for (let key of level) { insertData.push(item[key]); // 依据level中的程序，将对象换成数组 } trieTree.insert(insertData); // 将一整条关系链塞入树中}trieTree.print();- 因为data set的格局是对象，须要依据level转成关系链，再插入tire树中，最初调用print输入