Árbol estructura de categorías suma que cae en cascada a nodo raíz

Question

Voy a venir a la derecha y decir que no soy el más grande matemático mundos: D Así que este problema puede también ser simple a la mayoría de ustedes. Por desgracia me está confundiendo y han tenido varias puñaladas en unas soluciones viables.

Como con cualquier árbol, uno puede tener muchas ramas, muchas ramas pueden tener más ramas y así sucesivamente hasta que terminan con un nodo hoja. Tengo información sobre cada hoja que indica su valor.

Lo que necesita es una clara explination sobre la manera de abordar el problema de resumir cada valor de nodo de hoja como un total por su rama (matriz) y hacer lo mismo para el resto, pero sin olvidar que si una rama es compartida por otras ramas que es el resumen de cada rama de nivel inferior y la hoja que está directamente relacionada con la misma.

Para explicar mejor:

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

El objetivo:

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

Soy capaz de identificar los miembros más bajos de nivel (nodos de hoja), el nodo raíz y las propias ramas. No tengo identificación de si o no la rama tiene otras ramas ligadas a sí mismo más abajo o directamente vinculados a un nodo hoja. La relación es muy inferior hacia arriba a la raíz. IE:. La rama no tiene ninguna referencia a quién ha tenido como son los niños, pero los niños sabe quién es el padre

Por favor, si algo está claro preguntar y voy a tratar de explicar mejor el problema.

Cualquier ayuda sería apreciada.

Answer 1

OK, izquierdas dan a esta una puñalada.

Me gustaría ir en ello como esto con un poco de pseudo código

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

lo que se necesita para crear una función que, dado un nodo, devolver el nodo padre

nodo GetParentNodeFrom (nodo)

la nueva pseudo código sería algo como esto

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

Lo siento, mi error, que sólo debe mover el valor de la hoja hacia arriba, no los totales también. Véase el nuevo leafValue utilizado.

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

Se desea determinar la suma de todos los nodos en el árbol?

El árbol caminar se presta a una solución recursiva elegante:

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

Si se asume un árbol binario.