C++: Suma wartości wszystkich węzłów drzewa binarnego

Question

Przygotowuję się do rozmowy kwalifikacyjnej. Utknąłem na jednym z pytań drzewa binarnego:

Jak możemy obliczyć sumę wartości obecnych we wszystkich węzłach drzewa binarnego?

Answer 1

The eleganckie rozwiązanie rekurencyjne (w pseudo-kod):

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

następnie wystarczy użyć:

total = sum (root) 

to poprawnie obsługuje przypadek węzła głównego NULL.

---

A jeśli chcesz zobaczyć to w akcji w C++, oto kod wykorzystujący ten algorytm. Po pierwsze, struktura dla węzła i sum funkcja:

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

Następnie poniższy kod jest kodem uprząż testy do wstawiania węzłów:

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

I wreszcie, główną funkcją konstruowania następujące drzewo, który obejmuje wszystkich ważnych możliwości (pusty węzeł, węzeł z dwójką dzieci, bez dzieci węzła, węzeł z jednym dzieckiem i prawego węzła z jednym dzieckiem lewej):

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

Kod do skonstruowania tego drzewa i zgłosić sumę w różnych punktach jest pokazany tutaj:

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

This wyjść (prawidłowa):

0 
10 
37 
149 

Answer 2

W ten sam sposób, w jaki przeszukujesz drzewo lub wyświetlasz każdy węzeł lub dowolną inną operację obejmującą cały drzewo: odwiedź bieżący węzeł, przejdź do lewego pod-drzewa (rekurencyjnie) i przejdź do prawego pod-drzewa (rekursywnie) .

Zasadniczo coś takiego:

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

powodu if kontroli rekursja ostatecznie dno, kiedy dotrze węzły bez żadnych lewych lub prawych dzieci (węzłów leaf).

Answer 3

Choć STL ma bardziej złożone i zwięzłe mechanizmy ten sposób, to bardzo szybko jechał do wydajności po prostu nauczyć się korzystać z ręczną pętlę nad pojemnikiem, coś jak:

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

Zakłada binarnym drzewo jest mapą STL :: lub, jeśli nie, przedstawisz koncepcję iteratora do własnej implementacji ...

Answer 4

Użyj jednej z technik drzewa przekrojowego (w kolejności, w przedsprzedaży, po zamówieniu) odwiedzić każdy węzeł i zapisać sumę w zmiennej.

można znaleźć więcej szczegółów na przechodzenie drzewa w tej wiki

Answer 5

Traverse drzewie w dowolnej kolejności (przed, po, w). Zamiast drukowania węzła obliczyć sumę.

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 

powraca: 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; 

    }