对一棵树求和，值在叶节点中，小计在父节点中，直到根节点

Question

是否有现成的解决方案来对 n 叉树的所有叶节点求和，并将总和分配给它们的父节点，一直到根？

让我解释一下。我每周都会收到几份报告。它是一份财务文件，本质上是一个不平衡的分层数据集，最多可达九层。值仅在最后一级分配，但每个父级都有其子级的总和（即只有一个边缘）。

它看起来像：

root:
    sectionA:
        sectionB:
            sectionC:
                sectionD:
                    subtotal sectionE = sum of x 
                        leaf-1 = x_1
                        leaf-2 = x_2
                        leaf-n = x_n

我正在努力对此数据集进行自动化验证。我需要对每片叶子求和并确定它是否匹配它的 parent-subtotal 一直到 root-total.

此外，我还有第二个 table 列出所有叶元素及其父关系。像这样：

root:sectionA:sectionB:sectionC:sectionD:sectionE:leaf

我认为 k 元树可以表示从 table #2 生成的正确报告结构。然后使用树与每周报告进行比较。我喜欢这个方向，因为第二个 table 具有这种形式的结构数据（完整的父路径）。更进一步，当我的脚本完成时，我将需要概括解决方案。

是否有解决此问题的 Python 模块或通用算法？

这是一个示例解决方案，Sum of all elements of N-ary Tree。但是这个解决方案假设每个节点都有一个唯一的值，而边缘只是关系。

Answer 1

在鼓励的这种激动人心的回应之后，我在 NetworkX 中实施了一个解决方案。

研究文档和其他不同来源，我了解了我的特定 求和树问题（root 'amount' 值是 'amount' 每个 children) 的属性在野外并不常见——对其他人来说很明显。

对于后来发现此问题的任何人，这里是解决方案的概要。我用 Pandas 构建了如下图。

创建查询结果的 DF。
Munge DF（删除未使用的行、列）。
headers 和 DF 列的基本文本规范化
明确编辑 DF 行中的节点标签例外。
parent、child 标签发现的条件 DF。
将 DF 划分为与根的距离递增的块。
创建基础图。
更新基础图；使用 #6
用节点值更新图表。
验证每个 parent 节点的分配值与其 child 值之和的比较，recursively with a little help from my friends。

使用 NetworkX 从不同输入创建树的两个有用提示

为什么 G 不是一棵树？几种推荐的图形检查方法（nx.is_connected(G)、nx.connected_component_subgraphs(G)）导致此错误：NetworkXNotImplemented: not implemented for directed type。（第 10 步需要有向图）。另一种方法 (list(nx.isolates(G))) 没有产生错误，但总是产生一个空列表。

这棵树的最终图形生成解决方案使用了两种技术来确保图形是一棵树：

通过将节点添加到公共静态定义的基础图来构建图。
利用更多列数据将输入 DF 分块到从根开始递增的级别。

最后一点不是根据此数据创建树的要求，因为输入数据已经具有树结构。但是，有必要调试结果量中的节点标签。更新 DF 对于图形来说不是必需的，但事实证明它对以后的调试和识别标签异常值很有用。

所有异常情况都是源数据中的名称不一致。源数据发生变化，因此这将继续成为寻找未来解决方案的问题。

对一棵树求和，值在叶节点中，小计在父节点中，直到根节点

Sum a tree, with values in leaf nodes and subtotal in parent, up to root

python

graph-theory