再帰C++を使用してBSTのノード数を計算する

Question

再帰を使用してBST内のノードの数を調べようとしています。ここに私のコードです

struct Node{ 
    int key; 
    struct Node* left; 
    struct Node* right; 

    Node(){ 
     int key = 0; 
     struct Node* left = nullptr; 
     struct Node* right = nullptr; 
    } 
}; 

src_rootはツリーのルートノードのアドレスです。

int BST::countNodes(Node* src_root, int sum){ 

     if((src_root==root && src_root==nullptr) || src_root==nullptr) 
      return 0; 
     else if(src_root->left==nullptr || src_root->right==nullptr) 
      return sum; 
     return countNodes(src_root->left, sum + 1) + countNodes(src_root->right, sum + 1) + 1; 
     } 

しかし、私のコードは3つのノードがある場合にのみ動作するようです。 3以上のものは間違った答えを与える。何が問題なのかを教えてください。ありがとう！

Answer 1

私はC/C++で何かを作って以来、文法上の誤りがあるかもしれません。

int BST::countNodes(Node *scr_root) 
{ 
    if (scr_root == null) return 0; 
    return 1 + countNodes(scr_root->left) + countNodes(scr_root->right); 
} 

私は仕事をすると思います。

Answer 2

実装にはいくつかの論理的および構造的な問題があります。 Casperahはあなたがすでにウェブ上で見つけたと思われる「きれいな」答えをあなたに与えました（あなたがまだその研究をしていないなら、質問を投稿してはいけません）。したがって、あなたが探しているのは他の誰かの解決策ではなく、あなた自身の解決策です。

1. はなぜダウン合計ツリー渡すのですか？下位ノードは前回のカウントに気を付けるべきではありません。子どもの数を集めるのは親の仕事です。それがカスペラの答えでどのように行われたかを見てください。コードから余分なパラメータを削除します。それは単なるエラーの原因です。
2. はあなたのベースケースは、同一の偽の句を持っている：あなたは意味のある電話をかける場合src_root ==ルート& & src_root == nullptr ...、src_root ははルートと両方nullptrすることはできません。
3. なぜグローバル値、ルートと比較していますか？それぞれの呼び出しは、単に自分自身の仕事を完了して返します。コールツリーが元の呼び出しにクロールすると、ルートで呼び出された呼び出しがクロールされます。単純に呼び出しを呼び出して呼び出しプログラムに戻ります。これはではなく、の特別な場合です。
4. else句が間違っています：のいずれかがの子がnullの場合、他の子をすべて無視してこれまでのカウントのみを返します。これは、ツリーが完全に平衡し満たされない限り、間違った答えを出すことを保証します.Nレベルの合計2^N - 1ノードです。

これらの項目は、参考になる順序で修正してください。アイデアは学ぶことです。しかし、最終的なコードは、Casperahが提供した答えのように見えるはずです。