本文實(shí)例講述了Python實(shí)現(xiàn)簡(jiǎn)單字典樹的方法。分享給大家供大家參考，具體如下：
#coding=utf8"""代碼實(shí)現(xiàn)了最簡(jiǎn)單的字典樹，只支持由小寫字母組成的字符串。在此代碼基礎(chǔ)上擴(kuò)展一下，就可以實(shí)現(xiàn)比較復(fù)雜的字典樹，比如帶統(tǒng)計(jì)數(shù)的，或支持更多字符的字典樹，或者是支持刪除等操作。"""class TrieNode(object): def __init__(self): # 是否構(gòu)成一個(gè)完成的單詞 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')
