【题目】
字典树又称为前缀树或者Trie树，是处理字符串常用的数据结构。假设组成所有单词的字符仅是‘a’～‘z’，请实现字典树的结构，并包含以下四个主要的功能。
void insert(String word)：添加word，可重复添加void delete(String word)：删除word，如果word添加过多次，仅删除一次boolean search(String word)：查询word是否在字典树中int prefixNumber(String pre)：返回以字符串pre作为前缀的单词数量【基本思路】
字典树介绍。字典树是一种树形结构，优点是利用字符串的公共前缀来节约存储空间。如图，是插入abc, abcd, abd, b, bcd, efg, hik后的字典树。 字典树的基本性质如下： 1.根节点没有字符路径。除根节点外，每一个节点都被一个字符路径找到。 2.从根节点到某一节点，将路径上经过的字符连接起来，为扫过的对应字符串。 3.每个节点向下所有的字符路径上的字符都不同。
下面介绍有关字典树节点的类型，首先定义节点类。
class TrieNode: def __init__(self): self.path = 0 self.end = 0 self.map = [None for i in range(26)]TrieNode类中，path表示有多少个单词共用这个节点，end表示有多少个单词以这个单词结尾，map是一个哈希表结构，key代表该节点的一条字符路径，value表示字符路径指向的节点，根据题目的说明，map是一个长度为26的数组（相当于一棵有26个孩子的树），在字符种类较多的时候可以使用真实的哈希表结构实现map。下面介绍Trie树类如何实现。
void insert(String word)：假设word的长度为N。从左到右遍历word中的每个字符，并依次从头节点开始根据每一个word[i]，找到下一个节点。如果该节点不存在就新建一个，记为a，令a.path = 1.如果节点存在，记为b，令b + 1。通过最后一个字符找到最后一个节点时记为e，令e.path + 1，e.end + 1
boolean search(String word)：从左到右遍历word中字符，并依次从头节点根据word[i]找到下一个节点。如果找的过程中节点不存在，直接返回False。如果能通过最后一个字符找到最后一个节点，并且该节点的end值不等于0，返回True。如果最后一个节点的end值为0，说明word只是一个前缀，返回False
void delete(String word)：先调用search函数看word在不在树中，如果不在，直接返回。否则，进入如下的操作。从左到右依次遍历word中的字符，并依次从头节点根据word[i]找到下一个节点。在找的过程中，把扫过的每个节点的path值减 1 。如果发现下一个path的值减完为0，直接从当前节点的map中删除后续的所有路径，返回即可。如果扫到最后一个节点。记为e，令e.path，e.end都减1
int prefixNumber(String pre)：和查找操作同理，根据pre不断找到节点，假设最后的节点记为e，返回e.path即可
下面是使用python3.5实现的代码。
class Trie: def __init__(self): self.root = TrieNode() def insert(self, word): if word == None: return node = self.root for i in word: index = ord(i) - ord('a') if node.map[index] == None: node.map[index] = TrieNode() node = node.map[index] node.path += 1 node.end += 1 print("Inset successful") def search(self, word): if word == None: return False node = self.root for i in word: index = ord(i) - ord('a') if node.map[index] == None: return False node = node.map[index] return True if node.end != 0 else False def delete(self, word): if self.search(word): node = self.root for i in word: index = ord(i) - ord('a') node.map[index].path -= 1 if node.map[index].path == 0: node.map[index] = None return node = node.map[index] node.end -= 1 def prefixNumber(self, pre): if pre == None: return node = self.root for i in pre: index = ord(i) - ord('a') if node.map[index] == None: return 0 node = node.map[index] return node.path