1

だから私は二分探索木のノード数を取得する方法に取り組んでいます、私が3つのノードを持っているとき、それは私に3を与えます、しかし私が5をするとそれは私に4を与えます、私は何を変える必要がありますか？

int BinaryTree::size(int count, Node *leaf) const
{
    if(leaf != NULL)//if we are not at a leaf
    {
        size(count + 1, leaf->getLeft());//recurisvly call the function and increment the count
        size(count + 1, leaf->getRight());
    }
    else
    {
        return count;//return the count
    }

}
4

3 に答える 3

9 
int BinaryTree::size(Node *leaf) const 
{
    if(leaf == NULL) { //This node doesn't exist. Therefore there are no nodes in this 'subtree'
        return 0;
    } else { //Add the size of the left and right trees, then add 1 (which is the current node)
        return size(leaf->getLeft()) + size(leaf->getRight()) + 1;
    }
}

これは別のアプローチですが、私はそれがあなたが持っていたものよりも読み通しやすいと思います。

于 2013-03-12T22:00:28.180 に答える
3

他の人々は、すでに正しいアルゴリズムに賛同しています。アルゴリズムが機能しない理由を説明します。

あなたのアルゴリズムの背後にあるロジックは次のようです: 実行中のカウント値を保持します。リーフが null の場合は子がないため、カウントを返します。リーフが null でない場合は、子を再帰します。

これは後回しですが。値ではなく参照でintを渡す必要があるため、nullの場合はインクリメントせず、nullでない場合はインクリメントし、再帰します。

あなたの元のアイデアはいくつかの変更を加えると機能しますが、Nick Mitchinson と arrows にはより良い方法があります。これはアルゴリズムが修正されているため、機能します。

int BinaryTree::size(Node *leaf, int& count=0) const
{
    if(leaf != NULL)//if we are not at a leaf
    {
        count++;
        size(leaf->getLeft(), count);//recurisvly call the function and increment the count
        size(leaf->getRight(), count);
    }

    return count;//return the count
}

しかし、繰り返しますが、これを書くためのより良い方法があります。そして、他の答えはそれらを示しています。

于 2013-03-12T22:14:39.597 に答える
2 
int BinaryTree::size(Node *n) const
{
    if(!n) 
        return 0;
    else
        return size(n->getLeft()) + 1 + size(n->getRight()); 
}
于 2013-03-12T22:02:55.063 に答える