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

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

вы могли бы попробовать с post order visit (псевдокод):

postorder(node) { 

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

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

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

Answer 3

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

Где:

количество потомка листьев = СУММ (# детей игровая из потомков листьев)

Answer 4

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

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

Answer 5

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

Например

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