C++: Summe aller Knotenwerte eines Binärbaums

Question

Ich bereite mich auf ein Vorstellungsgespräch vor. Ich steckte bei einer der binären Baumfragen fest:

Wie können wir die Summe der Werte in allen Knoten eines Binärbaums berechnen?

Answer 1

Die eleganten rekursive Lösung (in Pseudocode):

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

dann benutzen Sie einfach:

total = sum (root) 

Diese korrekt behandelt den Fall eines NULL-Wurzelknotens.

---

Und wenn Sie es in Aktion in C++ sehen möchten, hier ist ein Code mit diesem Algorithmus. Zuerst wird die Struktur für einen Knoten und die sum Funktion:

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

Dann unterhalb der Code ist ein Test-Harnisch-Code zum Einfügen von Knoten:

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

Und schließlich die wichtigste Funktion für den Aufbau der folgenden Baum, einer, der alle gültigen Möglichkeiten abdeckt (leerer Knoten, Knoten mit zwei Kindern, Knoten ohne Kinder, Knoten mit einem rechten Kind und Knoten mit einem linken Kind):

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

Der Code, den Baum zu konstruieren und die Summe an verschiedenen Punkten berichten wird hier gezeigt:

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

Diese Ausgänge (die richtigen):

0 
10 
37 
149 

Answer 2

Auf die gleiche Weise wie Sie den Baum durchsuchen oder jeden Knoten oder eine andere baumweite Operation anzeigen: Besuchen Sie den aktuellen Knoten, besuchen Sie den linken Teilbaum (rekursiv) und besuchen Sie den rechten Teilbaum (rekursiv) .

Im Grunde so etwas wie diese:

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

Wegen der if prüft die Rekursion wird schließlich unten, wenn es Knoten ohne nach links oder rechts Kindern erreicht (Blattknoten).

Answer 3

Während die STL komplexe und präzise Mechanismen hat, dies zu tun, es ist ein sehr schnelles rodet, um die Produktivität eine manuelle Schleife über einen Behälter zu verwenden, nur um zu lernen, so etwas wie:

Tree::value_type total = Tree::value_type(); 
for (Tree::const_iterator i = tree.begin(); i != tree.end(); ++i) 
    total += *i; 

Dies setzt voraus, die Binärdatei tree ist eine STL :: map, oder falls nicht, stellst du ein Iteratorkonzept für deine eigene Implementierung zur Verfügung ....

Answer 4

Verwende eine der Tree Traversal Techniken (In-Order, Vorbestellung, Nachbestellung) um jeden Knoten zu besuchen und die Summe in einer Variablen zu speichern.

Sie können weitere Details zu dem Baumdurchlauf finden in dieser wiki

Answer 5

Traverse Baum in beliebiger Reihenfolge (pre, Post, im). Anstatt den Knoten zu drucken, berechnen Sie die Summe.

void sum(Node* root, int& total) 
{ 
    if(root == NULL) 
    { 
     return; 
    }  
    sum(root->left, total);  
    total = total + root->value; 
    sum(root->right, total); 
} 
int main() 
{ 
    int total =0; 
    sum(root,total); 
    cout << total; 
} 

Answer 6

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

Answer 7

  50 
    / \ 
     30  70 
    /\ /\ 
    20 40 60 80 

kehrt: 350

int Sum(struct node *root) 
    { 

     if(root->left == NULL && root->right== NULL) 
      return root->key; 

     int lvalue,rvalue; 


     lvalue=Sum(root->left); 
     rvalue=Sum(root->right); 

     return root->key+lvalue+rvalue; 

    }