关于javascript:Tire树

66次阅读

共计 2158 个字符,预计需要花费 6 分钟才能阅读完成。

构造

  • 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 输入

正文完
 0