Python数据结构与算法之字典树实现方法示例

本文实例讲述了Python数据结构与算法之字典树实现方法。分享给大家供大家参考，具体如下：

class TrieTree():
 def __init__(self):
 self.root = {}
 def addNode(self,str):
 # 树中每个结点(除根节点)，包含到该结点的单词数，以及该结点后面出现字母的键
 nowdict = self.root
 for i in range(len(str)):
 if str[i] not in nowdict: # 发现新的组合方式
 nowdict[str[i]] = {'count':0,'prefix':str[:i+1]}
 nowdict = nowdict[str[i]] # 转移到下一个结点
 nowdict['count'] += 1
 def countWord(self,str):
 # 返回输入单词在树中出现的次数
 nowdict = self.root
 for s in str:
 if s not in nowdict:
 return 0
 nowdict = nowdict[s] # 匹配当前结点,转下一个结点
 # 到了这一步证明单词存在
 return nowdict['count']
if __name__=="__main__":
 pass
 Text = ['b','abc','abd','bcd','abcd','efg','hii','bcd']
 t = TrieTree()
 for str in Text:
 t.addNode(str)
 print t.countWord('bcd')
>>> 2