c++ - 二叉搜索树中每个分支的总和

Question

我的任务是使用递归找到二叉搜索树中每个分支上所有节点的总和，并将它们与用户输入值进行比较。如果用户输入值与其中一个分支的总和相匹配，则该函数应返回 true。

也就是说，32+24+21+14之和=91。 32+24+28+25的总和=109。 32+24+28+31=115等的总和。我尝试了很多不同的方法，但似乎无法弄清楚如何准确遍历每个分支。到目前为止，我只能遍历并找到最左边分支的总和。

我正在使用从用户输入值中减去每个节点的方法。如果叶节点处的值达到 0，则显然用户输入与树上该分支的节点和相匹配。

对我来说特别困难的点是分支 fork 的时候，比如在节点 [24] 和 [28] 处。我显然犯了一些非常简单的错误，但我想不通。

下面是我到目前为止编写的精简代码，采用两个伴随方法的形式(也是作业所必需的)。

public:
bool findBranchSum1(int value) throw (InvalidTreeArgument) {
    if (root == nullptr)
        throw InvalidTreeArgument();
    return(findBranchSum(root, value));
}

private:
bool findBranchSum(NodePtr node, int value) throw (InvalidTreeArgument)
{
    bool result = false;
    if (root == nullptr)
        throw InvalidTreeArgument();

    value -= node->getElement(); //subtract current node from user-input value. 

    cout << "Current Value = " << value << endl; //help track value changes

    if (node->getLeftSide() == nullptr && node->getRightSide() == nullptr)
        {
            if (value == 0)
            {
                result = true;
                return(true);
            }
            else
                return(false);
        }
    else
    {
        if (node->getLeftSide() != nullptr)
        {
            node = node->getLeftSide(); //advance to next Left node
            result = findBranchSum(node, value); //recursive call using new node
        }
        if (node->getRightSide() != nullptr)
        {
            node = node->getRightSide(); //advance to next Right node
            result = findBranchSum(node, value); //recursive call using new node
        }
        return(result);
    }
}

我哪里做错了，我该如何修正我的代码以找到树上每个分支的总和？先感谢您。对于格式中的任何错误或信息缺失，我深表歉意。

Answer 1

这是错误的:

if (node->getLeftSide() != nullptr)
{
  node = node->getLeftSide(); //advance to next Left node
  result = findBranchSum(node, value); //recursive call using new node
}
if (node->getRightSide() != nullptr)
{
  node = node->getRightSide(); //advance to next Right node
  result = findBranchSum(node, value); //recursive call using new node
}

因为你向左移动，然后向左移动到右分支(节点被你的赋值改变)，如果它存在!更改为:

if (node->getLeftSide() != nullptr)
{
  result = findBranchSum(node->getLeftSide(), value);
}
if (node->getRightSide() != nullptr)
{
  result = findBranchSum(node->getRightSide(), value);
}

你的返回值管理也坏了，改成:

if (node->getLeftSide() != nullptr)
{
  result = findBranchSum(node->getLeftSide(), value);
}
if (!result && node->getRightSide() != nullptr) // cut exploration if previous was correct...
{
  result = findBranchSum(node->getRightSide(), value);
}
return result;

如果您需要停在第一个正确的分支。