Tire树

结构

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

你可能感兴趣的