C++：二叉树所有节点值的总和
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/3784411/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
C++: Sum of all node values of a binary tree
提问by csguy11
I'm preparing for a job interview. I was stuck at one of the binary tree questions:
我正在准备工作面试。我被困在二叉树问题之一：
How can we calculate the sum of the values present in all the nodes of a binary tree?
我们如何计算二叉树所有节点中存在的值的总和？
回答by paxdiablo
The elegant recursive solution (in pseudo-code):
优雅的递归解决方案（在伪代码中）：
def sum (node):
if node == NULL:
return 0
return node->value + sum (node->left) + sum (node->right)
then just use:
然后只需使用：
total = sum (root)
This correctly handles the case of a NULL root node.
这可以正确处理 NULL 根节点的情况。
And if you want to see it in action in C++, here's some code using that algorithm. First, the structure for a node and the sumfunction:
如果你想在 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);
}
Then the code below is a test harness code for inserting nodes:
那么下面的代码就是一个用于插入节点的测试工具代码：
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;
}
And, finally, the main function for constructing the following tree, one that covers all of the valid possibilities (empty node, node with two children, node with no children, node with one right child and node with one left child):
最后，构建以下树的主要功能，一个涵盖所有有效可能性（空节点，有两个孩子的节点，没有孩子的节点，有一个右孩子的节点和有一个左孩子的节点）：
10
/ \
7 20
/ \
3 99
\
4
\
6
The code to construct that tree and report the sum at various points is shown here:
构建该树并报告各个点的总和的代码如下所示：
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 outputs (the correct):
这输出（正确的）：
0
10
37
149
回答by Manoj R
Traverse the tree in any order (pre, post, in). Instead of printing the node calculate the total.
以任何顺序（前、后、中）遍历树。而不是打印节点计算总数。
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;
}
回答by John Kugelman
The same way you search the tree, or display each node, or any other tree-wide operation: visit the current node, visit the left sub-tree (recursively), and visit the right sub-tree (recursively).
与搜索树或显示每个节点或任何其他树范围操作的方式相同：访问当前节点，访问左子树（递归），并访问右子树（递归）。
Essentially, something like this:
本质上，是这样的：
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;
}
Because of the ifchecks the recursion will eventually bottom out when it reaches nodes with no left or right children (leaf nodes).
由于if检查，当递归到达没有左或右孩子的节点（叶节点）时，它最终会触底。
回答by Tony Delroy
While the STL has more complex and concise mechanisms for doing this, it's a very fast rode to productivity just to learn to use a manual loop over a container, something like:
虽然 STL 有更复杂和简洁的机制来执行此操作，但仅学习在容器上使用手动循环就可以非常快速地提高生产力，例如：
Tree::value_type total = Tree::value_type();
for (Tree::const_iterator i = tree.begin(); i != tree.end(); ++i)
total += *i;
This assumes your binary tree is a STL::map, or if not you'll provide an iterator concept for your own implementation....
这假设您的二叉树是 STL::map，否则您将为您自己的实现提供迭代器概念......
回答by aeh
回答by Andrew Watson
50 / \ 30 70 / \ / \ 20 40 60 80returns:350
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;
}
回答by Antoniet Ama Aggrey
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;
}
