ツリーのサイズを計算するプログラムを作成する-C++での再帰

この問題では、ツリーが与えられ、再帰を使用してツリーのサイズを計算するプログラムを作成することがタスクです。

ツリーのサイズは、ツリーに存在するノードの総数です。

問題を理解するために例を見てみましょう

上記の木のサイズは5です。

ツリーのサイズを見つけるには、左のサブツリーと右のサブツリーのサイズを追加してから、1ずつインクリメントする必要があります。再帰関数は、ツリーの左と右の両方のサブツリーに対して呼び出されます。また、サブツリーが見つからない場合は0を返します。

この方法を使用して解決された上記の例

木のサイズを見つけるには、

size（3）=size（5）+ size（7）+ 1

size（3）=（size（1）+ size（9）+ 1）+ 1 + 1

size（3）=（1 + 1 + 1）+ 1 + 1

size（3）=5

ソリューションの動作を説明するプログラム

例

#include <iostream>
using namespace std;
class node {
   public:
   int data;
   node* left;
   node* right;
};
node* insertNode(int data) {
   node* Node = new node();
   Node->data = data;
   Node->left = NULL;
   Node->right = NULL;
   return(Node);
}
int findSize(node* node) {
   if (node == NULL)
      return 0;
   else
      return(findSize(node->left) + 1 + findSize(node->right));
}
int main() {
   node *root = insertNode(6);
   root->left = insertNode(3);
   root->right = insertNode(7);
   root->left->left = insertNode(1);
   root->left->right = insertNode(5);
   root->right->left = insertNode(2);
   cout<<"The size of the given tree is "<<findSize(root);
   return 0;
}

出力

The size of the given tree is 6