找到二叉樹的平均值C++

所以我想寫一個遞歸函數來返回在C++中的值的二叉樹的平均值。這是我有，這是行不通的：找到二叉樹的平均值C++

double avg(bNode* root) 
{ 
    if(!root) return 0; 
    int sum = avg(root->left) + avg(root->right) + root->value; 
    if(root->left && root->right) return sum/3; 
    else if(!root->left && !root->right) return sum; 
    else return sum/2; 
}

感謝您的幫助。

來源

2013-01-25 Nick Sinklier

你嘗試過在紙上畫一個簡單的樹，從手工嘗試你的算法？ – Cameron

它顯示任何錯誤？你可以發佈你的結果 – user1954492

考慮樹根節點的值爲1，左邊是2，左邊 - >左邊是3.可以很容易地驗證平均值是2.然而，你的函數將產生1.75。我不認爲這很容易做到遞歸，可以考慮使用累加器。 – Betagan

這是一個非常簡單的例子，應該說明爲什麼你要計算不是一個平均值：

在「12」節點的平均值將(12 + 20)/2 = 16。

然後在10節點處，平均值將是(4 + 10 + 16)/3 = 10。

但是，平均值確實是11.5。

問題是平均值的平均值不等於一個大的正確的平均值。在每個級別，您必須將平均值乘以用於計算它的節點數（即總和），然後再用於下一次平均計算。

更簡單的方法是計算總和，然後除以樹中節點的數量。

一些僞代碼一個技術要做到這一點是：

class accumulator 
{ 
    int sum = 0; 
    int count = 0; 

    // implement the obvious operator+ 
}; 

accumulator avg(bNode* root) 
{ 
    if(!root) return <empty accumulator> 
    return <recursive children> + <self>; 
} 

int main() 
{ 
    accumulator acc = avg(root); 
    // ..calculate average.. 
}

來源

2013-01-25 04:14:10 JaredC

找到二叉樹的平均值C++

回答

相關問題