Сумма категорий древовидной структуры, которая каскадируется к корневому узлу

Question

Я собираюсь прямо заявить, что я не величайший математик в мире : D Так что эта проблема вполне может показаться простой для большинства из вас.К сожалению, это сбивает меня с толку, и у меня было несколько попыток найти приемлемые решения.

Как и у любого дерева, у одного может быть много ветвей, у многих ветвей может быть больше ветвей и так далее, пока они не закончатся листовым узлом.У меня есть информация на каждом листе, которая указывает на его ценность.

Что мне нужно, так это четкое объяснение того, как решить проблему суммирования значения каждого конечного узла в виде итога для его ветви (родительской) и выполнения того же для остальных, но не забывая, что если ветвь является общей для других ветвей, то это сводка каждой ветви и листа более низкого уровня, которая напрямую связана сама с собой.

Чтобы лучше объяснить:

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

Цель:

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

Я могу идентифицировать элементы самого низкого уровня (конечные узлы), корневой узел и сами ветви.У меня нет информации о том, есть ли у ветви другие ветви, связанные с ней ниже или напрямую связанные с конечным узлом.Отношения в значительной степени восходящие к корню.IE:Ветвь не имеет ссылки на то, кто ее дочерние элементы, но дочерние элементы знают, кто является родителем.

Пожалуйста, если что-то непонятно, спрашивайте, и я постараюсь лучше объяснить проблему.

Будем признательны за любую помощь.

Answer 1

Хорошо, левые нанесут удар по этому вопросу.

Я бы сделал это следующим образом с помощью некоторого псевдокода

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

вам нужно было бы создать функцию, которая при заданном узле вернет родительский узел

узел GetParentNodeFrom(узел)

новый псевдокод будет выглядеть примерно так

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

Извините, моя ошибка, вы должны увеличить только конечное значение, но не итоговые значения.Смотрите, как используется новое конечное значение.

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

Вы хотите определить сумму всех узлов в дереве?

Хождение по деревьям является элегантным рекурсивным решением:

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

Предполагая двоичное дерево.