在实现字典树（前缀树）之前，我们先看一下什么是字典树（前缀树）
“字典树又称前缀树，Trie树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。
它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。”------百度百科
字典树是一种树形结构，优点是利用字符串的公共前缀来节约存储空间。
字典树如图1所示：
图1
在字典树上搜索添加过的单词的步骤如下：
1、从根结点开始搜索
2、取得要查找单词的第一个字母，并根据该字母选择对应的字符路径向下继续搜索。
3、字符路径指向的第二层节点上，根据第二个字母选择对应的字符路径向下继续搜索。
4、一直向下搜索，如果单词搜索完后，找到的最后一个节点是一个终止节点，比如图1中的实心节点，说明字典树中含有这个单词，
如果找到的最后一个节点不是一个终止节点，说明单词不是字典树中添加过的单词。如果单词没搜索完，但是已经没有后续的节点了，
也说明单词不是字典树中添加过的单词。
题目：字典树（前缀树）的实现：
字典树又称为前缀树或Trie树，是处理字符串常见的数据结构。假设组成所有单词的字符串是“a”~“z”，请实现字典树结构，并包含以下四个主要功能。
void insert(String word)： 添加word，可以重复添加。
void delete(String word)：删除word，如果word添加过多次，仅删除一个。
boolean search(String word)：查询word是否在字典树中。
int prefixNumber(String pre)：返回以字符串pre为前缀的单词数量。
1 class TrieNode { 2 int path; 3 int end; 4 TrieNode[] map; 5 6 TrieNode() { 7 path=0; 8 end=0; 9 map=new TrieNode[26]; 10 } 11 } 12 class Trie { 13 private TrieNode root; 14 public Trie() { 15 root=new TrieNode(); 16 } 17 public void insert(String word) { 18 if (word==null) { 19 return; 20 } 21 char[] chs=word.toCharArray(); 22 TrieNode node=root; 23 node.path++; 24 int index=0; 25 for (int i=0; i<chs.length; i++) { 26 index=chs[i]-'a'; 27 if (node.map[index]==null) { 28 node.map[index]=new TrieNode(); 29 } 30 node=node.map[index]; 31 node.path++; 32 } 33 node.end++; 34 } 35 public void delete(String word) { 36 if (search(word)) { 37 char[] chs=word.toCharArray(); 38 TrieNode node=root; 39 node.path--; 40 int index=0; 41 for (int i=0; i<chs.length; i++) { 42 index=chs[i]-'a'; 43 node.map[index].path--; 44 node=node.map[index]; 45 } 46 node.end--; 47 } 48 } 49 public boolean search(String word) { 50 if (word==null) { 51 return false; 52 } 53 char[] chs=word.toCharArray(); 54 TrieNode node=root; 55 int index=0; 56 for (int i=0; i<chs.length; i++) { 57 index=chs[i]-'a'; 58 if (node.map[index]==null) { 59 return false; 60 } 61 node=node.map[index]; 62 } 63 return node.end!=0; 64 } 65 public int prefixNumber(String pre) { 66 if (pre==null) { 67 return 0; 68 } 69 char[] chs=pre.toCharArray(); 70 TrieNode node=root; 71 int index=0; 72 for (int i=0; i<chs.length; i++) { 73 index=chs[i]-'a'; 74 if (node.map[index]==null) { 75 return 0; 76 } 77 node=node.map[index]; 78 } 79 return node.path; 80 } 81 }
LeetCode208实现Trie（前缀树）
题目描述：
实现一个 Trie (前缀树)，包含 insert, search, 和 startsWith 这三个操作。
示例:
Trie trie = new Trie();
trie.insert("apple");
trie.search("apple"); // 返回 true
trie.search("app"); // 返回 false
trie.startsWith("app"); // 返回 true
trie.insert("app");
trie.search("app"); // 返回 true
说明:
你可以假设所有的输入都是由小写字母 a-z 构成的。
保证所有输入均为非空字符串。
1 class TrieNode { 2 int path; 3 int end; 4 TrieNode[] map; 5 6 TrieNode() { 7 path=0; 8 end=0; 9 map=new TrieNode[26]; 10 } 11 } 12 class Trie { 13 private TrieNode root; 14 public Trie() { 15 root=new TrieNode(); 16 } 17 public void insert(String word) { 18 if (word==null) { 19 return; 20 } 21 char[] chs=word.toCharArray(); 22 TrieNode node=root; 23 node.path++; 24 int index=0; 25 for (int i=0; i<chs.length; i++) { 26 index=chs[i]-'a'; 27 if (node.map[index]==null) { 28 node.map[index]=new TrieNode(); 29 } 30 node=node.map[index]; 31 node.path++; 32 } 33 node.end++; 34 } 35 public boolean search(String word) { 36 if (word==null) { 37 return false; 38 } 39 char[] chs=word.toCharArray(); 40 TrieNode node=root; 41 int index=0; 42 for (int i=0; i<chs.length; i++) { 43 index=chs[i]-'a'; 44 if (node.map[index]==null) { 45 return false; 46 } 47 node=node.map[index]; 48 } 49 return node.end!=0; 50 } 51 public boolean startsWith(String prefix) { 52 if (prefix==null) { 53 return false; 54 } 55 char[] chs=prefix.toCharArray(); 56 TrieNode node=root; 57 int index=0; 58 for (int i=0; i<chs.length; i++) { 59 index=chs[i]-'a'; 60 if (node.map[index]==null) { 61 return false; 62 } 63 node=node.map[index]; 64 } 65 return node.path!=0; 66 } 67 }
欢迎评论！！共同进步！！
（请问博客园中插入代码时“行内代码”选项是什么意思？？）