Baumstruktur Kategorie Summe daß Kaskaden-Knoten zu verankern

Question

Ich werde richtig herauskommen und sagen, dass ich bin nicht die Welten größte Mathematikers: D der meisten von Ihnen So gut dieses Problem kann einfach sein. Es ist verwirrend ich leider und hat mehrere Stiche an einer praktikable Lösung hat.

Wie bei jedem Baum kann man viele Zweige haben, können viele Zweige mehr Zweige haben und so weiter, bis sie mit einem Blattknoten zu beenden. Ich habe auf jedes Blatt erhält Informationen, die seinen Wert angibt.

Was ich benötige ist ein klares explination, wie das Problem zu lösen jeden Blattknoten Wert als Summe der Zusammenfassung für seine Niederlassung (Eltern) und das gleiche für den Rest zu tun, aber nicht vergessen, dass, wenn ein Zweig von anderen Zweigen geteilt wird dass es die Zusammenfassung der einzelnen unteren Ebene Zweig und Blatt, das sich direkt in Beziehung steht.

Um besser zu erklären:

Root
|----Branch
|         |-Leaf 10
|----Branch
|         |----Branch
|         |-Leaf 20 |-Leaf 30
|----Branch         |-Leaf 40
|         |----Branch
|                   |----Branch
|                             |----Leaf 50
|-Leaf 60

Ziel:

Root 210
|----Branch 10
|         |-Leaf 10
|----Branch 90
|         |----Branch 70
|         |-Leaf 20 |-Leaf 30
|----Branch 50      |-Leaf 40
|         |----Branch 50
|                   |----Branch 50
|                             |----Leaf 50
|-Leaf 60

Ich bin in der Lage, die unterste Ebene Mitglieder (Blattknoten), den Wurzelknoten und die Zweige, sich zu identifizieren. Ich habe keine Identifizierung, ob oder nicht der Zweig hat andere an sich selbst gebunden Zweige unten oder direkt zu einem Blattknoten verknüpft. Die Beziehung ist sehr viel unten nach oben zu root. IE. Der Zweig hat keinen Hinweis auf die es die Kinder sind, aber die Kinder wissen, wer der Elternteil

Bitte, wenn etwas unklar fragen, und ich werde versuchen, das Problem besser erklären.

Jede mögliche Hilfe würde geschätzt.

Answer 1

OK, lefts geben diese einen Stich.

Ich würde mit einigen Pseudo-Code über das so gehen

foreach leaf in knownLeafs
    parent = leaf.parent //get the leaf parent
    parent.total = parent.total + leaf.value //add leaf value to parent total
    while parent.parent != null //loop until no more parents, this would be the root
    {
        current = parent
        parent = parent.parent //move up the structure
        parent.total = parent.total + current.total
    }
next leaf

Sie müssten eine Funktion erstellen, die einen Knoten gegeben wird, geben Sie den übergeordneten Knoten

node GetParentNodeFrom (Knoten)

Der neue Pseudo-Code würde wie folgt aussehen

foreach leaf in knownLeafs
parent = GetParentNodeFrom(leaf) //get the leaf parent

parent.total = parent.total + leaf.value //add leaf value to parent total
while GetParentNodeFrom(parent) != null //loop until no more parents, this would be the root
{
    current = parent
    parent = GetParentNodeFrom(current) //move up the structure
    parent.total = parent.total + current.total
}
next leaf

Sorry, mein Fehler, sollten Sie nur das Blatt Wert nach oben, nicht zu den Summen. Siehe neuen leafValue verwendet.

foreach leaf in knownLeafs
parent = GetParentNodeFrom(leaf) //get the leaf parent
leafValue = leaf.value
parent.total = parent.total + leafValue //add leaf value to parent total
while GetParentNodeFrom(parent) != null //loop until no more parents, this would be the root
{
    current = parent
    parent = GetParentNodeFrom(current) //move up the structure
    parent.total = parent.total + leafValue
}
next leaf

Answer 2

Sie möchten die Summe aller Knoten im Baum bestimmen?

Baum Walking eignet sich für eine elegante rekursive Lösung:

public int SumTree (TreeNode n) {
    if(n.isLeafNode) return n.value;
    return SumTree(n.left) + SumTree(n.right);
}

Unter der Annahme eines binären Baum.