Albero categoria struttura somma che cascate a radicare nodo

Question

Ho intenzione di venire a destra fuori e dire che io non sono il più grande matematico mondi: D Quindi questo problema potrebbe essere semplice per la maggior parte di voi. Purtroppo mi sta confondendo e hanno avuto diverse coltellate in una soluzioni praticabili.

Come con qualsiasi albero, si può avere molti rami, molti rami possono avere più rami e così via fino a che non terminano con un nodo foglia. Ho informazioni su ogni foglia che indica il suo valore.

Che cosa ho bisogno è un chiaro explination su come affrontare il problema di riassumere ogni valore nodo foglia come un totale per sta ramo (padre) e fare lo stesso per il resto, ma non dimenticare che se un ramo è condivisa da altri rami che è la sintesi di ogni ramo di livello inferiore e foglia che è direttamente correlato a se stesso.

Per spiegare meglio:

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

L'obiettivo:

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

Sono in grado di identificare i membri più bassi di livello (nodi foglia), il nodo radice ei rami stessi. Non ho identificazione o meno del ramo ha altri rami collegati a sé più in basso o direttamente collegati ad un nodo foglia. Il rapporto è molto basso verso l'alto a root. IE:. Il ramo non ha alcun riferimento a chi di bambini sono, ma i bambini sanno che il genitore è

Per favore, se qualcosa non è chiaro chiedere e cercherò di spiegare meglio il problema.

Qualsiasi aiuto sarebbe apprezzato.

Answer 1

OK, sinistre dare a questo una pugnalata.

Vorrei andare su di esso in questo modo con un po 'pseudo codice

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

si avrebbe bisogno di creare una funzione che, dato un nodo, restituire il nodo principale

nodo GetParentNodeFrom (nodo)

il nuovo codice pseudo sarebbe simile a questo

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

Siamo spiacenti, il mio errore, si deve spostare solo il valore foglia su, non i totali troppo. Vedere nuova leafValue utilizzato.

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

Si vuole determinare la somma di tutti i nodi dell'albero?

Albero a piedi si presta ad una elegante soluzione ricorsiva:

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

Supponendo un albero binario.