Trie树的JS或TS实现

作者: 烟伤肺 | 来源:发表于2018-08-31 08:50 被阅读0次

数据结构在各大开发语言中应用广泛，尤其是后端开发对数据的处理，而大部分前端开发很少应用到，或是应用场景不允许等因素，但是了解数据结构却对程序开发都是有很大裨益的，那么接下来介绍Trie树的前端实现。

Trie的简介

Trie树，简称“字典树或前缀树”，可以存储字符串与值的对应关系，它与 Java 的 HashMap 功能相同，以 key-value 形式存储，Trie树的key是单个字符。

Trie的数据结构特点

根节点不包含字符，除根节点意外每个节点只包含一个字符。
从根节点到某一个节点，路径上经过的字符连接起来，为该节点对应的字符串。
每个节点的所有子节点包含的字符串不相同。
如果字符的种数为n，则每个结点的出度为n，这也是空间换时间的体现，浪费了很多的空间。
插入查找的复杂度为O(n)，n为字符串长度

如图，跟节点是root，没有存储任何字符，它的key为空，包含了一个数组存放子节点。

Trie树的数据结构

Trie树的操作

插入节点
向树中存储一个单词，比如high，首先从root开始，遍历子节点从high的第一个字符h开始比较，如果找到了对应的子节点，则递归遍历子节点的children继续查找，并与单词的下一个字符（i）比较，直到最后一个字符h为止，如果能找到最后一个字符则说明已存在单词前缀；如果过程中未找到则取出字符进行插入到当前节点中，直到单词的最后一个字符。
查找节点
查找节点的过程，其实跟插入节点类似，也是遍历+递归判断树节点查找单词是否存在，其满足条件：单词的最后一个字符所在节点是叶子节点。
删除节点
删除一个单词，一般在应用中很少操作，但也只需要删除节点即可，先查找到节点判断是否存在，如果存在，则从单词倒序递归判断字符是否是叶子节点，如果是则删除，直到不是叶子节点结束。

原生JS代码实现

一、定义数据结构

Trie有一个根节点root，它的key为null。

/**
 * Trie
 */
function Trie() {
    this.root = new TrieNode(null);
}

TrieNode有两个属性，其中key代表一个字符，children数组表示子节点。

/**
 * 节点
 * @param {*} key 
 */
function TrieNode(key) {
    this.key = key; // 节点字符
    this.children = []; // 子节点集合
}

二、实现Trie的插入、查找、删除、输出

为了更好的描述具体实现细节，以下先声明列出我要扩展的方法类型。接下来将一步一步去讲解和实现每个方法及细节。

Trie.prototype = {
    // 插入单词
    insertData:(stringData)=>void,
    insert:(stringData,node)=>void,
    // 查找单词
    search:(queryData)=>boolean,
    searchNext:(node,stringData)=>boolean, // 递归
    // 删除单词
    delete:(stringData)=>this,
    delNext:(parent, index, stringData, delStr)=>boolean, // 递归
    // 打印树上的所有单词
    printData:()=>void,
    printHelper:(node, data)=>void // 递归
}

插入单词

1、从根节点开始遍历树节点，将节点的key的值与字符串第一个字符比较；
2、如果找到了字符，则截取剩余子字符串和当前节点继续递归；
3、如果没有找到字符，则判断当前节点是否存在子节点，若不存在则直接插入，如果存在子节点，则遍历子节点取出字符与当前字符判断排序位置，最后在该位置插入节点；
4、直到字符串最后一个字符，即可完成整个单词的插入。

    insertData: function (stringData) {
        this.insert(stringData, this.root);
    },
    // 递归判断插入
    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); //说明找到了对应的节点
        } else { //那如果没有找到则插入
            if (children.length == 0) { //当前节点没有子节点
                let node = new TrieNode(stringData[0]);
                children.push(node);
                this.insert(stringData.substring(1), node); //将该字符节点插入节点的children中
            } 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中
            }
        }
    },

查找单词，判断是否存在

