python - 使用python搜索n叉树的函数

Question

我正在尝试为 n 叉树构建一个搜索函数。节点类是这样的:

class node(object):
  """docstring for node"""
  def __init__(self, val=''):
    self.val = val #value of the node
    self.subtrees = [] #list of subtree node objects

以下是调用搜索函数的代码:

temp_search(root, "1")

并且有一个节点的值为“1”。我希望在成功搜索时返回节点对象。

以下是我实现的第一个搜索功能:

#temp_search v0.1
def temp_search(node, key):
    if node.val == key:
        print 'Found', node
        return node
    for subtree in node.subtrees:         
        return temp_search(subtree, key)

上面的东西返回'None'并且它从未打印'Found'

现在我稍微修改了一下:

#temp_search v0.2
def temp_search(node, key):
    if node.val == key:
        print 'found', node
        return node
    for subtree in node.subtrees:         
        temp_search(subtree, key)  

虽然它返回“None”，但它仍然打印“Found”。好的，这是一些改进。

所以我意识到循环在每个子树对象上运行，即使在它返回节点之后也是如此。这有任何意义吗？因为我认为一旦它返回了一些东西，它就应该从中出来，对吧？于是再次修改:

#temp_search v0.3
def temp_search(node, key):
    if node.val == key:
        print 'Found', node
        return node       
    for subtree in node.subtrees:         
        temp = temp_search(subtree, key)
        if temp:
            return temp

类似地，我实现了这样的多重搜索 [即它应该返回值与键匹配的所有节点]

#temp_multi_search v0.1
def temp_multi_search(some_node, key, result=[]):
    if some_node.val == key:
        print 'found', some_node
        return result.append(some_node)
    for subtree in some_node.subtrees:         
        temp = temp_multi_search(subtree, key, result)
        if temp:
            result.append(temp)
    return result

我会这样调用上面的函数:

temp_multi_search(root, "1")

但我得到的结果是:

[<__main__.node object at 0x101eb4610>, [...], [...], [...], [...], [...], [...], [...], <__main__.node object at 0x101eb47d0>, [...], [...], [...], [...]]

所以它是附加空列表(？)。我就是这样修复它的:

#temp_multi_search v0.2
def temp_multi_search(some_node, key, result=[]):
    #result = []
    if some_node.val == key:
        print 'found', some_node
        return result.append(some_node)
    for subtree in some_node.subtrees:         
        temp = temp_multi_search(subtree, key, result)
        if isinstance(temp, node):
             result.append(temp)
    return result

现在我会得到正确的预期结果:

[<__main__.node object at 0x10b697610>, <__main__.node object at 0x10b6977d0>]

这是我的问题:

1. 为什么 temp_search v0.1 失败了？当遍历每个子树，找到搜索结果时，返回值。为什么循环没有终止？
2. 在 temp_search v0.2 中，for 循环中没有 return 语句。那么它在这里有什么不同呢？既然找到了对象，那么如何返回成功呢？
3. 我是否以正确的方式实现了 temp_search v0.3？有什么改进吗？
4. 为什么 temp_multi_search v0.1 失败了？
5. 我是否以正确的方式实现了 temp_multi_search v0.2？有什么改进吗？

这是我的想法:

1. 我认为 for 循环只运行一次。它仅在第一个子树中搜索(递归)，如果项目不存在则返回 none。我通过发送第一个子树中存在的值来确认这一点
2. 此处 for 循环在每个子树上成功运行，这就是它能够找到节点的原因。但是我如何让它返回 temp_search v0.3 以外的节点？我发现 temp_search v0.3 少了 pythonic
3. -
4. 我认为它失败了，因为返回的温度是一些列表，所以它只是将它附加到结果。
5. -

Answer 1

1. 你的回答是正确的。由于对第一个子树的函数调用总是返回(无论是否找到值)，它不会检查下一个子树。
2. 您没有 return 语句，因此在函数末尾 Python 将隐式插入 return None
3. 这已经是最优的了。没有一个 Python 语句可以做到这一点。
4. 添加列表(不是空列表!)是因为您执行了return result，因此父函数调用将收到一个(结果)列表作为结果。然后它将追加到 result 的本地副本，并返回。
5. 您可以通过不将 result 作为参数来改进它:

#temp_multi_search v0.25
def temp_multi_search(some_node, key):
    result = []                    # Line 1
    if some_node.val == key:
        print 'found', some_node
        result.append(some_node)   # Line 2
    for subtree in some_node.subtrees:         
        result.extend(temp_multi_search(subtree, key)) # Line 3
    return result

解释:

它将首先检查根节点上的值，如果不匹配，我们不会将该节点附加到搜索结果中，否则，我们将其添加到目前的结果中(它只会包含它自己) .接下来我们检查每个子树。

现在，我们已经知道函数 temp_multi_search(subtree, key) 将返回该树上的所有出现。因此，在我们对每个子树调用 temp_multi_search(subtree, key) 之后，我们将在该子树中找到的结果扩展到我们目前的结果(可能包含之前的结果) child )。

在迭代所有子项结束时，我们返回结果。

例子:

假设我们要在下面的树中查找数字 1，并期望该函数返回所有出现的地方。

          0   _______|________   |      |       |   1      2       3  _|_    _|_   ___|___  | |    | |   |  |  |  1 4    1 5   6  1  7

所以我们首先调用 temp_multi_search(root,1)。它不是 1，所以 result 现在仍然是空的。

接下来我们检查每个子树:

1. child 1:节点值匹配，因此我们将其添加到结果中(在第 2 行)。现在假设我们有 result = [node1]。然后检查每个子树:
   • GrandChild 1:节点值匹配，因此我们将其添加到结果中(在第 2 行)。没有更多的子树。返回 [node2]。 Child 1 调用会将结果 [node2] 扩展到他的结果 [node1](第 3 行)。所以 Child 1 现在有 [node1, node2]。
   • 孙子 2:节点值不匹配。没有更多的子树。返回 []。 child 1 扩展了空列表，所以没有变化。
2. child 2:不匹配。检查每个子树:
   • 孙子 3:比赛。添加到结果(第 2 行)。没有更多的子树。返回 [node5]。 child 2 成为 [node5](第 3 行)。
   • 孙子 4:不匹配。没有更多的子树。返回 []。 child 2 仍然是 [node5]。
3. child 3:不匹配。检查每个子树:
   • 孙子 5:不匹配。没有更多的子树。返回[]
   • 孙子 6:匹配添加到结果(第 2 行)。返回 [node9]。 child 3 将其扩展为 [node9](第 3 行)
   • 孙子 7:不匹配。没有更多的子树。返回 [].

在上述每个步骤结束时，返回的结果将由第 3 行扩展为 Root 结果。因此在步骤 1 之后，Root 结果为 [node1, node2]。在第 2 步之后，Root 结果为 [node1, node2, node5]。第 3 步之后，Root 结果为 [node1, node2, node5, node9]。

然后检查完​​所有 child 后，返回结果。