字典树及其实现

简介

字典数，又称为前缀树，是哈希树的一种，是一种有序树。其中心思维是空间换时刻，使用字符串的公共前缀节省时刻，减少字符串的比较。其典型应用包括排序、全文搜索、web引擎等。

结构

每个树节点保护两个元素，第一个是包括26个字典数节点的数组，第二个是每个节点是否是单词结尾的标识，我们以sea,sells,she三个单词为例构建字典树，其逻辑结构如下图左面所示，有部分公共字符是共用的，其物理结构如下图右边所示，保护一个26位的数组，若某个字符存在，则在数组的对应方位寄存一个节点，这个节点又向下保护一个26位的数组，如此继续向下保护，直到字符串完毕。

代码完成

Java完成

class Trie {
    boolean isEnd;
    Trie[] next;
    public Trie() {
        isEnd = false;
        next = new Trie[26];
    }
    public void insert(String word) {
        Trie node = this;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            if (node.next[c - 'a'] == null) {
                node.next[c - 'a'] = new Trie();
            }
            node = node.next[c - 'a'];
        }
        node.isEnd = true;
    }
    public boolean search(String word) {
        Trie node = this;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            node = node.next[c - 'a'];
            if (node == null) {
                return false;
            }
        }
        return node.isEnd;
    }
    public boolean startsWith(String prefix) {
        Trie node = this;
        for (int i = 0; i < prefix.length(); i++) {
            char c = prefix.charAt(i);
            node = node.next[c - 'a'];
            if (node == null) {
                return false;
            }
        }
        return true;
    }
}

代码简要剖析：

界说一个数组int[] trie和一个完毕标识，并在结构办法中初始化，trie初始化为26位数组，完毕标识默认为false。

insert()办法加入新字符串时，循环遍历每一个字符，假如该字符不存在，就在对应的方位新建一个Trie节点，假如存在，则当时节点直接向下移动,当字符串完毕遍历时，将最后一个字符的完毕标识设为true。

search（）办法遍历字符串，若某个字符不存在，则这个字符串不存在，若最后一个字符的完毕标识isEnd不是false，则表明这个字符串在字典树中找不到。

startsWith()办法和search()类似，只是不再以isEnd判读是否存在，在循环完毕的时候，假如所有的字符都存在，则存在这个前缀。

go语言的完成和Java差不多。

Go完成

type Trie struct {
    child []*Trie
    isEnd bool
}
func Constructor() Trie {
    return Trie{make([]*Trie, 26), false}
}
func (this *Trie) Insert(word string)  {
    node := this
    for _, value := range word {
        if node.child[value - 'a'] == nil {
            node.child[value - 'a'] = &Trie{make([]*Trie, 26), false}
        }
        node = node.child[value - 'a']
    }
    node.isEnd = true
}
func (this *Trie) Search(word string) bool {
    node := this
    for _, value := range word {
        node = node.child[value - 'a']
        if node == nil {
            return false
        }
    }
    return node.isEnd
}
func (this *Trie) StartsWith(prefix string) bool {
    node := this
    for _, value := range prefix {
        node = node.child[value - 'a']
        if node == nil {
            return false
        }
    }
    return true
}