इस समस्या में, हमें एक पेड़ दिया जाता है और हमारा काम रिकर्सन का उपयोग करके पेड़ के आकार की गणना करने के लिए एक प्रोग्राम बनाना है।
पेड़ का आकार पेड़ में मौजूद नोड्स की कुल संख्या है।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
उपरोक्त पेड़ का आकार 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