Python实现简单字典树的方法

#coding=utf8"""代码实现了最简单的字典树，只支持由小写字母组成的字符串。在此代码基础上扩展一下，就可以实现比较复杂的字典树，比如带统计数的，或支持更多字符的字典树，或者是支持删除等操作。"""class TrieNode(object):  def __init__(self):    # 是否构成一个完成的单词    self.is_word = False    self.children = [None] * 26class Trie(object):  def __init__(self):    self.root = TrieNode()  def add(self, s):    """Add a string to this trie."""    p = self.root    n = len(s)    for i in range(n):      if p.children[ord(s[i]) - ord('a')] is None:        new_node = TrieNode()        if i == n - 1:          new_node.is_word = True        p.children[ord(s[i]) - ord('a')] = new_node        p = new_node      else:        p = p.children[ord(s[i]) - ord('a')]        if i == n - 1:          p.is_word = True          return  def search(self, s):    """Judge whether s is in this trie."""    p = self.root    for c in s:      p = p.children[ord(c) - ord('a')]      if p is None:        return False    if p.is_word:      return True    else:      return Falseif __name__ == '__main__':  trie = Trie()  trie.add('str')  trie.add('acb')  trie.add('acblde')  print trie.search('acb')  print trie.search('ac')  trie.add('ac')  print trie.search('ac')