Проценты и деревья

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

Если этого недостаточно, вы можете добавить вес к каждому заданию и рассчитать общий вес, разделенный на общий вес.

Answer 2

Для любого узла, % выполнено = количество потомков листья выполнено / всего количество потомков листья

Где:

количество листьев потомков = сумма (количество листьев потомков детей)

Answer 3

Я думаю, что процент каждого узла - это среднее значение его дочерних (не дочерних) процентов.

Например

 1_per = (1.1_per + 1.2_per) / 2
 3_per = (3.1_per + 3.2_per + 3.3_per) / 3

Answer 4

Это зависит от веса, который вы хотите придать каждому уровню. Если бы я был вами, я бы выбрал первый метод, который вы упомянули (т.е. поместите тот же вес на предметы на том же уровне), чтобы 1 с 50% выглядело бы правильно для меня, и разница в наличии большего количества узлов была бы замечена при медленном увеличении Процент «выполнено» для 1,2 узла.

Чтобы узел влиял на более отдаленных предков, вы можете рассчитать процент предков как среднее значение всех листьев в его поддереве (что дало бы 33% завершения для задачи 1), но это не Мне кажется, это совершенно не правильно. Все зависит от того, как вы действительно хотите представлять данные - я не думаю, что есть «правильный» способ сделать это.

Answer 5

Вы можете попробовать с посещением после заказа (псевдокод):

postorder(node) {

    foreach(child : children) {
        postorder(child)
        node.visited++

        if (child.completed == 1) {
           node.completed++        
        }
    }

    print("%d%%", (node.completed / node.visited) * 100)
}