二进制搜索树C ++中的计算平均值

Question

我对如何在整数的二进制搜索树中查找整数的平均值感到困惑。

如果树为空，则应返回0。

到目前为止，我的代码是：

//Node class
class Node
{
public:
private:
    int data;
    Node* left;
    Node* right;
friend class BST;
};

Binary Search Tree class
class BST
{
public:
    Node* insert(int value, Node* root)
    {
        if (root == NULL)
        {
            root = new Node;
            root->data = value;
            root->left = root->right = NULL;
        }
        else if (value < root->data)
        {
            root->left = insert(value, root->left);
        }
        else if (value > root->data)
        {
            root->right = insert(value, root->right);
        }
        return root;
    }
    void insert(int x)
    {
        root = insert(x, root);
    }
    int sum(Node* root) {
        if (root == NULL)
        {
            return 0;
        }
        return root->data + sum(root->right) + sum(root->left);
    }
    int count(Node* root)
    {
        if (root == NULL)
        {
            return 0;
        }
        return count(root->right) + count(root->left) + 1;
    }
    double average(Node* root) {
        return (double)sum(root) / count(root);
    }

private:
    Node* root;
};

int main()
{
    BST tree;
    tree.insert(20);
    tree.insert(25);
    tree.insert(15);
    tree.insert(10);
    tree.insert(30);
    tree.insert(0);

    cout << tree.average(root) << endl; // this gives an error

}

我添加了一些辅助函数，但也请告知它们是否有误。。

当我调用average（）函数时，它给了我一个错误。我想我需要sum（）函数和count（）函数。并且，如果count（）为0，则平均值为0。然后average（）函数将仅对求和值求和。

Answer 1

您的average函数根本不需要参数。您可以简单地做：

double average() 
{
  return static_cast<double>(sum(root)) / count(root);  // uses the actual root
}

并这样称呼它：

cout << tree.average() << endl;

Answer 2

我要这样做的方法是通过使包装函数调用递归函数。递归函数可以具有两个变量，这些变量通过引用传递总和和金额。这样，您只需要遍历两个值一次。

这里是包装函数：

double average(node * root) {
    if(!root) {
        return 0;
    }

    int sum = 0;
    int amount = 0;

    averageRecursive(root, sum, amount);

    cout << "The average is: " << (double)sum / amount << endl;
}

以及正在被调用的递归函数：

void averageRecursive(node * root, int &sum, int &amount) {
    if(!root)
        return;

    countAverage(root->left, sum, amount);

    sum += root->data;
    ++amount;

    countAverage(root->right, sum, amount);
}

然后您将以main从tree.average()调用它，它将返回平均值。