嵌套字典访问和值 Return

Question

我有许多嵌套字典，其中键是一个字符，即：“D”，值是对包含另一个字典的对象的引用。

EX:

对于单词“DAD”、“BAD”、“DADDY”：

          B|D
         /  \
       A     A
      /       \
     D         D
    /          /\
   *          *  D
                  \
                   Y
                    \
                     *

If we are accessing "BAD"
    self.child = { B : ref to object, D : ref to object}
    self.child.get("B").child = { A : ref to object }
    self.child.get("B").child.get("A").child = { D : {}}

我正在尝试访问树并打印树中的所有单词，或者是完整的树，或者只是与输入字符匹配的部分。即：如果我输入“B”我想要“BAD”，如果我输入“D”我想要“DAD”，“DADDY”

现在下面的代码并没有像预期的那样return，如果输入“D”，“DAD”和“DY”是returned。

自值在 class 中较早初始化。

def traverseTree(self, dictionary, baseValue):
    for key, value in dictionary.items():
        if isinstance(value.child, dict):
            if not value.leaf:
                self.accum += key
            else:
                self.l.append(baseValue + (self.accum + key)
                self.accum = ''
            self.traverseTree(value.child, baseValue)

我怀疑“DADDY”(DAD) 的第一块被切掉了，因为它们的值没有被推入累加器。我相信通过这种递归算法我正在访问每个节点，因为我到达了终点，但是递归访问和存储所有单词值的最佳实践是什么？

MRE:


class Trie:
    def __init__(self):
        self.dict = {}
        self.terminate = False

    def insert(self, word):
        if len(word) == 0:
            self.terminate = True
        else:
            if word[0] in self.dict:
                self.dict[word[0]].insert(word[1:])
            else:
                self.dict[word[0]] = Trie()
                self.dict[word[0]].insert(word[1:])

    def terminal(self):
        if self.terminate:
            return True

    def autoSearch(self, toSearch):
        if toSearch == '':
            return self.traverseTreeTest()

    def traverseTreeTest(self):
        if self.terminate:
            return [""]
        returnval = []
        for key, children in self.dict.items():
            returnval.extend([key + rest for rest in children.traverseTreeTest()])
        return returnval

word = ["D","DAD", "B", "BAD", "DADDY", "Lad"]
x = Trie()
for y in word:
    x.insert(y)
print(x.autoSearch(''))

Answer 1

我认为问题在于您在每个级别更新 self.l 和 self.accum，这会修改嵌套对象，因此您无法在顶层获得完整结果对象。

这里的版本只是 return 将所有内容都作为列表，而不是修改对象。

def traverseTree(self):
    if self.leaf:
        return [""]

    returnval = []
    for key, value in self.child.items():
        returnval.extend([key + rest for rest in value.traverseTree()])
    return returnval

这是基本的递归。所有情况 return 一个字符串列表。基本情况是一片叶子，它 return 是一个只有一个空字符串的列表。

递归 case 遍历字典，将键作为递归到子项的结果的前缀，并return生成所有这些字符串的列表。

嵌套字典访问和值 Return

Nested Dictionary Access and value Return

python

python-3.x

dictionary

trie