python - 在 Python 中实现 Trie

Question

我用 Python 编写了一个 Trie 作为一个类。搜索和插入功能很清楚，但现在我尝试编写 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)

现在如果我创建一个 Trie 对象:

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

当我现在打印 Trie 时，出现了条目 hello 和 hellas 不完整的问题。

print tr
hallo | ellas | o 

我该如何解决这个问题？

Answer 1

为什么不让 str 实际上以存储的格式转储数据:

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}}}}}