Arborescence catégorie somme qui tombe en cascade au noeud enracinent

Question

Je vais sortir tout droit et dire que je ne suis pas le plus grand monde Mathématicien: D Donc, ce problème pourrait être simple à la plupart d'entre vous. Malheureusement, il m'a confusion et ont eu plusieurs coups de couteau à une des solutions viables.

Comme un arbre, on peut avoir de nombreuses branches, de nombreuses branches peuvent avoir plus de branches et ainsi de suite jusqu'à ce qu'ils se terminent par un nœud feuille. J'ai des informations sur chaque feuille qui indique sa valeur.

Ce que je requiers une explination claire sur la façon d'aborder le problème de résumer chaque valeur de nœud feuille comme total il est branche (parent) et faire la même chose pour le reste, mais sans oublier que si une branche est partagée par d'autres branches qu'il est le résumé de chaque branche de niveau inférieur et la feuille qui est directement lié à lui-même.

Pour mieux expliquer:

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

Le but:

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

Je suis en mesure d'identifier les membres du plus bas niveau (nœuds de feuilles), le nœud racine et les branches elles-mêmes. Je n'ai pas d'identifier si oui ou non la branche a d'autres branches liées à elle-même plus bas ou directement liés à un nœud feuille. La relation est beaucoup plus bas vers le haut à la racine. IE:. La branche n'a pas de référence à qui il ENFANCE sont, mais les enfants savent qui est le parent est

S'il vous plaît, si quelque chose ne sait pas demander et je vais essayer de mieux expliquer le problème.

Toute aide serait appréciée.

Answer 1

OK, Gauches donner ce un coup de poignard.

Je voudrais aller à ce sujet comme celui-ci avec un code pseudo

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

vous devez créer une fonction qui, étant donné un nœud, retourner le nœud parent

GetParentNodeFrom noeud (noeud)

le nouveau code de pseudo ressemblerait à quelque chose comme ceci

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

Désolé, mon erreur, vous ne devez déplacer la valeur de vantail, pas les totaux aussi. Voir nouvelle leafValue utilisé.

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

Vous voulez déterminer la somme de tous les noeuds dans l'arbre?

marche des arbres se prête à une solution récursive élégante:

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

En supposant un arbre binaire.