字典树(前缀树)的实现（5）0423

字典树又称前缀树或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、从根节点开始搜索。

2、取得要查找单词的第二个字母，并根据该字母选择对应的字符路径向下继续搜索。

3、字符路径指向的第二层节点上，根据第二个字母选择对应的字符路径向下继续搜索。

4、一直向下搜索，如果单词搜索完后，找到的最后一个节点是一个终止节点，说明字典树中含有这个单词，如果找到的最后一个节点不是一个终止节点，说明单词不是字典树中添加过的单词。如果单词没搜索完，但是已经没有后续的节点了，也说明单词不是字典树中添加过的单词。

public class TrieNode{//有多少个单词公用此节点public int path;//表示有多少个单词以这个节点结尾public int end;//map 是一个哈希表结构，key代表该节点的一条字符路径，value表示字符路径指向的节点public int TrieNode[] map;public TrieNode(){path = 0 ;end = 0 ;map = new TrieNode[26];}
}

void insert(String word) 假设单词word的长度为N，从左到右遍历word中的每个字符，并依次从头节点开始根据每一个word[i]，找到下一个节点。如果找的过程中节点不存在，就建立新节点，记为a，并令a.path = 1。如果节点存在，记为b，令b.path++。通过最后一个字符（word[N-1]）找到最后一个节点时记为e，令e.path++，e.end++。

boolean search(String word) 从左到右遍历word中的每个字符，并依次从头节点开始根据每一个word[i]，找到下一个节点。如果找的过程中节点不存在，说明这个单词的整个部分没有添加进Trie树，否则不可能找的过程中节点不存在，直接返回false，如果能通过word[N-1]找到最后一个节点，记为e，如果e.end!=0，说明有单词通过word[N-1]的字符路径，并以节点e结尾，返回true，如果e.end==0,返回false。

void delete(String word) 先调用search(word)，看word再不在Trie树中，若在，则执行后面的过程，若不在，则直接返回，从左到右遍历word中的每个字符，并依次从头节点开始根据每一个word[i]找到下一个的节点，在找的过程中，把扫过每一个节点的path值减1。如果发现下一个节点的path值减完之后已经为0，直接从当前节点的map中删除后续的所有路径，返回即可。如果扫到最后一个节点，记为e，令e.path--，e.end--

int prefixNumber(String pre) 和查找操作同理，根据pre不断找到节点，假设最后的节点记为e，返回e.path的值即可。