C++: сумма всех значений узлов двоичного дерева

Question

Я готовлюсь к собеседованию. Я застрял в одном из вопросов двоичного дерева:

Как мы можем вычислить сумму значений, присутствующих во всех узлах двоичного дерева?

Answer 1

Элегантный рекурсивного решения (в псевдокоде):

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

затем просто использовать:

total = sum (root) 

Это правильно обрабатывает случай корневого узла NULL.

---

И если вы хотите увидеть его в действии на C++, вот какой код использует этот алгоритм. Во-первых, структура узла и sum функции:

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

Затем код ниже тест Жгут код для вставки узлов:

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

И, наконец, основной функцией для построения следующего дерево, которое охватывает все допустимые возможности (пустой узел, узел с двумя дочерними узлами, узел без детей, узел с одним правым дочерним узлом и узел с одним левым дочерним элементом):

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

код для построения этого дерева и сообщить сумму в различных точках показано здесь:

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

Воспроизводит (правильный):

0 
10 
37 
149 

Answer 2

Точно так же вы ищите дерево или показываете каждый узел или любую другую операцию по всему дереву: посетите текущий узел, перейдите в левое поддерево (рекурсивно) и перейдите к правильному поддереву (рекурсивно) ,

По сути, что-то вроде этого:

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

Из-за if проверок рекурсии в конечном итоге дно, когда он достигает вершины с не левыми или правыми детьми (листовые узлами).

Answer 3

Хотя STL имеет более сложные и краткие механизмы для этого, это очень быстро ехала производительность просто научиться использовать ручной цикл над контейнером, что-то вроде:

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

Это предполагает бинарное tree - это STL :: map, или если нет, вы предоставите концепцию итератора для своей собственной реализации.

Answer 4

Используйте одну из методов обхода дерева (в порядке, предзаказ, пост-порядок) для посещения каждого узла и хранения суммы в переменной.

Вы можете найти более подробную информацию о обходе дерева в этом wiki

Answer 5

траверс дерева в любом порядке (до, после, в). Вместо того, чтобы печатать узел, вычислить общее количество.

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 

возвращается: 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; 

    }