트리의 크기를 계산하는 프로그램 작성 - C++의 재귀

이 문제에서는 나무가 주어지고 우리의 임무는 재귀를 사용하여 나무의 크기를 계산하는 프로그램을 만드는 것입니다.

트리의 크기는 트리에 존재하는 총 노드 수입니다.

문제를 이해하기 위해 예를 들어보겠습니다.

위 트리의 크기는 5입니다.

트리의 크기를 찾으려면 왼쪽 하위 트리와 오른쪽 하위 트리의 크기를 추가한 다음 1씩 증가시켜야 합니다. 트리의 왼쪽 및 오른쪽 하위 트리 모두에 대해 재귀 함수가 호출됩니다. 하위 트리가 없으면 0을 반환합니다.

이 방법을 사용하여 해결된 위의 예

나무의 크기를 구하려면

크기(3) =크기(5) + 크기(7) + 1

크기(3) =(크기(1) + 크기(9) + 1) + 1 + 1

크기(3) =(1 + 1 + 1) + 1 + 1

크기(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