Ответ 1
Элегантное рекурсивное решение (в псевдокоде):
def sum (node):
if node == NULL:
return 0
return node->value + sum (node->left) + sum (node->right)
то просто используйте:
total = sum (root)
Это правильно обрабатывает случай NULL root node.
И если вы хотите увидеть его в действии на С++, здесь некоторый код использует этот алгоритм. Во-первых, структура для функции node и 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;
}
И, наконец, главная функция для построения следующего дерева, которая охватывает все допустимые возможности (пустой node, node с двумя дочерними элементами node без детей, node с одним правом child и 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