JavaScript实现字典树

字典树，也叫前缀树或Trie树，是一种用于快速检索字符串的数据结构。它常常被用于实现自动完成或词频统计的功能。在本文中，我们将使用JavaScript来实现一个字典树。

字典树简介

字典树是一种树状数据结构，用于存储关联数组，其中的键通常是字符串。字典树的根节点为空，每个节点包含一个字符或一个字符的部分。从根节点到某个叶节点的路径上，经过的字符连接起来就是该节点对应的字符串。

字典树的实现

下面是一个简单的字典树的实现代码：

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

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

  insert(word) {
    let currentNode = this.root;

    for (let i = 0; i < word.length; i++) {
      const char = word[i];
      if (!currentNode.children[char]) {
        currentNode.children[char] = new TrieNode();
      }
      currentNode = currentNode.children[char];
    }

    currentNode.isEndOfWord = true;
  }

  search(word) {
    let currentNode = this.root;

    for (let i = 0; i < word.length; i++) {
      const char = word[i];
      if (!currentNode.children[char]) {
        return false;
      }
      currentNode = currentNode.children[char];
    }

    return currentNode.isEndOfWord;
  }
}

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

在上面的代码中，我们定义了两个类：TrieNode和Trie。TrieNode类表示一个字典树节点，它包含一个指向子节点的映射(children)和一个布尔值(isEndOfWord)，用于标记该节点是否是一个单词的结尾。

Trie类是字典树的主要实现。它包含一个根节点(root)，并提供了两个方法：insert用于将一个单词插入字典树，search用于搜索一个单词是否存在于字典树中。

在insert方法中，我们从根节点开始遍历单词的每个字符，依次插入到字典树中。如果某个字符对应的子节点不存在，则创建一个新的节点，并将其设置为当前节点的子节点。然后，我们将当前节点更新为子节点，并继续处理下一个字符。最后，将当前节点标记为一个单词的结尾。

在search方法中，我们遍历目标单词的每个字符，并继续查找对应的子节点。如果某个字符对应的子节点不存在，则说明目标单词不存在于字典树中。如果遍历完成后，当前节点被标记为一个单词的结尾，则说明目标单词存在于字典树中。

字典树的应用

字典树常常被用于实现自动完成或词频统计的功能。通过将大量的词汇构建成字典树，我们可以非常高效地完成单词的匹配和统计。

此外，字典树还可以用于查找字符串的最长公共前缀。我们可以通过遍历字典树的每一层，如果某一层的子节点数量为1，则表示公共前缀继续延伸，可以将对应的字符添加到结果中。一旦某一层的子节点数量大于1或当前节点标记为一个单词的结尾，就可以停止遍历，返回结果。

总结

字典树是一种非常有用的数据结构，特别适合用于存储和处理大量的字符串。通过将字符串按照字符拆分，并构建成树状结构，我们可以极大地提高字符串的检索和匹配效率。希望本文对你理解字典树的实现和应用有所帮助，谢谢阅读！