C ++：二叉树的所有节点值的总和 [英] C++: Sum of all node values of a binary tree

问题描述

我正在准备工作面试。我陷入了二叉树问题之一：

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?

推荐答案

优雅的递归解决方案（使用伪代码）：

The elegant recursive solution (in pseudo-code):

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

然后只需使用：

total = sum (root)

此正确处理

如果您想在C ++中看到它的实际作用，可以使用以下代码该算法。首先，节点的结构和 sum 函数：

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 sum function:

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

输出（正确）：

0
10
37
149

这篇关于C ++：二叉树的所有节点值的总和的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！