JavaScript实现Trie前缀树

"JavaScript Trie 前缀树的示例" 在计算机科学中，Trie树，也称为前缀树，是一种高效的字符串查找数据结构。它通过存储字符串的公共前缀来减少比较次数，从而提高搜索效率。Trie树特别适用于需要频繁进行字符串前缀查询的场景，例如自动补全、IP地址解析、关键词过滤等。 Trie树的基本性质如下： 1. 根节点不包含任何字符，通常只是一个起始点。 2. 从根节点到任意一个叶子节点的路径上的边代表了一个字符串，这个字符串由路径上经过的节点的字符组成。 3. 每个节点的子节点对应一个字符，且不同子节点的字符互不相同，这样可以保证每个字符串的唯一性。 在JavaScript中，我们可以使用数组来构建Trie树。由于JavaScript的数组是动态的，可以方便地添加新元素，因此很适合用来表示Trie树中的节点链接。每个节点通常包含以下几个属性： - `son`：一个数组，用于存储子节点，每个子节点对应一个字符。 - `value`：节点所代表的字符。 - `numPass`：记录有多少个字符串经过了这个节点。 - `isEnd`：布尔值，标记当前节点是否为一个字符串的结尾。 - `numEnd`：记录以当前节点为结尾的字符串的数量。 以下是一个简单的JavaScript Trie树实现： ```javascript class TrieNode { constructor() { this.son = new Array(58); // 假设只处理字母和数字，0-9 + a-z + A-Z this.value = null; this.numPass = 0; this.isEnd = false; this.numEnd = 0; } } class Trie { constructor() { this.root = new TrieNode(); } isValid(str) { return /^[a-z1-9]+$/i.test(str); } insert(word) { if (this.isValid(word)) { let cur = this.root; for (let i = 0; i < word.length; i++) { const c = word.charCodeAt(i) - 48; // 减去 '0' 的 charCode const node = cur.son[c]; if (node === null) { cur.son[c] = (node = new TrieNode()); node.value = word.charAt(i); node.numPass = 1; } else { node.numPass++; } cur = node; } cur.isEnd = true; cur.numEnd++; // 重复次数 return true; } else { return false; } } // remove 方法未给出，但一般包括从树中删除一个单词的逻辑 } ``` 在这个实现中，`insert`方法负责将一个字符串插入Trie树。首先，检查字符串是否有效（仅包含字母和数字）。然后，遍历字符串的每个字符，将其插入到相应的子节点中。如果节点不存在，则创建新的节点。最后，到达字符串末尾时，将`isEnd`标志设置为`true`，并增加`numEnd`计数。 值得注意的是，Trie树的删除操作相对复杂，因为它需要考虑字符串的共用前缀可能影响其他字符串的情况。在实际应用中，可能还需要实现`remove`方法来支持删除功能。 Trie树是一种高效的数据结构，尤其适用于字符串查找和前缀匹配。JavaScript中的实现利用了动态数组的灵活性，能够轻松构建和维护一个Trie树实例。