python - 在树上聚合节点的值
问题描述
我有一个相当复杂的树结构,我想遍历和聚合值(例如求和、连接、追加......)。我想traverse
成为树的一种方法,而不是一个单独的函数。我可以遍历并将函数应用于每个节点,但我无法弄清楚如何更新与树关联的聚合变量。
这是我的代码的简化版本,包括没有聚合的节点处理程序,这是可行的。
# A tree is a node that recursively includes more nodes under it.
# More correctly the Tree is the particular node regarded as the root Node.
class Node:
def __init__(self, value):
self.value = value
self.children = []
def traverse(self, handle_node):
handle_node(self)
for child in self.children:
child.traverse(handle_node)
tree = Node('A')
tree.children.append(Node('B')) # Note we append Nodes not values!
tree.children.append(Node('C'))
tree.children[1].children.append(Node('D'))
tree.children[1].children.append(Node('E'))
# This is just an example of a node-handler.
def example_func_on_a_node(node):
print(node.value)
# Execute the node handler on every node in the tree.
tree.traverse(example_func_on_a_node)
正如所料,这打印
A
B
C
D
E
但是,我想要的是在一般情况下进行聚合。如果我有一个返回值的节点处理程序,我如何将每个节点的值与所有先前节点的值结合起来最终返回聚合。节点处理程序需要是一个通用函数,它将节点作为参数并返回一个值。
例如,假设我想连接上述简单示例中的值。代码应该看起来像这样,但这不起作用。
class Node2:
def __init__(self, value):
self.value = value
self.children = []
self.concat = ''
def traverse(self, handle_node):
self.concat += handle_node(self)
for child in self.children:
child.traverse(handle_node)
tree = Node2('A')
tree.children.append(Node2('B')) # Note we append Nodes not values!
tree.children.append(Node2('C'))
tree.children[1].children.append(Node2('D'))
tree.children[1].children.append(Node2('E'))
# This is a node-handler that returns a value I want to aggregate.
def example_func_on_a_node2(node):
return node.value
# Execute the node handler on every node in the tree.
tree.traverse(example_func_on_a_node2)
print(tree.concat)
我得到的答案是A
,但我想要的是'ABCDE'
注意我尝试了很多变体,包括使用静态和类方法,以及非局部变量,但很可能错误地使用了它们。
我可以看到我需要什么,但看不到聚合变量的放置位置,因此它在树周围传递并返回根节点,同时保持节点处理程序和节点类简单。
解决方案
您的代码不起作用,因为self.concat
指的是当前节点。因此,您不会在某处聚合值,而是将每个节点的值放入一个单独的concat
变量中,最终只打印其中一个(第一个)。所以你需要做的是为每次调用提供对同一个变量的引用traverse
。有多种方法可以做到这一点:
可能性 A:使用全局变量(另请参阅为什么全局变量是邪恶的?)
class Node2:
def __init__(self, value):
self.value = value
self.children = []
def traverse(self, handle_node):
global concat
concat += handle_node(self)
for child in self.children:
child.traverse(handle_node)
concat = ''
tree = Node2('A')
tree.children.append(Node2('B')) # Note we append Nodes not values!
tree.children.append(Node2('C'))
tree.children[1].children.append(Node2('D'))
tree.children[1].children.append(Node2('E'))
# This is a node-handler that returns a value I want to aggregate.
def example_func_on_a_node2(node):
return node.value
# Execute the node handler on every node in the tree.
tree.traverse(example_func_on_a_node2)
print(concat)
可能性 B:使用类变量
class Node2:
concat = ''
def __init__(self, value):
self.value = value
self.children = []
def traverse(self, handle_node):
self.__class__.concat += handle_node(self)
for child in self.children:
child.traverse(handle_node)
tree = Node2('A')
tree.children.append(Node2('B')) # Note we append Nodes not values!
tree.children.append(Node2('C'))
tree.children[1].children.append(Node2('D'))
tree.children[1].children.append(Node2('E'))
# This is a node-handler that returns a value I want to aggregate.
def example_func_on_a_node2(node):
return node.value
# Execute the node handler on every node in the tree.
tree.traverse(example_func_on_a_node2)
print(tree.concat)
可能性 C:使用return
intraverse
将内部concat
值“传递”到第一个值
class Node2:
def __init__(self, value):
self.value = value
self.children = []
self.concat = ''
def traverse(self, handle_node):
self.concat += handle_node(self)
for child in self.children:
self.concat += child.traverse(handle_node)
return self.concat
tree = Node2('A')
tree.children.append(Node2('B')) # Note we append Nodes not values!
tree.children.append(Node2('C'))
tree.children[1].children.append(Node2('D'))
tree.children[1].children.append(Node2('E'))
# This is a node-handler that returns a value I want to aggregate.
def example_func_on_a_node2(node):
return node.value
# Execute the node handler on every node in the tree.
tree.traverse(example_func_on_a_node2)
print(tree.concat)
可能性 D:添加一个可选参数以traverse
将第一个节点的引用传递给后续调用traverse
class Node2:
def __init__(self, value):
self.value = value
self.children = []
self.concat = ''
def traverse(self, handle_node, tree=None):
if tree is None:
tree = self
tree.concat += handle_node(self)
for child in self.children:
child.traverse(handle_node, tree)
tree = Node2('A')
tree.children.append(Node2('B')) # Note we append Nodes not values!
tree.children.append(Node2('C'))
tree.children[1].children.append(Node2('D'))
tree.children[1].children.append(Node2('E'))
# This is a node-handler that returns a value I want to aggregate.
def example_func_on_a_node2(node):
return node.value
# Execute the node handler on every node in the tree.
tree.traverse(example_func_on_a_node2)
print(tree.concat)
推荐阅读
- linux - 如何从多个 dec 值构建 ASCII 十六进制转储?
- swift - 谷歌自动完成不填充表格视图
- android - 普通的虚拟主机可以作为安卓应用的后端吗?
- html - Firefox 和 Safari 浏览器的字体不工作问题
- azure - 外部用户无法登录 Azure DevOps
- sql - 获取具有 JSONB 值的行,以及如果值不存在的行
- ionic-framework - 使用 PHPMailer 和 ionic 3 发送电子邮件
- c - Sys V ABI 规范(i386 和 AMD64)中描述的标准“函数调用序列”是否适用于静态 C 函数?
- jenkins - 如何同时在同一个项目(工作区)上运行多个 SonarQube 分析?
- javascript - 从 RN 中的 setTimeout 或 Alert 回调中调度 redux 操作时性能下降