我正在尝试为 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>]
这是我的问题:
- 为什么 temp_search v0.1 失败了?当遍历每个子树,找到搜索结果时,返回值。为什么循环没有终止?
- 在 temp_search v0.2 中,for 循环中没有 return 语句。那么它在这里有什么不同呢?既然找到了对象,那么如何返回成功呢?
- 我是否以正确的方式实现了 temp_search v0.3?有什么改进吗?
- 为什么 temp_multi_search v0.1 失败了?
- 我是否以正确的方式实现了 temp_multi_search v0.2?有什么改进吗?
这是我的想法:
- 我认为 for 循环只运行一次。它仅在第一个子树中搜索(递归),如果项目不存在则返回 none。我通过发送第一个子树中存在的值来确认这一点
- 此处 for 循环在每个子树上成功运行,这就是它能够找到节点的原因。但是我如何让它返回 temp_search v0.3 以外的节点?我发现 temp_search v0.3 少了 pythonic
- -
- 我认为它失败了,因为返回的温度是一些列表,所以它只是将它附加到结果。
- -
请您参考如下方法:
- 你的回答是正确的。由于对第一个子树的函数调用总是返回(无论是否找到值),它不会检查下一个子树。
- 您没有 return 语句,因此在函数末尾 Python 将隐式插入
return None - 这已经是最优的了。没有一个 Python 语句可以做到这一点。
- 添加列表(不是空列表!)是因为您执行了
return result,因此父函数调用将收到一个(结果)列表作为结果。然后它将追加到result的本地副本,并返回。 - 您可以通过不将
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 现在仍然是空的。
接下来我们检查每个子树:
- child 1:节点值匹配,因此我们将其添加到结果中(在第 2 行)。现在假设我们有
result = [node1]。然后检查每个子树:- GrandChild 1:节点值匹配,因此我们将其添加到结果中(在第 2 行)。没有更多的子树。返回
[node2]。 Child 1 调用会将结果[node2]扩展到他的结果[node1](第 3 行)。所以 Child 1 现在有[node1, node2]。 - 孙子 2:节点值不匹配。没有更多的子树。返回 []。 child 1 扩展了空列表,所以没有变化。
- GrandChild 1:节点值匹配,因此我们将其添加到结果中(在第 2 行)。没有更多的子树。返回
- child 2:不匹配。检查每个子树:
- 孙子 3:比赛。添加到结果(第 2 行)。没有更多的子树。返回
[node5]。 child 2 成为[node5](第 3 行)。 - 孙子 4:不匹配。没有更多的子树。返回 []。 child 2 仍然是
[node5]。
- 孙子 3:比赛。添加到结果(第 2 行)。没有更多的子树。返回
- 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 后,返回结果。
