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

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

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

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);
}

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