无法在Python的Trie中打印节点

Question

大家好，

我在这里有两个疑问。

疑问1：-

我很难理解Trie中的插入功能。

这是插入词功能。

def add(self, word):
    cur = self.head
    for ch in word:
        if ch not in cur:
            cur[ch] = {}
        cur = cur[ch]
    # * denotes the Trie has this word as item
    # if * doesn't exist, Trie doesn't have this word but as a path to longer word
    cur['*'] = True

为什么在if语句后启动一个空字典？

以及“ cur = cur [ch]”的意义是什么。

请帮助我理解代码中if语句中的那些行。

疑问2：-我正在尝试打印Trie内部存在的所有节点，但是它正在打印为“ <__ main __>”这样的对象。有人可以帮我打印特里树的节点。下面是代码。

class Trie:
    head = {}

    def add(self, word):
        cur = self.head
        for ch in word:
            if ch not in cur:
                cur[ch] = {}
            cur = cur[ch]
        # * denotes the Trie has this word as item
        # if * doesn't exist, Trie doesn't have this word but as a path to longer word
        cur['*'] = True

    def search(self, word):
        cur = self.head
        for ch in word:
            if ch not in cur:
                return False
            cur = cur[ch]

        if '*' in cur:
            return True
        else:
            return False
dictionary = Trie()
dictionary.add("hi")
dictionary.add("hello")
print((dictionary)) # <__main__.Trie object at 0x7f655de1c9e8>

Answer 1

疑问1

最初，您有一个普通的旧空字典head = {}。您的第一个单词是"cat"。因此，您获得了对head的引用，称为cur。对cur所做的更改将反映在head上。我们需要在空字典中添加一个ch = "c"键作为我们的"cat"的首字母，但不幸的是，该键不存在。因此，我们创建了它。head/ cur现在看起来像：

head = {"c": {}}
cur = head

然后，执行行cur = cur[ch]。 ch是"c"，因此与cur = cur["c"]相同。 cur刚刚向下移动了特里，然后将for循环到下一个字符"a"。我们回到相同的场景：cur = {}，我们需要添加"a"键，所以我们这样做：

head = {"c": {"a": {}}}
cur = head["c"]

cur = cur["a"]运行，并且下一次迭代重复相同的事情：

head = {"c": {"a": {"t": {}}}}
cur = head["c"]["a"]

最后，循环结束，我们设置标志字符"*"，然后添加"cat"。我们的结果是：

head = {"c": {"a": {"t": {}, "*": True}}}

现在，我们叫trie.add("cart")。我只显示更新：

head = {"c": {"a": {"t": {}, "*": True}}}
cur = head

head = {"c": {"a": {"t": {}, "*": True}}}
cur = head["c"]

head = {"c": {"a": {"t": {}, "*": True}}}
cur = head["c"]["a"]

head = {
    "c": {
        "a": {
            "r": {},
            "t": {}, 
            "*": True
        }
    }
}
cur = head["c"]["a"]["r"]

head = {
    "c": {
        "a": {
            "r": {
                "t": {}
            }
            "t": {}, 
            "*": True
        }
    }
}
cur = head["c"]["a"]["r"]["t"]

最后：

head = {
    "c": {
        "a": {
            "r": {
                "t": {},
                "*": True
            }
            "t": {}, 
            "*": True
        }
    }
}

希望这很有道理。

疑问2

[打印对象时，print尝试调用对象的魔术__str__方法。如果不存在，它将继承默认值__str__，该值仅打印对象的内存位置。这对于快速比较对象引用很有用，但是如果要显示对象的数据，则需要实现它。可能最简单的方法是将head字典转储为字符串：

import json

class Trie:
    def __str__(self):
        return json.dumps(self.head, sort_keys=True, indent=4)

Answer 2

1）if语句将检查给定字符在当前深度是否还没有自己的字典，然后它将创建一个空字典。 cur = cur[ch]会将cur的深度增加1，以试图找到放置word

的位置

2）要显示Trie的内容，请在Trie中添加__ str__方法。

例如：

def __str__(self):
    #code