一、前缀树定义
1）单个字符串中，字符从前到后的加到一棵多叉树上
2）字符放在边上，节点上有专属的数据项（常见的是pass和end值）
3）样本增加形式，每个字符串都从根节点开始加，如果没有路就新建，如果有路就复用
4）增加时，沿途节点的pass值加1，每个字符串完结时来到的节点end值加1
作用：能够更加不便的实现前缀相干的查问
二、简版的前缀树
只能寄存26个小写字母组成的字符串
/** * 字符品种：只有26个小写字母 * * @author Java和算法学习：周一 */public static class Node1 { // 以后节点被通过了几次 private int pass; // 有多少个字符串以以后节点结尾 private int end; // 以后节点所有的子节点 private Node1[] nexts; // 节点只寄存26个小写字母 public Node1() { pass = 0; end = 0; // node[i] == null，节点不存在 nexts = new Node1[26]; }}public static class Trie1 { private Node1 root; public Trie1() { root = new Node1(); } /** * 向前缀树中增加一个字符串 */ public void insert(String word) { if (word == null) { return; } // 正在增加字符的节点 Node1 node = root; // 曾经有字符通过该节点，批改节点pass值 node.pass++; int path = 0; // 以后单词挨个字符的增加到前缀树上 char[] chars = word.toCharArray(); for (char aChar : chars) { // 以后字符应该走的门路 path = aChar - 'a'; // 以后节点的path门路对应节点不存在，则新建 if (node.nexts[path] == null) { node.nexts[path] = new Node1(); } // 以后节点的path门路对应节点必定曾经存在了 // 所以以后节点来到path门路对应节点 node = node.nexts[path]; // 曾经有字符达到该节点，批改pass值 node.pass++; } // 字符增加结束，批改最初节点的end值 node.end++; } /** * word单词之前加过多少次 */ public int search(String word) { if (word == null) { return 0; } int index = 0; char[] chars = word.toCharArray(); // 从根节点开始找 Node1 node = root; for (char aChar : chars) { // 以后字符应该走的门路 index = aChar - 'a'; // 以后节点的index门路对应节点不存在，间接返回 if (node.nexts[index] == null) { return 0; } // 以后节点的index门路对应节点存在，则以后查找节点来到index门路对应节点 node = node.nexts[index]; } // 最初以后节点的end值即是此单词加过的次数 return node.end; } /** * 所有曾经退出的字符串中，有多少是以pre为前缀的 */ public int prefixNumber(String pre) { if (pre == null) { return 0; } int index = 0; // 从根节点开始找 Node1 node = root; // 挨个字符找 char[] chars = pre.toCharArray(); for (char aChar : chars) { // 以后字符应该走的门路 index = aChar - 'a'; // 以后节点的index门路对应节点不存在，间接返回 if (node.nexts[index] == null) { return 0; } // 以后节点的index门路对应节点存在，则以后查找节点来到index门路对应节点 node = node.nexts[index]; } // 最初以后查找节点所处节点的pass值即是以pre为前缀的数量 return node.pass; } /** * 在前缀树中删除某个字符串 */ public void delete(String word) { // 字符串存在才执行删除逻辑 if (search(word) != 0) { // 从根节点开始 Node1 node = root; // 批改根节点pass值 node.pass--; int index = 0; char[] chars = word.toCharArray(); for (char aChar : chars) { // 以后字符应该走的门路 index = aChar - 'a'; // 以后节点index门路对应节点的pass值减一 if (--node.nexts[index].pass == 0) { // 减一后如果为0，表明没有字符串再通过此节点 // 将此节点index门路对应节点置空，帮忙GC node.nexts[index] = null; return; } // 减一后不为0，表明还有字符串通过此节点 // 则以后节点挪动到index门路对应的节点 node = node.nexts[index]; } // 最初批改节点所在位置end值 node.end--; } }}三、通用的前缀树
不限定寄存的内容
/** * 字符品种：不肯定只有26个小写字母 * * @author Java和算法学习：周一 */public static class Node2 { // 以后节点被通过了几次 private int pass; // 有多少个字符串以以后节点结尾 private int end; // 以后节点所有的子节点，Key为节点对应字符串字符转换为整型后的ASCII码值 private HashMap<Integer, Node2> nexts; public Node2() { pass = 0; end = 0; nexts = new HashMap<>(); }}public static class Trie2 { private Node2 root; public Trie2() { root = new Node2(); } /** * 向前缀树中增加一个字符串，此字符串不肯定全是小写字母 */ public void insert(String str) { if (str == null) { return; } // 正在增加字符串的节点 Node2 node = root; // 曾经有字符通过该节点，批改节点pass值 node.pass++; int index = 0; // 以后字符串挨个字符的增加到前缀树上 char[] chars = str.toCharArray(); for (char aChar : chars) { index = aChar; // 以后节点的index门路对应节点不存在，则新建 if (!node.nexts.containsKey(index)) { node.nexts.put(index, new Node2()); } // 以后节点的index门路对应节点曾经存在了 // 所以以后节点来到index门路对应节点 node = node.nexts.get(index); // 曾经有字符达到该节点，批改pass值 node.pass++; } // 字符串增加结束，批改最初节点的end值 node.end++; } /** * 字符串之前加过多少次 */ public int search(String str) { if (str == null) { return 0; } int index = 0; char[] chars = str.toCharArray(); // 从根节点开始找 Node2 node = root; for (char aChar : chars) { // 以后字符应该走的门路 index = aChar; // 以后节点的index门路对应节点不存在，间接返回 if (!node.nexts.containsKey(index)) { return 0; } // 以后节点的index门路对应节点存在，则以后查找节点来到index门路对应节点 node = node.nexts.get(index); } // 最初以后节点的end值即是此字符串加过的次数 return node.end; } /** * 所有曾经退出的字符串中，有多少是以pre为前缀的 */ public int prefixNumber(String pre) { if (pre == null) { return 0; } int index = 0; // 从根节点开始找 Node2 node = root; // 挨个字符找 char[] chars = pre.toCharArray(); for (char aChar : chars) { // 以后字符应该走的门路 index = aChar; // 以后节点的index门路对应节点不存在，间接返回 if (!node.nexts.containsKey(index)) { return 0; } // 以后节点的index门路对应节点存在，则以后查找节点来到index门路对应节点 node = node.nexts.get(index); } // 最初以后节点的pass值即是以pre为前缀的数量 return node.pass; } /** * 在前缀树中删除某个字符串 */ public void delete(String str) { // 字符串存在才执行删除逻辑 if (search(str) != 0) { // 从根节点开始 Node2 node = root; // 批改根节点pass值 node.pass--; int index = 0; char[] chars = str.toCharArray(); for (char aChar : chars) { // 以后字符应该走的门路 index = aChar; // 以后节点index门路对应节点的pass值减一 if (--node.nexts.get(index).pass == 0) { // 减一后如果为0，表明没有字符串再通过此节点 // 将此节点index门路对应节点置空 node.nexts.remove(index); return; } // 减一后不为0，表明还有字符串通过此节点 // 则以后节点挪动到index门路对应的节点 node = node.nexts.get(index); } // 最初批改节点所在位置end值 node.end--; } }}以上两种前缀树都只实现了最根本的性能，当理论我的项目中遇到相似的需要，能够在此基础上增加须要的性能即可，相当于提供了一个模板。
本文所有代码Github获取