#coding=utf8 """代码实现了最简单的字典树，只支持由小写字母组成的字符串。 在此代码基础上扩展一下，就可以实现比较复杂的字典树，比如带统计数的，或支持更多字符的字典树， 或者是支持删除等操作。 """ class trienode(object): def __init__(self): # 是否构成一个完成的单词 self.is_word = false self.children = [none] * 26 class 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 false if __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')
更多python实现简单字典树的方法介绍。