前缀树

前缀树

前缀树也被称为字典树，被广泛用在字典查找中。字典树也是一个非典型的多叉树，多叉好理解，即每个结点的分支数量可能为多个。为什么说非典型呢？因为它和一般的多叉树不一样。

一般的多叉树的结点是这样的：

struct TreeNode {
    VALUETYPE value;    //结点值
    TreeNode* children[NUM];    //指向孩子结点
};

而 Trie 的结点是这样的(假设只包含’a’~’z’中的字符)：

struct TrieNode {
    bool isEnd; //该结点是否是一个串的结束
    TrieNode* next[26]; //字母映射表
};

TrieNode结点中并没有直接保存字符值的数据成员，而是通过 next 的映射来找到对应值的

重要性质

每个结点至少包含两个基本属性，根节点一定要为空因为字符串没有一个固定的起点含有 next 即可

• children/next：数组或集合，罗列出每个分支当中包含的所有字符，最好使用 hash 这样可以直接进行查找

• isEnd：该节点是否为字符串的结尾

  基本操作

  创建

• 遍历一遍输入的字符串，对每个字符串的字符进行遍历

• 从前缀树的根节点开始，将每个字符加入到节点的children字符集当中
• 如果字符集已经包含了这个字符，跳过

• 如果当前字符是字符串的最后一个，把当前节点的isEnd标记为真

  搜索

• 从根节点出发，逐个匹配字符串，匹配到了就向下一层搜索，没有就立即返回

  实现 Trie (前缀树)

  实现一个 Trie (前缀树)，包含 insert, search, 和 startsWith 这三个操作。 ```jsx Trie trie = new Trie();

trie.insert(“apple”); trie.search(“apple”); // 返回 true trie.search(“app”); // 返回 false trie.startsWith(“app”); // 返回 true trie.insert(“app”);
trie.search(“app”); // 返回 true

```jsx
var TrieNode = function() {
    this.next = {};
    this.isEnd = false;
};
var Trie = function() {
    this.root = new TrieNode();
};
Trie.prototype.insert = function(word) {
    if (!word) return false;
    let node = this.root;
    for (let i = 0; i < word.length; ++i) {
        if (!node.next[word[i]]) {
            node.next[word[i]] = new TrieNode();
        }
        node = node.next[word[i]];
    }
    node.isEnd = true;
    return true;
};
Trie.prototype.search = function(word) {
    if (!word) return false;
    let node = this.root;
    for (let i = 0; i < word.length; ++i) {
        if (node.next[word[i]]) {
            node = node.next[word[i]];
        } else {
            return false;
        }
    }
      //之前的循环没有返回false那么就会判断树里的字符串是否结束
    return node.isEnd;
};
Trie.prototype.startsWith = function(prefix) {
    if (!prefix) return true;
    let node = this.root;
    for (let i = 0; i < prefix.length; ++i) {
        if (node.next[prefix[i]]) {
            node = node.next[prefix[i]];
        } else {
            return false;
        }
    }
      //之前的循环没有返回false那么就会返回true
    return true;
};