遍历递归逻辑类似，请查看代码具体注释，需要注意的是调用递归函数时别忘了return 函数返回值。

    // 查询字符串
    search: function (queryData) {
        if (queryData == '' || this.root.children.length == 0) {
            return false;
        }
        for (let i in this.root.children) {
            if (this.searchNext(this.root.children[i], queryData)) {
                return true;
            }
        }
        return false;
    },
    // 递归查询判断
    searchNext: function (node, stringData) {
        // 若字符与节点key不相等，则不匹配
        if (stringData[0] != node.key) {
            return false;
        } else { // 若与key相等，继续判断
            let children = node.children;
            if (children.length == 0 && stringData.length == 1) { // 叶子节点，最后一个字符，则完全匹配
                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;
            }
        }
    },

删除单词

遍历递归逻辑类似，先判断单词是否存在，不存在则不做处理。与查找、插入不同，删除需先找到单词，然后从单词字符串反向判断节点是否是叶子节点（如high，那么从h、g、i、h倒序遍历判断），如果是则删除，直到单词某个字符所处的节点是叶子节点为止。

    // 删除字符串
    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
                    }
                }
            }
        }
    },

输出所有的单词

从根节点开始遍历，console.log输出所有单词。递归单个节点直到叶子节点，输出单词，注意data.pop()，递归完毕找到叶子节点后，此操作目的返回原始遍历节点继续遍历直到找到下一个单词为止。

    // 打印字符串
    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);
            data.pop(); // 注意，找打一个单词后，返回下一个初始节点继续遍历
        }
    }

三、调试运行

命令行执行：node Trie.js，查看console输出结果：


/**
 * 测试
 */
let trie = new Trie();

trie.insertData('我爱你');
trie.insertData('我爱你中国');
trie.insertData('我爱你宝贝');
trie.insertData('我爱你中原');
trie.insertData('爱你一万年');
trie.insertData('永远爱你');
trie.insertData('爱你真的好难');

trie.printData();

// console：
// > 我爱你中原
// > 我爱你中国
// > 我爱你宝贝
// > 永远爱你
// > 爱你一万年
// > 爱你真的好难

// console.log(trie.search('我爱你')); // false
// console.log(trie.search('我爱你中国')); // true
// console.log(trie.search('我爱你宝宝')); // false
// console.log(trie.search('我爱你宝贝')); // true

console.log(JSON.stringify(trie.delete('爱你真的好难')));
// 查看输出发现，单词已删除

上面是原生JS实现，下面用TypeScript重写

TypeScript 这门语言越来越流行了，像主流框架React、Vue、Angular，都有很好的支持。重写主要体现TS的面向对象特性，在这里主要用到了TS的接口及实现、类的继承、模块、类型断言等，话不多说了，直接上代码：

Trie.ts文件

/**
 * 接口类
 */
interface ITrie {
    /**
     * 插入单词
     * @param data 
     */
    insertData(data: string): void;
    /**
     * 删除单词
     * @param data 
     */
    deleteData(data: string): Trie;
    /**
     * 查找单词
     * @param data 
     */
    searchData(data: string): boolean;
    /**
     * 输出单词列表
     */
    printData(): void;
}

/**
 * 基类
 */
class TrieBase {
    /**
     * 本类不能实例化对象，能被继承
     */
    protected constructor() { }

    /**
     * 占个位，去派生类中重写
     * @param stringData 
     */
    protected deleteData(stringData) {
        return
    }

