对树求和，值在叶节点中，小计在父节点中，向上

Question

有没有一个现成的解决方案来求n元树的所有叶节点的和，并将和分配给它们的父节点直至根节点？你知道吗

让我解释一下。我每周收到几份报告。这是一个金融文件，本质上是一个不平衡的层次数据集，多达九个层次。值仅在最后一级分配，但每个父级都有其子级的总和（即只有1个边）。你知道吗

它看起来像：

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

我正致力于自动验证这个数据集。我需要对每片叶子求和，并确定它是否匹配它的父小计，一直到根总数。你知道吗

另外，我还有一个表列出了所有叶元素及其父关系。像这样：

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

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

是否有一个Python模块或可归纳的算法来解决这个问题？你知道吗

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

Answer 1

在这种振奋人心的鼓励之后，我在NetworkX中实现了一个解决方案。你知道吗

通过研究文档和其他各种来源，我了解到我的特定的求和树问题（根'amount'值是每个子级的'amount'属性的总和）在野外并不常见，对其他人来说很明显。你知道吗

对于任何后来发现这一点的人，这里是解决方案的概要。我用熊猫构建了如下图表。你知道吗

1. 创建查询结果的DF。你知道吗
2. Munge DF（删除未使用的行、列）。你知道吗
3. 标题和DF列的基本文本规范化
4. 显式编辑DF行中的节点标签异常。你知道吗
5. 父、子标签发现的条件。你知道吗
6. 将DF按与根的水平距离的增加分成块。你知道吗
7. 创建基本图形。你知道吗
8. 更新基本图形；使用#6添加父、子边
9. 使用节点值更新图形。你知道吗
10. 验证每个父节点的赋值与其子节点的值之和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对于图不是必需的，但是对于以后的调试和识别标签异常值是有用的。你知道吗

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