数据结构-前缀树(字典树)

简介

前缀树是N叉树的一种特殊形式。前缀树的每一个节点通常表示一个字符或者字符串。每一个节点拥有多个不同的子节点。值得注意的是，根节点表示空字符串。

前缀树的一个重要的特性是，节点所有的后代都与该节点相关的字符串有着共同的前缀。这就是前缀树名称的由来。

API设计

根据标题图可知，可以将前缀树分为两个对象，节点对象和前缀树对象，他们的功能各不相同

节点对象 TrieNode：

1. val: string 用来存储当前节点的值
2. children: object 用来存储子节点
3. isWord: boolean 用来表示是一个单词
4. add(val: string): TrieNode 插入节点，并返回插入的节点

前缀树对象 Trie：

1. root: TrieNode 存储节点
2. insert(word: string): void 向树中插入词语
3. search(word: string): boolean 查找是否有该词语
4. startsWith(prefix: string): boolean 前缀词语

实现

// 节点
var TrieNode = function ( val = "" ){
    // 一个节点只保存一个值
    this.val = val
    // 用来存储子节点
    this.children = {}
    // 标记单词结束
    this.isWord = false
}

// 向当前节点添加子节点
TrieNode.prototype.add = function( val ){
    let child = new TrieNode( val )
    this.children[val] = child
    return this.children[val]
}

/**
 * Initialize your data structure here.
 */
var Trie = function() {
    this.root = new TrieNode("")
};

/**
 * Inserts a word into the trie. 
 * @param {string} word
 * @return {void}
 */
Trie.prototype.insert = function(word) {
    let current = this.root
    let words = word.split("")
    for( let item of words ){
        if( current.children[ item ] ){
            current = current.children[item]
        } else {
            current = current.add( item )
        }
    }
    current.isWord = true
};

/**
 * Returns if the word is in the trie. 
 * @param {string} word
 * @return {boolean}
 */
Trie.prototype.search = function(word) {
    let current = this.root
    let words = word.split("")
    for( let item of words ){
        if( current.children[item] ){
            current = current.children[item]
        } else {
            return false
        }
    }
    return current.isWord
};

/**
 * Returns if there is any word in the trie that starts with the given prefix. 
 * @param {string} prefix
 * @return {boolean}
 */
Trie.prototype.startsWith = function(prefix) {
    let current = this.root
    let prefixs = prefix.split("")
    for( let item of prefixs ){
        if( current.children[item] ){
            current = current.children[item]
        } else {
            return false
        }
    }
    return true
};

参考材料

数据结构与算法（十一）Trie字典树

数据结构的故事之二叉树, 前缀树, N叉树

leetcode-208. 实现 Trie (前缀树)