    /**
     * 递归插入单词
     * @param stringData 
     * @param node 
     */
    protected insert(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); //说明找到了对应的元素
        } else { //那如果没有找到
            if (children.length == 0) {
                //当前没有子元素，所以应该判断一下
                let node = new TrieNode(stringData[0]);
                children.push(node);
                this.insert(stringData.substring(1), node); //对吧，此时应该将该元素插入子元素中
            } 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); //对吧，此时应该将该元素插入子元素中
            }
        }
    }

    /**
     * 先递归查找到字符串的叶子节点，然后从字符串的叶子节点逐级向根节点递归删除叶子节点，直到删除字符串
     * @param parent 父节点
     * @param index 子节点在父节点children数组中的索引位置
     * @param stringData 递归遍历中的字符串
     * @param delStr 调用deleteData方法时的原始字符串
     */
    protected delNext(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.deleteData(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
                    }
                }
            }
        }
    }

    /**
     * 递归查找单词
     * @param node 
     * @param stringData 
     */
    protected searchNext(node, stringData) {
        // 若字符与节点key不相等，则不匹配
        if (stringData[0] != node.key) {
            return false;
        } else { // 若与key相等，继续判断
            let children = node.children;
            if (children.length == 0 && stringData.length == 1) { // 叶子节点，最后一个字符，则完全匹配
                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;
            }
        }
    }

    /**
     * 递归打印单词
     * @param node 
     * @param data 
     */
    protected printHelper(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);
            data.pop();
        }
    }

    /**
     * 类型保护，以免typescript报错，或使用类型断言
     * @param node 
     */
    protected isTrieNode(node: TrieNode): node is TrieNode {
        return (<TrieNode>node).key !== undefined;
    }
}

/**
 * 节点
 * @param {*} key
 */
class TrieNode {
    key: string;
    children: [];
    constructor(key) {
        this.key = key; // 节点字符
        this.children = []; // 子节点集合
    }
}

/**
 * Trie类
 */
class Trie extends TrieBase implements ITrie {
    root: TrieNode;
    constructor() {
        super();
        this.root = new TrieNode(null);
    }
    //插入单词（字符串）
    insertData(stringData): void {
        this.insert(stringData, this.root);
    }
    //删除单词
    deleteData(stringData): Trie {
        if (this.searchData(stringData)) { // 判断是否存在该单词（字符串）
            for (let i in this.root.children) {
                if (this.delNext(this.root, i, stringData, stringData)) {
                    return;
                }
            }
        }
        return this;
    }
    //查找单词（字符串）
    searchData(queryData): boolean {
        if (queryData == '' || this.root.children.length == 0) {
            return false;
        }
        for (let i in this.root.children) {
            if (this.searchNext(this.root.children[i], queryData)) {
                return true;
            }
        }
        return false;
    }
    //输出所有单词（字符串）
    printData(): void {
        for (let i in this.root.children) {
            //为了让代码工作，第二个参数，我使用了类型断言，避免TS编译报错，找不到key属性，也可以使用类型保护函数（从TrieBase类继承过来的isTrieNode函数判断）
            this.printHelper(this.root.children[i], [(<TrieNode>this.root.children[i]).key]);
        }
    }
}

// 导出Trie模块
export { Trie }

在其他模块中使用Trie模块

// 导入模块
import {Trie} from 'Trie';

/**
 * 使用
 */
let trieObj = new Trie();

trieObj.insertData('我爱你');
trieObj.insertData('我爱你中国');
trieObj.insertData('我爱你宝贝');
trieObj.insertData('我爱你中原');
trieObj.insertData('爱你一万年');
trieObj.insertData('永远爱你');
trieObj.insertData('爱你真的好难');

trieObj.printData();

// console：
// > 我爱你中原
// > 我爱你中国
// > 我爱你宝贝
// > 永远爱你
// > 爱你一万年
// > 爱你真的好难

console.log(trieObj.searchData('我爱你')); // false
console.log(trieObj.searchData('我爱你中国')); // true
console.log(trieObj.searchData('我爱你宝宝')); // false
console.log(trieObj.searchData('我爱你宝贝')); // true

console.log(JSON.stringify(trieObj.deleteData('爱你真的好难')));

运行TS

// 安装
npm install -g typescript
// 编译生成Trie.js
tsc Trie.ts 
// 运行
node Trie.js

好了，讲完了，有点啰嗦莫怪，就写这么多吧，希望对你有所帮助，如不正确的地方也请指正，有问题也可留言或私信邮件，欢迎交流。