python-3.x - 在python中使用递归查找通用树中的节点
问题描述
我想使用递归在通用树中找到一个节点,但我似乎无法让它工作。我将它作为类中的一个方法,并且只发布该方法。我使用的是 python 3.Any帮助将不胜感激
def search_tree2(self, node):
if self.name == node.name:
return self
elif self.child_nodes:
result = None
for child in self.child_nodes:
if child.name == node.name:
result = child
elif child.child_nodes:
result = child.search_tree2(child)
if result.child_nodes:
for kid in result.child_nodes:
if kid.name == node.name:
result = kid
return result
else:
return None
编辑:使用 Neel Mehta 的更新方法添加了其余代码。为了清楚起见,我要做的是通过搜索节点在树中的任何节点处向树中添加一个节点,然后添加新的node.Also我在手机上,所以粘贴代码有点困难;这就是为什么我最初只发布了代码片段。
class Tree:
def __init__(self, value=None, name=None, parent=None):
self.value = value
self.name = name
self.parent = parent
self.child_nodes = []
def add_node(self, value=None, name=None, parent=None):
node = Tree(value, name, parent)
if node.parent.name == 'root':
self.child_nodes.append(node)
else:
parent_node = self.search_tree2(node.parent)
if parent_node:
parent_node.child_nodes.append(node)
print(node.name, 'added..')
else:
print('Parent Node not found.')
return node
def print_tree(self, node):
if node.name:
if node.name == 'root':
pass
else:
print(node.name.title() + ', ', 'age ', str(node.value) + ', ' if node.value else 'unknown' + ', ',
'with parent ', node.parent.name, ' and ',
*[node.child_nodes[i].name + ' ' for i in range(len(node.child_nodes))] if len(
node.child_nodes) > 0 else 'no one ', 'as children.', sep='')
if node.child_nodes:
for member in node.child_nodes:
member.print_tree(member)
def search_tree2(self, node):
if self.name == node.name:
return self
elif self.child_nodes:
for child in self.child_nodes:
result = child.search_tree2(node)
if result:
return result
return None
def delete_node(self, node):
parent = self.search_tree2(node.parent)
for child in parent.child_nodes:
if child.name == node.name:
parent.child_nodes.remove(child)
family = Tree(name='root', parent=None)
rebecca = family.add_node(value=64, name='Rebecca', parent=family)
jack = family.add_node(value=64, name='Jack', parent=family)
kate = family.add_node(value=36, name='Kate', parent=jack)
randall = family.add_node(value=36, name='Randall', parent=jack)
kevin = family.add_node(value=36, name='Kevin', parent=rebecca)
becky = family.add_node(value=11, name='Becky', parent=kevin)
daisy = family.add_node(value=8, name='Daisy', parent=randall)
jen = family.add_node(value=22, name='Jen', parent=kate)
william = family.add_node(value=8, name='William', parent=daisy)
kyle = family.add_node(value=20, name='Kyle', parent=kate)
解决方案
正如您在问题中提到的,您想使用递归。这意味着您应该从函数中调用您正在定义的函数。
当您遍历节点的子节点时,可以调用search_tree2
子节点。这将确保它递归整个树的深度。它还将在所有节点上执行您定义的逻辑,因此您无需在循环中为子节点添加 if 条件。
您的代码将如下所示:
def search_tree2(self, node):
if self.name == node.name:
return self
elif self.child_nodes:
for child in self.child_nodes:
result = child.seach_tree2(node)
if result:
return result
# Could not find the result in any of the children
return None
推荐阅读
- flutter - 模拟器上的应用程序运行完美,但在真实设备上运行时,位置标记不可见,并且在运行代码时显示无法加载资产
- c# - 需要使用正则表达式用“,”而不是“\”来分割字符串
- latex - 如何减少位于其他节点之上的 2 个节点之间的空间?
- xamarin.forms - 如何使项目包装在 Xamarin 表单中
- kotlin - 如何在 Kotlin 中将字节转换为位串?
- machine-learning - 将参数发送到 Keras Tuner 模型构建器函数
- python - 使用 .get() 处理不存在的嵌套键
- video - 通过 WebRTC 分辨率更改问题的 HTML5 视频和 MediaStreamTrack 流
- python - 如何与 matplotlib 同步绘图?
- swift - 启用应用程序组时使用`defaults` CLI:“域不存在”