C++関数の独立和

Question

RBツリーのルートから距離= nにあるノードの合計値をプログラムで計算します。私はそのようなノードを見つける再帰的な関数を持っているが、私はそれらのすべてをどのように合計するか考えていない。どのように見える：

void nSum (RBTreeNode* B, int n) { 
    if (B == NULL || n < 0) 
     return; 
    if (n == 0) { 
     Integer* v = (Integer*) B->value; 
     S += v->number // there I want to make an independent sum of them 
     return; 
    } 
    nSum (B->right, n-1); 
    nSum (B->left, n-1); 
} 

私はこれにかなり新しいと私は答えが見つかりませんでした。

void nSum (RBTreeNode* B, int n, vector <int> sum) { 
    if (B == NULL || n < 0) 
     return; 
    if (n == 0) { 
     int* v = (int*) B->value; 
     sum.push_back(v->number); 
     return; 
    } 
    nSum (B->right, n-1, sum); 
    nSum (B->left, n-1, sum); 
} 

をしかし、その後合計が空

Answer 1

あなたは、このような関数を宣言する場合：

void nSum (RBTreeNode* B, int n, vector <int> sum) 

機能はあなたが合格ベクトルのコピーである取得ベクトルしたがって、nSumがベクトルを変更した場合、それはnSumを呼び出すコードのベクトルには影響しません。これは値渡しと呼ばれます。

また、渡される同じベクトルへのnSumアクセスを提供する参照渡しも可能で、nSumで行われた変更は呼び出しコードのベクトルに影響します。参照渡しの方法は次のとおりです。

void nSum (RBTreeNode* B, int n, vector <int>& sum) 

"&"に注目してください。しかし、ベクトルは必要ありません、あなただけの合計を追跡する必要があります。

void nSum (RBTreeNode* B, int n, int& sum) 

nSumが呼び出されるたびに、合計intを変更することができ、関数外の値に影響します。

Answer 2

あるこの合計は単純な再帰式（バイナリツリーの構造に多くの関係がそうであるように）で表現することができます。

は、次のことをしようとしました。

S(root, 0) = root->value; 
S(root, n) = S(root->left_child, n - 1) + S(root->right_child, n - 1); 

式から、再帰関数を2回呼び出すだけでは不十分であることがわかります。実際に結果を合計する必要があります。どの関数でも要約することができます何かを返さなければならないことを意味する：

int nSum (RBTreeNode* B, int n) { 
    // Take a stab at completing it yourself 

    return nSum(B->left, n-1) + nSum(B->right, n-1); 
}