單詞查找樹Trie樹，是一種樹形結(jié)構(gòu)，是一種哈希樹的變種。典型應(yīng)用是用于統(tǒng)計，排序和保存大量的字符串（但不僅限于字符串），所以經(jīng)常被搜索引擎系統(tǒng)用于文本詞頻統(tǒng)計。

python函數(shù)引用傳遞
列表、字典、集合:按引用傳入函數(shù)

def change(mylist):mylist[0:2]=[2,3]mylist = [11,22,33,44] print() change(mylist) print(mylist)

[2, 3, 33, 44]

#node:[計數(shù)，子樹] def refreshTrieNode(prevChar,nextChar,nowNode,isEndChar):if prevChar in nowNode.keys() and (not nowNode[prevChar][1] is None):if nextChar in nowNode[prevChar][1].keys():if isEndChar:nowNode[prevChar][1][nextChar][0]+=1newNode=nowNode[prevChar][1]else: if isEndChar:newNodeData=[1,None]else:newNodeData=[0,None] nowNode[prevChar][1][nextChar]=newNodeDatanewNode=nowNode else:if isEndChar:newNode={nextChar:[1,None]}else:newNode={nextChar:[0,None]} nowNode[prevChar][1]=newNode return newNode,nextChar def searchTrieNode(prevChar,nextChar,nowNode,isEndChar):if (not nowNode is None) and prevChar in nowNode.keys():newNode=nowNode[prevChar][1]if not newNode is None:if nextChar in newNode.keys():if isEndChar: if newNode[nextChar][0]>0:return newNode,nextChar,False,True,newNode[nextChar][0]#,,continue,findedelse: return newNode,nextChar,True,False,None#,,continue,findedreturn None,None,False,False,None#,,continue,finded #code:劉興,https://blog.csdn.net/AI_LX def test():words=["ab","ab","ad","adcd","add"]print(words)rootNode={"ROOT":[0,None]}for word in words:node=rootNodeprevChar="ROOT"for i in range(len(word)):if i==len(word)-1:isEndChar=Trueelse:isEndChar=Falsechar=word[i]node,prevChar=refreshTrieNode(prevChar,char,node,isEndChar)print("===")print(rootNode)print("---")words=["aa","ab","addd","abc","ad","adcd"]for word in words:node=rootNodeprevChar="ROOT"for i in range(len(word)):if i==len(word)-1:isEndChar=Trueelse:isEndChar=Falsechar=word[i]node,prevChar,isContinue,isFind,wc=searchTrieNode(prevChar,char,node,isEndChar)if not isContinue:if isFind:print(f"找到{word}，共有{wc}個。")else:print(f"找不到{word}")break test() ['ab', 'ab', 'ad', 'adcd', 'add'] === {'ROOT': [0, {'a': [0, {'b': [2, None], 'd': [1, {'c': [0, {'d': [1, None]}], 'd': [1, None]}]}]}]} --- 找不到aa 找到ab，共有2個。 找不到addd 找不到abc 找到ad，共有1個。 找到adcd，共有1個。

總結(jié)

以上是生活随笔為你收集整理的python3精要(5)-最长公共前缀Trie树的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。