参考链接

实现

  1. import java.util.HashMap;
  2. import java.util.Map;
  4. /**
  5.  * 字典树， 以实现基本的增删查操作
  6.  */
  7. public class Trie {
  8.     /**
  9.      * 根结点
  10.      */
  11.     private Node root;
  13.     /**
  14.      * 单词数量
  15.      */
  16.     private int size;
  18.     public Trie() {
  19.         root = new Node();
  20.     }
  22.     /**
  23.      * 添加单词
  24.      *
  25.      * @param word 单词
  26.      */
  27.     public void add(String word) {
  28.         Node p = root;
  29.         for (char ch : word.toCharArray()) {
  30.             if (p.next.get(ch) == null) {
  31.                 p.next.put(ch, new Node());
  32.             }
  33.             p = p.next.get(ch);
  34.         }
  35.         // 该节点上没有单词则加上单词
  36.         // 防止相同单词重复添加
  37.         if (!p.isWord) {
  38.             p.isWord = true;
  39.             ++size;
  40.         }
  41.     }
  43.     /**
  44.      * 查询单词
  45.      *
  46.      * @param word 单词
  47.      * @return 是否存在于Trie中
  48.      */
  49.     public boolean contains(String word) {
  50.         Node p = root;
  51.         for (char ch : word.toCharArray()) {
  52.             p = p.next.get(ch);
  53.             if (p == null) {
  54.                 return false;
  55.             }
  56.         }
  57.         return p.isWord;
  58.     }
  60.     /**
  61.      * 删除一个单词
  62.      *
  63.      * @param word 单词
  64.      * @return 是否删除成功
  65.      */
  66.     public boolean delete(String word) {
  67.         Node p = root;
  68.         for (char ch : word.toCharArray()) {
  69.             p = p.next.get(ch);
  70.             if (p == null) {
  71.                 return false;
  72.             }
  73.         }
  74.         if (p.isWord) {
  75.             --size;
  76.             p.isWord = false;
  77.             if (p.next.size() == 0) {
  78.                 p.next = null;
  79.                 p = null;
  80.             }
  81.             return true;
  82.         } else {
  83.             return false;
  84.         }
  85.     }
  86. }
  88. /**
  89.  * 字符结点
  90.  */
  91. class Node {
  92.     /**
  93.      * 当前结点是否为某个单词的结尾
  94.      */
  95.     public boolean isWord;
  97.     /**
  98.      * 用Map存储子结点
  99.      */
  100.     public Map<Character, Node> next;
  102.     public Node() {
  103.         next = new HashMap<>();
  104.     }
  106.     public Node(boolean isWord) {
  107.         this.isWord = isWord;
  108.     }
  109. }
  111. class Main {
  112.     public static void main(String[] args) {
  113.         Trie trie = new Trie();
  114.         trie.add("hello");
  115.         trie.add("app");
  116.         trie.add("test");
  117.         System.out.println(trie.contains("test"));
  118.         System.out.println(trie.contains("tes"));
  119.         System.out.println(trie.delete("test"));
  120.         System.out.println(trie.contains("test"));
  121.     }
  122. }