用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)

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

tr = Trie()

tr.insert('hallo', 54)

tr.insert('hello', 69)

tr.insert('hellas', 99)

当我现在打印Trie时，会出现以下问题：条目hello和hellas并不完全。

print tr

hallo | ellas | o 

我该如何解决这个问题？