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

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

2 голосов
/ 04 декабря 2009

Я собираюсь выйти прямо и сказать, что я не величайший математик в мире: 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: В ветке нет ссылок на то, кто это дети, но дети знают, кто их родители.

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

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

Ответы [ 2 ]

2 голосов
/ 04 декабря 2009

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

Я бы сделал это с каким-нибудь псевдокодом 

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
0 голосов
/ 04 декабря 2009

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

Прогулка по дереву предоставляет элегантное рекурсивное решение: 

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

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

...