在Python中實現Trie

Question

我編寫了一個Trie作爲Python中的類。搜索和插入功能很明顯，但現在我試圖編程python函數__str__，我可以在屏幕上打印它。但我的功能不起作用！

class Trie(object): 
    def __init__(self): 
     self.children = {} 
     self.val = None 

    def __str__(self): 
     s = '' 
     if self.children == {}: return ' | ' 
     for i in self.children: 
     s = s + i + self.children[i].__str__() 
     return s 

    def insert(self, key, val): 
     if not key: 
     self.val = val 
     return 
     elif key[0] not in self.children: 
     self.children[key[0]] = Trie() 
     self.children[key[0]].insert(key[1:], val) 

現在，如果我創建特里結構的一個對象：

tr = Trie() 
tr.insert('hallo', 54) 
tr.insert('hello', 69) 
tr.insert('hellas', 99) 

當我現在打印特里，occures問題的條目打招呼，HELLAS不完全。

print tr 
hallo | ellas | o 

我該如何解決這個問題？

Answer 1

而不是你的打印目前的策略，我建議以下策略來代替：

保留所有字符的list爲了你迄今走過。當下降到你的一個孩子時，將其角色推到列表的末尾。返回時，將結束字符從列表中彈出。當您處於葉節點時，將該列表的內容作爲字符串打印。

所以說你有一個hello和hellas內建的trie。這意味着，當你下降到你好，你建立一個列表h，e，l，l，o，並在葉節點打印你好，返回一次得到（地獄），推a，s，並在下一葉你打印hellas。這樣，您可以在樹的早期重新打印信件，而不是無法記憶它們是什麼以及錯過它們。 （另一種可能是下降樹，並且每當你到達一個葉節點時，轉到你的父母，你父母的父母，你父母的父母的父母......等，跟蹤你遇到的字母，顛倒清單你製作和印刷了這一點，但它可能是低效率）

Answer 2

爲什麼不海峽其實倒出來，它被保存在格式的數據：。

def __str__(self): 
    if self.children == {}: 
     s = str(self.val) 
    else: 
     s = '{' 
     comma = False 
     for i in self.children: 
      if comma: 
       s = s + ',' 
      else: 
       comma = True 
      s = s + "'" + i + "':" + self.children[i].__str__() 
     s = s + '}' 
    return s 

導致：

{'h':{'a':{'l':{'l':{'o':54}}},'e':{'l':{'l':{'a':{'s':99},'o':69}}}}} 

Answer 3

您遇到了幾個問題。首先，如果你有幾個同級的孩子，你只能在其中一個字符串的前面加上前綴，然後只顯示其他的後綴。另一個問題是，即使您的終端值不在葉中（即使用"foo"和"foobar"作爲Trie的關鍵字也會發生什麼情況），您僅顯示葉節點。最後，你根本不輸出數值。

爲了解決第一個問題，我建議使用循環Trie的遞歸生成器。將遍歷從__str__中分離出來會使事情變得更容易，因爲發生器可以簡單地yield我們遇到的每個值，而不需要像我們去建立一個字符串。 __str__方法可以使用str.join輕鬆組裝最終結果。

對於第二個問題，只要self.val不是None，而不是僅在葉節點，您應該產生當前節點的密鑰和值。只要你沒有任何方法去除值，所有的葉節點都會有一個值，但我們實際上並不需要任何特殊的外殼來檢測它。

而對於最後一個問題，我建議使用字符串格式來創建一個key:value對。 （我想你可以跳過這個，如果你真的不需要值。）

下面是一些代碼：

def traverse(self, prefix=""): 
    if self.val is not None: 
     yield "{}:{}".format(prefix, self.val) 
    for letter, child in self.children.items(): 
     yield from child.traverse(prefix + letter) 

def __str__(self): 
    return " | ".join(self.traverse()) 

如果你使用一個版本的Python 3.3之前，你需要與外在的循環替換yield from語句從遞歸調用產生的項目：

for item in child.traverse(prefix + letter) 
    yield item 

輸出示例：

>>> t = Trie() 
>>> t.insert("foo", 5) 
>>> t.insert("bar", 10) 
>>> t.insert("foobar", 100) 
>>> str(t) 
'bar:10 | foo:5 | foobar:100' 

Answer 4

你可以用一個簡單的表示，只是提供什麼樣的結構包含一個總結去：

class Trie: 

    def __init__(self): 
     self.__final = False 
     self.__nodes = {} 

    def __repr__(self): 
     return 'Trie<len={}, final={}>'.format(len(self), self.__final) 

    def __getstate__(self): 
     return self.__final, self.__nodes 

    def __setstate__(self, state): 
     self.__final, self.__nodes = state 

    def __len__(self): 
     return len(self.__nodes) 

    def __bool__(self): 
     return self.__final 

    def __contains__(self, array): 
     try: 
      return self[array] 
     except KeyError: 
      return False 

    def __iter__(self): 
     yield self 
     for node in self.__nodes.values(): 
      yield from node 

    def __getitem__(self, array): 
     return self.__get(array, False) 

    def create(self, array): 
     self.__get(array, True).__final = True 

    def read(self): 
     yield from self.__read([]) 

    def update(self, array): 
     self[array].__final = True 

    def delete(self, array): 
     self[array].__final = False 

    def prune(self): 
     for key, value in tuple(self.__nodes.items()): 
      if not value.prune(): 
       del self.__nodes[key] 
     if not len(self): 
      self.delete([]) 
     return self 

    def __get(self, array, create): 
     if array: 
      head, *tail = array 
      if create and head not in self.__nodes: 
       self.__nodes[head] = Trie() 
      return self.__nodes[head].__get(tail, create) 
     return self 

    def __read(self, name): 
     if self.__final: 
      yield name 
     for key, value in self.__nodes.items(): 
      yield from value.__read(name + [key])