Python小练习（008）：字典树基础篇（查找关键字）

jerryxjr1220

昨天介绍了字典树的创建，传送门
今天继续学习用字典树查找关键词。

其实，查找关键词相对还是比较简单的。原理就是按关键词的每个字母依次到字典树中查找，如果有就进下一级，没有就中止搜索，返回'未找到'。若每个字母都找到了，那么在最后返回'找到'。再进入下一个查找循环。

请利用上一个小练习的题目，继续编写搜索函数。

xinshouxuexi

学习了！

jerryxjr1220

解答

1. def findtree(lst,tree):
   
2.     for word in lst:
   
3.         node = tree
   
4.         for w in word:
   
5.             node = node.get(w,None)
   
6.             if node == None:
   
7.                 print word + ' not found!'
   
8.                 break
   
9.         try:
   
10.             node=node.get('/',0)
    
11.             if node == None:
    
12.                 print word + ' found!'
    
13.             else:
    
14.                 print word + ' not found!'
    
15.         except:
    
16.             pass

复制代码

jerryxjr1220

其实，为了方便使用，我们可以把字典树的创建和查找做成一个类。这样调用的时候就非常方便了。
完整代码如下：

1. #coding=utf-8  
   
2. class Trie:  
   
3.     root = {}  
   
4.     END = '/'  
   
5.     def add(self, word):  
   
6.         #从根节点遍历单词,char by char,如果不存在则新增,最后加上一个单词结束标志  
   
7.         node = self.root  
   
8.         for c in word:  
   
9.             node=node.setdefault(c,{})  
   
10.         node[self.END] = None
    
11.                
    
12.     def find(self, word):  
    
13.         node = self.root  
    
14.         for c in word:  
    
15.             if c not in node:  
    
16.                 return False  
    
17.             node = node[c]  
    
18.         return self.END in node

复制代码

调用创建字典树：

1. tree = Trie()
   
2. List = ["A", "to", "tea", "ted", "ten", "i", "in", "inn"]
   
3. for s in List:
   
4.         tree.add(s)
   
5. print tree.root

复制代码

在字典树中查找：

1. print tree.find('ted')

复制代码

jerryxjr1220

更新完毕。
在下一次的《字典树提高篇》中会给大家分享如何应用字典树做到“输入单词的前缀马上能显示完整的单词”，其实IDLE的提示功能就是运用的类似原理。