百分比和树木

Question

我有一棵无序的树.每个节点代表一个可以完成(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 完成了

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 小于 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%

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

Answer 1

您可以将完成的%完成定义为总(子)节点除以总(子)节点.只计算叶子.

在这种情况下:

       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

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