Prozentsätze und Bäume

Question

Ich habe einen ungeordneten Baum. Jeder Knoten stellt eine Aufgabe dar, die ausgeführt werden kann (1), nicht erledigt (0) oder untergeordnete Aufgaben haben.

Zum Beispiel:

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

sei angenommen, dass die Blätter 1.2.1, 3.1 und 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* 

Ich möchte berechnen den Prozentsatz der Vollständigkeit der einzelnen Knoten erfolgt sind. Die Blätter sind leicht mit 0% oder 100% berechnet, aber wie berechnet man alle anderen?

Im Moment gehe ich den Baum von den Blättern auf und jeder Knoten wird basierend auf dem Prozentsatz der Vollständigkeit der Kinder berechnet. Zum Beispiel:

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

Nun werden mehr Kinder zu 1.2 hinzugefügt (das ist kein Blatt mehr, sondern wird zu einem Knoten). Wenn die Kinder "nicht fertig" sind, ist 1,2 immer 0% und so ist 1 50%, aber ich möchte 1 weniger dann 50%, wie, absteigend in seine Kinder und Enkel die Anzahl der Aufgaben zu abgeschlossen sein, damit es fertig ist 100% ist größer!

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% 

Was ist der beste Weg, dies zu berechnen? Dank

Answer 1

Sie können das% definieren als Gesamt (sub) erfolgt Knoten, die durch insgesamt (Unter-) Knoten fertig geteilt. Zählen nur die Blätter.

In diesem Fall:

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

den zusätzlichen Knoten hinzu:

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

Wenn das nicht genug ist, können Sie ein Gewicht auf jede Aufgabe hinzufügen und das Fertiggewicht durch die Gesamt geteilt berechnen Gewicht.

Answer 2

Sie mit einem post order visit (Pseudo-Code) versuchen könnten:

postorder(node) { 

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

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

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

Answer 3

Für jeden Knoten, % done = Anzahl der Nachkomme verlässt done/Gesamtanzahl der Nachkomme

Wo Blätter:

Anzahl von Nachkommen verlässt = Summe (für Kinder Anzahl der Nachkomme Blätter)

Answer 4

Das hängt von dem Gewicht ab, das Sie jedem Level geben möchten. Wenn ich du wäre, würde ich die erste Methode wählen, die du erwähnt hast (dh dasselbe Gewicht auf Gegenstände auf dem gleichen Level legen), also würde 1 mit 50% richtig zu mir aussehen und der Unterschied, mehr Knoten zu haben, würde durch einen langsameren Anstieg gesehen werden von 'getan' Prozent für 1.2 Knoten.

Um einen Knoten auf weiter entfernte Vorfahren zu beeinflussen, könnten Sie den Vorfahrenprozentsatz als Durchschnitt alle die Blätter in seinem Teilbaum berechnen (das würde 33% Vervollständigung für Aufgabe 1 geben), aber das scheint nicht ganz direkt zu mir.Alles hängt davon ab, wie Sie die Daten wirklich darstellen wollen - ich glaube nicht, dass es einen "richtigen" Weg gibt.

Answer 5

Ich denke, der Prozentsatz jedes Knotens ist der Durchschnittswert seiner Kinder (nicht Unterkinder) Prozentsätze.

Zum Beispiel

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