数据结构之字典树或前缀树(Trie)

class Node{
  char c;
  Node next[26];
 }
复制

class Node{
boolean isWord;
 Map<Character,Node> next;
 }
复制

  private class Node {
    // 我们设计时,不一定存放的一定是26个因为字母
    // 所以每一个节点指向的是n个节点
    // 所以每个节点存放的是一个映射Map,
    // map中的存放的是一个字符,及对应的下一个node
    // 可以这样理解,这个节点中存放的是可以去下一个节点的路标
    // 正好映射中存放的一一对应的关系,Character就是连接下一个不同节点的路径
    Map<Character, Node> next;


    // 这里没有设计 char c;
    // 因为这个节点需要存放的字符,就是上一个节点找过的路标,就是Character
    // char c


    // 我们trie存放的是一个单词,所以需要设计一个表示单词结尾的符号
    boolean isWord;


    // 构造函数
    public Node(boolean isWord) {
      this.isWord = isWord;
      next = new TreeMap<>();
    }


    // 无参
    public Node() {}
  }
复制

public class Trie{
    //内部类
   
    //设计成员变量
    private Node root;
    private int size;
    
    //构造函数
    public Trie(){
        root = new Node();
        size = 0;
    }
    
    //获取trie中存储的单词数量
    public int getSize(){
        return size;
    }
}
复制

//想trie中添加一个新的单词word
  public void add(String word){
    //定义当前trie的节点为根几点
    Node cur = root;
    
    //遍历每一个字符串的每一个字符
    for(int i = 0; i < word.length();i++){
      //取出每一个字符比较
      char c = word.charAt(i);
      //当前节点是否有能根据c,到达的下一个节点
      if(cur.next.get(c) == null){//没有找到下一个节点
        cur.next.put(c, new Node());
      }
      //当前节点网下移
      cur = cur.next.get(c);
      
      //判断最后节点位置isword是否为true
      if(!cur.isWord){
        cur.isWord = true;
        size++;
      }
    }
  }
复制

  //查询单词word是否存在trie中
  public boolean contains(String word){
    Node cur = root;
    for(int i = 0; i <word.length();i++ ){
      char c = word.charAt(i);
      if(cur.next.get(c) == null){
        return false;
      }
      cur = cur.next.get(c);
    }
    return cur.isWord;
  }
复制

// 查询单词word是否存在trie中
  public boolean isPrefix(String word) {
    Node cur = root;
    for (int i = 0; i < word.length(); i++) {
      char c = word.charAt(i);
      if (cur.next.get(c) == null) {
        return false;
      }
      cur = cur.next.get(c);
    }
    return true;
  }
复制