パーセンテージとツリー

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 

は3.1、1.2.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% 

これを計算するにはどのような方法が最適ですか？あなたはpost order visit（擬似コード）を試みることができるおかげで

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 

それが十分でない場合は、各タスクに重みを追加し、合計で割った完成重量を計算することができます重量。子孫の葉の

番号= SUM（子孫の葉の子供＃：子孫の＃は子孫の完了/全＃は

葉葉

任意のノードについて

Answer 2

：

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

これは、各レベルに与えたい体重によって異なります。私があなたの場合は、最初に述べた方法を選択します（つまり、同じレベルのアイテムに同じ重みを付けます）.50％で1が私にとって正しいと思われ、より多くのノードを持つことの違いは、 1.2ノードの「完了」パーセンテージの

あなたはそのサブツリーにすべて葉の平均として祖先の割合を計算することができ、より遠い祖先に影響を与えるノードを取得するために（つまり、タスク1のために33％の完了を与えるだろう）が、これはかなりのようではありません私には正しい。それはすべてあなたが本当にデータを表現する方法に依存しています - 私はそれを行うのに「正しい」方法がないと思います。

Answer 5

私は、各ノードのパーセンテージは、その子（子ノードではない）パーセンテージの平均値だと思います。まだ与えられた回答のほとんどと不一致

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