data-structures - 将节点值向有根树中的根节点求和

Question

问题

我有一个有向根树，其中每个节点都有一些初始值。我希望每个节点的新值等于它及其后代的初始值的总和。我将这个过程设想为从叶节点开始并将值沿树向上传播到根节点。

到过程结束时，根节点的值应该是所有节点的总和；每个其他节点相应地具有较小的值；每个叶节点都有它开始的值（因为没有子节点可以求和）。

在给定图形上执行此过程的最佳/最优雅的方式是什么？

数据结构

只是为了澄清有向根树：它是有向无环图的限制形式，其中每个节点最多有一个父节点，并且有一个唯一指定的没有父节点的根节点。

在我的实现中，每个节点都有一个对其父节点的引用（根节点为空）和一个对其子节点的引用数组（叶节点为空）。

插图

初始树和节点值

具有更新节点值的修改树

尝试失败

我的简单初始尝试从叶节点开始，每个节点向上遍历树，将运行总和添加到其父节点中，直到达到分叉的父节点——这样一个节点被添加为从下一个开始的候选节点迭代。

这样做的问题是某些分叉节点可以多次叠加到它们自己的父节点中，例如，如果从其自己的子节点到相关叶节点的路径具有不同数量的进一步分叉节点。

List<Node> nodes = getLeaves();
HashSet<Node> nextNodes = new HashSet<>();

while (!nodes.isEmpty()) {

    for (Node node : nodes) {

        Node current = node;

        while (current.degree < 2) { // terminate when reach bifurcating parent node
            current.parent.value += current.value;
            current = current.parent;
        }

        if (current.parent != null) { // skip root node
            nextNodes.add(current.parent); // add bifurcating parent node for next iteration
        }

    }
    nodes = new ArrayList<Node>(nextNodes);
    nextNodes.clear();
}

标签： data-structurestreegraph-theorygraph-algorithmdirected-acyclic-graphs