1

我正在尝试创建一个函数来查找树节点内某些数据的平均值。问题是，每个节点都包含两条数据，并且与其他 BST 不同，构建它的主要数据是一个字符串。在树中找到基于数字的元素的平均值对我来说不是问题，但是由于每个节点都包含一个字符串（一个人的名字）和一个看似随机的数字（这个人的权重），所以这棵树实际上是完整的混乱，我不知道如何处理它。这是我的节点，所以你明白我的意思：

struct Node {
    string name;
    double weight;
    Node* leftChild;
    Node* rightChild;
};
Node* root;

这是其多个阶段之一的功能：

 // This isn't what I'm actually using so don't jump to conclusions
 double nameTree::averageWeight(double total, double total, int count) const
 {
     if (parent != NULL)
     {      //nonsense, nonsense
        averageWeight(parent->leftChild, total, count);
        averageWeight(parent->rightChild, total, count);
        count++;                                 
        total = total + parent->weight;      
        return total;
     }
     return (total / count);
}

为了遍历这棵树，我尝试了一些递归，但是每次我设法对所有内容进行计数和总计时，都会出现一些问题，并且每次都会执行 return(total/count) 。我还尝试通过遍历树并将权重添加到数组来实现数组，但这不起作用，因为返回和递归受到干扰，或者其他什么。

就因为我知道有人会问，是的，这是为了学校作业。但是，这是一个类中的 18 个函数中的一个，所以我并不要求任何人为我做这件事。我已经使用这个功能几个小时了，我整晚都没有睡，我的大脑很痛，所以任何帮助都将不胜感激！

4

2 回答 2

2

您可以尝试以下方法：

    //total number of tree nodes
static int count=0;


 // Calculate the total sum of the weights in the tree 
double nameTree::calculateWeight(Node *parent)   
{   
    double total=0;

    if (parent != NULL)       
    {      
        //nonsense, nonsense    
        //Calculate total weight for left sub-tree
        total+=calculateWeight(parent->leftChild); 
        //Calculate weight for right sub-tree
        total+=calculateWeight(parent->rightChild);  
        //add current node weight
        total+=parent->weight;                                                       
    } 
    count++;   
    //if it is a leaf it will return 0
    return total;   
}  

double averageWeight()
{
    double weightSum;

    weightSum=calculateWeight();

    if(count!=0)
        return (weightSum/count);
    else
    {
        cout<<"The tree is empty";
        return 0;
    }
}

我这里没有编译器，但我相信它可以工作。

于 2012-04-20T12:41:15.150 回答
0

要计算平均值，您需要两个数字：总值和集合中元素的数量。您需要提供一个函数（递归可能是最简单的），它将遍历树并返回pair<double,int>带有这些值的 a 或修改作为引用传递的一些参数以存储这两个值。

在您的代码中，averageWeight返回 a double，但是当您递归调用它时，您会忽略（丢弃）结果。参数通过count副本传递，这意味着调用者将看不到递归调用中应用的修改（然后不知道parent->weight应该对结果加权多少。

这应该足以让你开始。

于 2012-04-20T12:29:25.833 回答