Árvore Categoria estrutura soma que cascatas para nó raiz

Question

Vou dar certo e dizer que eu não sou dos mundos o grande matemático: D Portanto, este problema pode ser bem simples para a maioria de vocês. Infelizmente isso está me confundindo e tiveram várias facadas em uma soluções viáveis.

Como acontece com qualquer árvore, pode-se ter muitos ramos, muitos ramos podem ter mais ramos e assim por diante até que eles acabam com um nó folha. Eu tenho informações sobre cada folha que indica o seu valor.

O que eu preciso é um explination clara sobre como lidar com o problema de resumir cada valor nó folha como um total para a sua filial (pai) e fazer o mesmo para o resto, mas não esquecendo que, se um ramo é compartilhada por outros ramos que é o resumo de cada ramo nível mais baixo e folha que está diretamente relacionada com o próprio.

Para explicar melhor:

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

O 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

Eu sou capaz de identificar os mais baixos membros de nível (nós folha), o nó raiz e dos próprios ramos. Eu não tenho identificação sobre se ou não o ramo tem outros ramos ligados a si mais abaixo ou diretamente ligados a um nó folha. A relação é muito baixo para cima a raiz. IE:. O ramo não tem referência para quem é as crianças são, mas as crianças sabem quem é o pai

Por favor, se algo não estiver claro perguntar e eu vou tentar explicar melhor o problema.

Qualquer ajuda seria apreciada.

Answer 1

OK, esquerdas dar a este uma facada.

eu iria sobre isso assim com algum código 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

você precisa criar uma função que, dado um nó, o retorno do pai nó

nó GetParentNodeFrom (nó)

o novo código pseudo seria algo parecido com isto

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

Desculpe, meu erro, você só deve mover o valor da folha para cima, não os totais também. Ver o novo leafValue usado.

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

Você quer determinar a soma de todos os nós na árvore?

Árvore curta se presta a uma solução recursiva elegante:

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

Assumindo uma árvore binária.