import java.util.Arrays; class TrieNode { TrieNode[] arr; boolean isEnd; char val; public TrieNode() { this.arr = new TrieNode[26]; } public char getVal() { return val; } public void setVal(char val) { this.val = val; } @Override public String toString() { return "TrieNode [arr=" + Arrays.toString(arr) + ", isEnd=" + isEnd + ", val=" + val + "]"; } } public class Trie { private TrieNode root; public Trie() { root = new TrieNode(); } /** * 构造树节点 * @param word */ public void insert(String word) { TrieNode p = root; for (int i = 0; i < word.length(); i++) { char c = word.charAt(i); int index = c - 'a'; if (p.arr[index] == null) { TrieNode temp = new TrieNode(); temp.setVal(c); p.arr[index] = temp; p = temp; } else { p = p.arr[index]; } } p.isEnd = true; } public boolean search(String word) { TrieNode p = searchNode(word); if (p == null) { return false; } else { if (p.isEnd) return true; } return false; } public boolean startWith(String prefix) { TrieNode p = searchNode(prefix); if (p == null) { return false; } else { return true; } } public TrieNode searchNode(String s) { TrieNode p = root; for (int i = 0; i < s.length(); i++) { char c = s.charAt(i); int index = c - 'a'; if (p.arr[index] != null) { p = p.arr[index]; } else { return null; } } if (p == root) return null; return p; } public static void main(String[] args) { Trie trie = new Trie(); trie.insert("and"); trie.insert("hello"); trie.insert("world"); System.out.println(trie.startWith("he")); TrieNode node = trie.searchNode("h"); System.out.println(node); } }