【題目】

　字典樹又稱為前綴樹或者Trie樹，是處理字符串常用的數據結構。假設組成所有單詞的字符僅是‘a’～‘z’，請實現字典樹的結構，并包含以下四個主要的功能。

void insert(String word)：添加word，可重復添加
void delete(String word)：刪除word，如果word添加過多次，僅刪除一次
boolean search(String word)：查詢word是否在字典樹中
int prefixNumber(String pre)：返回以字符串pre作為前綴的單詞數量

Trie類中，path表示有多少個單詞共用這個節點，end表示有多少個單詞以這個單詞結尾，map是一個哈希表結構，key代表該節點的一條字符路徑，value表示字符路徑指向的節點，根據題目的說明，map是一個長度為26的數組（相當于一棵有26個孩子的樹），在字符種類較多的時候可以使用真實的哈希表結構實現map。下面介紹Trie樹類如何實現。

void insert(String word)：假設word的長度為N。從左到右遍歷word中的每個字符，并依次從頭節點開始根據每一個word[i]，找到下一個節點。如果該節點不存在就新建一個，記為a，令a.path = 1.如果節點存在，記為b，令b + 1。通過最后一個字符找到最后一個節點時記為e，令e.path + 1，e.end + 1

boolean search(String word)：從左到右遍歷word中字符，并依次從頭節點根據word[i]找到下一個節點。如果找的過程中節點不存在，直接返回False。如果能通過最后一個字符找到最后一個節點，并且該節點的end值不等于0，返回True。如果最后一個節點的end值為0，說明word只是一個前綴，返回False

void delete(String word)：先調用search函數看word在不在樹中，如果不在，直接返回。否則，進入如下的操作。從左到右依次遍歷word中的字符，并依次從頭節點根據word[i]找到下一個節點。在找的過程中，把掃過的每個節點的path值減 1 。如果發現下一個path的值減完為0，直接從當前節點的map中刪除后續的所有路徑，返回即可。如果掃到最后一個節點。記為e，令e.path，e.end都減1

int prefixNumber(String pre)：和查找操作同理，根據pre不斷找到節點，假設最后的節點記為e，返回e.path即可

class trie:def __init__(self):"""path: 表示有多少個單詞共用這個節點end: 表示有多少個單詞以這個節點結尾map: key 表示節點一條路徑，value表示字符路徑指向的節點"""self.path = 0self.end = 0self.map = [None for i in range(26)]class Trie:def __init__(self):self.root = trie()def inset(self,word):if word == None:return node = self.rootfor i in word:index = ord(i) - ord('a')if node.map[index] == None:node.map[index] = trie()node = node.map[index]node.path +=1node.end +=1def search(self,word):if word == None:returnnode = self.rootfor i in word:index = ord(i) - ord('a')if node.map[index] == None:return Falsenode = node.map[index]if node.end!=0:return Trueelse:return Falsedef delete(self,word):if self.search(word):node = self.rootfor i in word:index = ord(i) - ord('a')node.map[index].path -=1if node.map[index].path == 0:node.map[index] = Nonereturn node = node.map[index]self.end -=1def prefixNumber(self,pre):if pre == None:return node = self.rootfor i in pre:index = ord(i) - ord('a')if node.map[index] == None:return 0node = node.map[index]return node.path

?

總結

以上是生活随笔為你收集整理的字典数(前缀树)的实现的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。