当前位置：首页 > JavaScript

js实现前缀树

2026-03-16 06:49:49JavaScript

前缀树（Trie）的基本概念

前缀树是一种树形数据结构，用于高效存储和检索字符串集合。每个节点代表一个字符，从根节点到某一节点的路径构成一个字符串。常用于自动补全、拼写检查等场景。

实现前缀树的核心结构

使用对象（或Map）表示节点，每个节点包含子节点和标记是否为单词结尾的属性。

js实现前缀树

class TrieNode {
    constructor() {
        this.children = {}; // 子节点
        this.isEndOfWord = false; // 标记是否为单词结尾
    }
}

前缀树的插入操作

从根节点开始，逐字符插入字符串。若字符不存在则创建新节点，最后标记单词结尾。

js实现前缀树

class Trie {
    constructor() {
        this.root = new TrieNode();
    }

    insert(word) {
        let node = this.root;
        for (const char of word) {
            if (!node.children[char]) {
                node.children[char] = new TrieNode();
            }
            node = node.children[char];
        }
        node.isEndOfWord = true;
    }
}

前缀树的搜索操作

检查字符串是否存在：逐字符匹配，若全部字符匹配且最后一个节点标记为结尾，则返回true。

search(word) {
    let node = this.root;
    for (const char of word) {
        if (!node.children[char]) {
            return false;
        }
        node = node.children[char];
    }
    return node.isEndOfWord;
}

前缀树的前缀检查

检查是否存在以给定前缀开头的单词，逻辑与搜索类似，但无需检查结尾标记。

startsWith(prefix) {
    let node = this.root;
    for (const char of prefix) {
        if (!node.children[char]) {
            return false;
        }
        node = node.children[char];
    }
    return true;
}

完整代码示例

class TrieNode {
    constructor() {
        this.children = {};
        this.isEndOfWord = false;
    }
}

class Trie {
    constructor() {
        this.root = new TrieNode();
    }

    insert(word) {
        let node = this.root;
        for (const char of word) {
            if (!node.children[char]) {
                node.children[char] = new TrieNode();
            }
            node = node.children[char];
        }
        node.isEndOfWord = true;
    }

    search(word) {
        let node = this.root;
        for (const char of word) {
            if (!node.children[char]) {
                return false;
            }
            node = node.children[char];
        }
        return node.isEndOfWord;
    }

    startsWith(prefix) {
        let node = this.root;
        for (const char of prefix) {
            if (!node.children[char]) {
                return false;
            }
            node = node.children[char];
        }
        return true;
    }
}

使用示例

const trie = new Trie();
trie.insert("apple");
console.log(trie.search("apple"));   // true
console.log(trie.search("app"));     // false
console.log(trie.startsWith("app")); // true