ZYZ/shared/pubUtils/trie.ts

function Trie(this: any) {
    this.root = new TrieNode(null);
    this.hitStr = '';
}

function TrieNode(this: any, key) {
    this.key = key; // 节点字符
    this.children = []; // 子节点集合
    this.end = false;
}

Trie.prototype = {
    insertData: function (stringData) {
        this.insert(stringData, this.root);
        // console.log(JSON.stringify(this.root, null, 2))
    },
    // 递归判断插入
    insert: function (stringData, node) {
        if (stringData == '') {
            return;
        }
        let children = node.children;
        let haveData = null;
        for (let i in children) {
            if (children[i].key == stringData[0]) {
                haveData = children[i];
            }
        }
        if (haveData) {
            this.insert(stringData.substring(1), haveData); //说明找到了对应的节点
            if (stringData.substring(1).length == 0) haveData.end = true;
        } else { //那如果没有找到则插入
            if (children.length == 0) { //当前节点没有子节点
                let node = new TrieNode(stringData[0]);
                children.push(node);
                this.insert(stringData.substring(1), node); //将该字符节点插入节点的children中
                if (stringData.substring(1).length == 0) node.end = true;
            } else { //当前节点存在子节点，需要查找一个合适的位置去插入新节点
                let validPosition = 0;
                for (let j in children) {
                    if (children[j].key < stringData[0]) {
                        validPosition++;
                    }
                }
                let node = new TrieNode(stringData[0]);
                children.splice(validPosition, 0, node);
                this.insert(stringData.substring(1), node); //将该字符节点插入节点的children中
                if (stringData.substring(1).length == 0) node.end = true;
            }
        }
    },
    // 查询字符串
    search: function (queryData) {
        if (queryData == '' || this.root.children.length == 0) {
            return false;
        }
        for (let j = 0; j < queryData.length; j++) {
            for (let i in this.root.children) {
                this.hitStr = '';
                if (this.searchNext(this.root.children[i], queryData.substring(j))) {
                    console.log('hitStr:' + this.hitStr);
                    return true;
                }
            }
        }

        return false;
    },
    // 获取命中的关键词
    getHitStr: function (queryData) {
        this.hitStr = '';
        this.search(queryData)
        return this.hitStr;
    },
    // 递归查询判断
    searchNext: function (node, stringData) {
        // 若字符与节点key不相等，则不匹配
        if (stringData[0] != node.key) {
            return false;
        } else { // 若与key相等，继续判断
            this.hitStr += node.key;
            let children = node.children;
            if (children.length == 0) { // 叶子节点，最后一个字符，则完全匹配
            // if (children.length == 0) { // 叶子节点，最后一个字符，则完全匹配
                return true;
            } else if (node.end) {
                return true;
            } else if (children.length > 0 && stringData.length > 1) { // 既不是叶子节点，也不是最后一个字符，则继续递归查找
                for (let i in children) {
                    if (children[i].key == stringData[1]) {
                        return this.searchNext(children[i], stringData.substring(1)); // 记得return 递归函数，否则获取的返回值为undefined
                    }
                }
            } else { // C1：叶子节点，C2：最后一个字符；若只满足其中一个条件，则不匹配
                return false;
            }
        }
    },
    // 删除字符串
    delete: function (stringData) {
        if (this.search(stringData)) { // 判断是否存在该单词（字符串）
            for (let i in this.root.children) {
                if (this.delNext(this.root, i, stringData, stringData)) {
                    return;
                }
            }
        }
        return this;
    },
    /**
     * 先递归查找到字符串的叶子节点，然后从字符串的叶子节点逐级向根节点递归删除叶子节点，直到删除字符串
     * @param parent 父节点
     * @param index 子节点在父节点children数组中的索引位置
     * @param stringData 递归遍历中的字符串
     * @param delStr 调用delete方法时的原始字符串
     */
    delNext: function (parent, index, stringData, delStr) {
        //当前节点对象
        let node = parent.children[index];
        // 若字符与节点key不相等，则不匹配
        if (stringData[0] != node.key) {
            return false;
        } else { // 若与key相等，继续判断
            let children = node.children;
            if (children.length == 0 && stringData.length == 1) { // 叶子节点，最后一个字符，则完全匹配
                // 删除叶子节点，利用父节点删除子节点原理
                parent.children.splice(index, 1);
                // 字符串从尾部移除一个字符后，继续遍历删除方法
                this.delete(delStr.substring(0, delStr.length - 1));
            } else if (children.length > 0 && stringData.length > 1) { // 既不是叶子节点，也不是最后一个字符，则继续递归查找
                for (let i in children) {
                    if (children[i].key == stringData[1]) {
                        return this.delNext(node, i, stringData.substring(1), delStr); // 记得return 递归函数，否则获取的返回值为undefined
                    }
                }
            }
        }
    },
    // 打印字符串
    printData: function () {
        for (let i in this.root.children) {
            this.printHelper(this.root.children[i], [this.root.children[i].key]);
        }
    },
    // 递归输出字符串
    printHelper: function (node, data) {
        if (node.children.length == 0) {
            console.log('>', data.join(''));
            return;
        }
        for (let i in node.children) {
            data.push(node.children[i].key);
            this.printHelper(node.children[i], data);
            // if (node.end) console.log(data);
            data.pop(); // 注意，找打一个单词后，返回下一个初始节点继续遍历
        }
    }
}

export default Trie;