1

我在 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

我该如何解决这个问题？

4

4 回答 4

2

为什么不让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}}}}}
于 2013-06-05T07:14:03.237 回答
1

您遇到了几个问题。第一个是，如果您有多个处于同一级别的孩子，您只会在其中一个孩子前面加上字符串的初始部分，而只显示其他孩子的后缀。另一个问题是您只显示叶子节点，即使您可以拥有不在叶子上的终端值（考虑当您同时使用"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())

如果您使用的是 3.3 之前的 Python 版本，则需要将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'
于 2013-06-05T07:56:12.897 回答
1

您可以使用更简单的表示形式，仅提供结构所包含内容的摘要：

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])
于 2013-07-12T16:34:19.310 回答
0

我建议使用以下策略，而不是您当前的打印策略：

保留list所有字符中的一个，以便您到目前为止已遍历。当下降到您的一个孩子时，将其角色推到其列表的末尾。返回时，从列表中弹出结束字符。当您位于叶节点时，将列表的内容打印为字符串。

因此，假设您有一个由helloand构建的 trie hellas。这意味着当你下降到 hello 时，你会构建一个列表 h、e、l、l、o，然后在叶节点上打印 hello，返回一次以获取（地狱），推送 a，s 并在下一个叶节点上打印地狱。这样，您可以在树中更早地重新打印字母，而不是不记得它们是什么而错过了它们。

（另一种可能性是只下降树，每当你到达叶节点时，去你的父母，你父母的父母，你父母的父母的父母......等等，跟踪你遇到的字母，反转你制作的列表并打印那个。但它可能效率较低。）

于 2013-06-05T06:35:23.510 回答