实现类：

public class Trie {private class TrieNode {//元素的序号int level;//子节点信息TrieNode[] children = new TrieNode[26];//是否是最后一个节点public boolean isLast;//出现的频率public int fre = 1;}TrieNode root;public Trie() {root = new TrieNode();}public void insert(String str) {char[] chars = str.toCharArray();TrieNode p = root;//遍历单词的每个字符for (int i = 0; i < chars.length; ++i) {char c = chars[i];TrieNode child = p.children[c - 'a'];if (child == null) {TrieNode node = new TrieNode();node.level = i;p.children[c - 'a'] = node;p = node;} else {p = child;++child.fre;}}p.isLast = true;}//输出以prefix为前缀的所有后缀public void print(String prefix, TrieNode p) {if (p.isLast && prefix.length() > 0) {System.out.println(prefix);}for (int i = 0; i < 26; ++i) {if (p.children[i] != null) {print(prefix + (char) ('a' + i), p.children[i]);}}}//查找以prefix为前缀的所有后缀public void search(String prefix) {char[] chars = prefix.toCharArray();TrieNode p = root;for (int i = 0; i < chars.length; ++i) {char c = chars[i];TrieNode child = p.children[c - 'a'];if (child == null) {return;} else {p = child;}}print("", p);}
}

 

测试类：

import org.junit.Before;
import org.junit.Test;public class TrieTest {Trie trie = new Trie();@Beforepublic void insert() {trie.insert("hit");trie.insert("hat");trie.insert("had");trie.insert("have");trie.insert("hate");}@Testpublic void print() {trie.print("", trie.root);}@Testpublic void search() {trie.search("ha");}
}

执行public void print() {trie.print("", trie.root);}

执行public void search() {trie.search(“ha”);}