DataStructure-Trie前缀树

前缀树 ｜ Trie ｜ Prefix Tree

前缀树，顾名思义，就是由前缀构成的一棵树。

有什么用呢？

• 搜索框里的自动补全
• 拼写检查
• 9键键盘的单词预测，比如输入 hello，后面提示world

这些都是前缀树的应用。

简单的来说，就是将很多不同的字符串，放到同一棵树里，前缀相同的部分构成一个前缀树的节点。

比如，apple 和 application，就可以变成 appl -> e 和 appl -> ication。

LeetCode 相关题目

208 Implement Trie (Prefix Tree)

211 Design Add and Search Words Data Structure

实现思路

首先，设计一棵树，肯定要从节点开始。

TrieNode

在这里，我们规定所有放入前缀树的字符串都是lowercase的字母。

那么，在每一个节点上，就可以记录会出现的子节点的字母，为了方便进行遍历，可以使用一个长度为26的TrieNode[]数组来记录。根据当前的char - 'a' 这个index就可以获得下一层的节点。

此外，还需要记录，该节点是否是最后一个字母。当然通过遍历当前节点的TrieNode[] 数组也是可以判断是否为end，但是那样也太麻烦了。

然后，再提供一些方法供调用。

TrieNode类如下。

class TrieNode{
    
    boolean isEnd;
    
    final int R = 26;
    
    TrieNode[] links;//相当于二叉树里的 TreeNode left, TreeNode right。
    
    public TrieNode(){
        links = new TrieNode[R];//创建每个节点，都要分配这个数组
    }
    
    //判断当前节点有没有被ch这个字符连接
    public boolean containsKey(char ch){
        return links[ch - 'a'] != null;
    }
    
    //在当前节点，获得字符为ch的下一个节点。
    public TrieNode get(char ch){
        return links[ch - 'a'];
    }
    
    //添加下一个字符为ch的节点，并连接到这个树上
    //也就是在数组里赋值上这个新节点
    public void put(char ch, TrieNode node){
        links[ch - 'a'] = node;
    }
    
    public boolean isEnd(){
        return isEnd;
    }
    
    public void setEnd(){
        isEnd = true;
    }
}

Trie

class Trie {
    //树的根节点，实际上的作用就相当于dummyNode,不表示值，但含有所有首字母的link
    private TrieNode root;

    public Trie() {
        root =new TrieNode();
    }
    
    //把一段字符串放进前缀树里
    //遍历字符串，一个字符一个节点。
    public void insert(String word) {
        TrieNode node = root;
        for(int i = 0 ; i < word.length(); i++){
            char curCh = word.charAt(i);
            if(!node.containsKey(curCh)){
                node.put(curCh, new TrieNode());//links数组里没有这个字符，就新建一个并加入树
            }
            node = node.get(curCh);//向下遍历
        }
        
        node.setEnd();//遍历完，设置当前节点为end
    }
    
    public boolean search(String word) {
        TrieNode res = searchPrefix(word);
        
        return res != null && res.isEnd();
        
    }
    
    private TrieNode searchPrefix(String word) {
        TrieNode node = root;
        for(int i = 0 ; i < word.length(); i++) {
            char curCh = word.charAt(i);
            if(node.containsKey(curCh)){
                node = node.get(curCh);
            }else{
                return null;
            }
        }
        
        return node;
    }
    
    public boolean startsWith(String prefix) {
        TrieNode node = searchPrefix(prefix);
        return node != null;
    }
}