代码如下：
def longestCommonPrefix(str1,str2): #求最长公共子序列 i = 0; while (i < len(str1) and i < len(str2) and (str1[i] == str2[i])): i = i + 1; return (str1[0:i],str1[i:],str2[i:]); #返回str1和str2的相同前缀，str1的后缀，str2的后缀 class Trie: def __init__(self,value = None): #Trie树的定义 self.value = value; self.children = dict(); class PatriciaCharTrie(Trie): #PatriciaCharTrie的定义，继承Trie def __init__(self): self.root = None; def insert(self,key,value): #插入函数 if self.root is None: self.root = Trie(); p = self.root; while True: match = False; for k,node in p.children.items(): if key == k: node.value = value; return node; (prefix,remainK,remainKey) = longestCommonPrefix(k,key); #print 'prefix: ',prefix,',key:',key; if prefix != "": #若前缀不为空 match = True; if remainK != "": #若k的剩余后缀不为空, if remainKey == "": p.children[prefix] = Trie(value); prefixNode = p.children[prefix]; else: p.children[prefix] = Trie(); prefixNode = p.children[prefix]; prefixNode.children[remainKey] = Trie(value); prefixNode.children[remainK] = node; del p.children[k]; return ; else: p = node; key = remainKey; break; if not match: p.children[key] = Trie(value); return ; return; def search(self,searchKey): #查找searchKey是否在该PatriciaCharTrie中，若是则返回指向该searchKey的节点，否则返回None p = self.root; while True: match = False; for key,node in p.children.items(): if key == searchKey: return node; else: (prefix,remainKey,remainSearchKey) = longestCommonPrefix(key,searchKey); if prefix != "" and remainKey == "": match = True; p = node; searchKey = remainSearchKey; break; if (not match): return None; def lookUp(self,searchKey): #电子词典的补齐函数 searchNode = self.search(searchKey); #找到指向该searchKey的节点 self.look(searchNode); def look(self,searchNode): if searchNode is not None: for key,node in searchNode.children.items(): if node.children: #若node的children不为空dict，则递归查询searchNode的下一个节点node self.look(node); if node.value is not None: #若node.value不为None,打印该node的值 print node.value; else: if node.value is not None: print node.value; else: print 'in else node is None: '; if __name__ == '__main__': trie = PatriciaCharTrie(); str = ['a','ab','abc','able','abs', 'baby','back','bad','bag','balance' ,'ball','band','between']; for i in range(len(str)): trie.insert(str[i],str[i]); while True: word = raw_input('enter a word: '); trie.lookUp(word);运行结果：
转载于:https://www.cnblogs.com/lxpzh/p/6673785.html
