百分比和树木

我有一棵无序的树。 每个节点代表一个可以完成 (1)、未完成 (0) 或有子任务的任务。

例如：

1
-1.1
-1.2
--1.2.1
--1.2.2
-1.3
2
3
-3.1
4
-4.1
--4.1.1
5

假设叶子 1.2.1、3.1 和 5 是done

1
-1.1
-1.2
--1.2.1*
--1.2.2
-1.3
2
3
-3.1*
4
-4.1
--4.1.1
5*

我想计算每个节点的完整性百分比。叶子很容易用0%或100%来计算，但是如何计算所有其他的呢？

目前，我从叶子开始遍历树，每个节点都是根据子节点的完整性百分比来计算的。例如：

1      50%
-1.1*  100%
-1.2   0%
2      0%
3      33%
-3.1*  100%
-3.2   0%
-3.3   0%

现在，1.2 中添加了更多子节点（不再是叶子，而是成为节点）。如果孩子们“没有完成”，1.2 总是 0%，所以 1 是 50%，但我希望 1 是less那么50%，因为，递减到他的子孙要完成的任务数量，才能让它完成100%更大！

1       50%
-1.1*   100%
-1.2    0%
--1.2.1 0%
--1.2.2 0%
2       0%
3       33%
-3.1*   100%
-3.2    0%
-3.3    0%

计算这个的最佳方法是什么？谢谢

您可以将 %done 定义为已完成的（子）节点总数除以（子）节点总数。只数叶子。

在这种情况下：

       1  (1/2 = 50%)
      / \
   1.1*  1.2

添加额外的节点：

       1  (1/3 = 33%)
      / \
   1.1*  1.2 (0/2 = 0%)
         / \
    1.2.1   1.2.2

如果这还不够，您可以为每个任务添加一个权重，并计算完成的重量除以总重量。