C++: la Somme de toutes les valeurs de nœud d'un arbre binaire

L'élégante solution récursive (en pseudo-code):

def sum (node):
    if node == NULL:
        return 0
    return node->value + sum (node->left) + sum (node->right)

alors utilisez simplement:

total = sum (root)

Ce gère correctement le cas d'une valeur NULL nœud racine.

---

Et si vous voulez le voir en action en C++, voici le code à l'aide de cet algorithme. Tout d'abord, la structure d'un nœud et le sum fonction:

#include <iostream>

typedef struct sNode {
    int value;
    struct sNode *left;
    struct sNode *right;
} tNode;

int sum (tNode *node) {
    if (node == 0) return 0;
    return node->value + sum (node->left) + sum (node->right);
}

Puis le code ci-dessous est un harnais de test de code pour l'insertion de nœuds:

static tNode *addNode (tNode *parent, char leftRight, int value) {
    tNode *node = new tNode();
    node->value = value;
    node->left = 0;
    node->right = 0;

    if (parent != 0) {
        if (leftRight == 'L') {
            parent->left = node;
        } else {
            parent->right = node;
        }
    }

    return node;
}

Et, enfin, la fonction principale de la construction de l'arbre suivant, qui couvre l'ensemble de la validité de possibilités (vide nœud, nœud avec deux enfants, nœud, sans enfants, nœud avec un droit à l'enfant et à nœud avec un gauche de l'enfant):

    10
   /  \
  7    20
 /       \
3         99
 \
  4
   \
    6

Le code pour construire l'arbre et le rapport de la somme à différents points est indiquée ici:

int main (void) {
    //Empty tree first.

    tNode *root = 0;

    std::cout << sum (root) << '\n';

    //Then a tree with single node (10).

    root = addNode (0, ' ', 10);

    std::cout << sum (root) << '\n';

    //Then one with two subnodes (10, 7, 20).

    addNode (root,'L',7);
    addNode (root,'R',20);

    std::cout << sum (root) << '\n';

    //Then, finally, the full tree as per above.

    addNode (root->left,'L',3);
    addNode (root->left->left,'R',4);
    addNode (root->left->left->right,'R',6);
    addNode (root->right,'R',99);

    std::cout << sum (root) << '\n';

    return 0;
}

Ce sorties (la bonne):

0
10
37
149

OriginalL'auteur paxdiablo

De la même manière que la recherche de l'arbre, ou l'affichage de chaque nœud, ou de tout autre arbre à l'échelle de l'opération: visite du nœud actuel, visite de la gauche du sous-arbre (de manière récursive), et de visiter le droit de sous-arbre (de manière récursive).

Essentiellement, quelque chose comme ceci:

int TreeNode::calculateSum() const
{
    int sum = this->value;

    if (this->left  != NULL) sum += this->left ->calculateSum();
    if (this->right != NULL) sum += this->right->calculateSum();

    return sum;
}

En raison de la if vérifie la récursivité finira par le fond lorsqu'il atteint les nœuds avec pas à gauche ou à droite des enfants (les nœuds feuilles).

OriginalL'auteur John Kugelman

Utiliser l'une de l'Arbre Transversal techniques(Dans l'ordre, en Pré-commande, Post-order) à visiter, chaque nœud et de stocker la somme dans une variable.

Vous pouvez trouver plus de détails sur l'arbre transversal dans ce wiki

OriginalL'auteur aeh

public int sum(Node root){
    if(root==null){
        return 0;
    }
    if(root.left == null && root.right==null){
        return root.key;
    }
    return sum(root.left)+sum(root.right)+root.key;
}

OriginalL'auteur Antoniet Ama Aggrey