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