इस ट्यूटोरियल में, हम सीखेंगे कि सिंगल ट्रैवर्सल में बाइनरी ट्री का घनत्व कैसे पता करें।
बाइनरी ट्री का घनत्व पेड़ के आकार को पेड़ की ऊंचाई से विभाजित करके प्राप्त किया जाता है।
बाइनरी ट्री का आकार दिए गए बाइनरी ट्री में मौजूद नोड्स की कुल संख्या है।
बाइनरी ट्री की ऊंचाई रूट नोड से लीफ नोड की अधिकतम गहराई है।
आइए समस्या को हल करने के लिए चरणों को देखें।
-
बाइनरी ट्री डमी डेटा को इनिशियलाइज़ करें।
-
पेड़ का आकार और ऊंचाई ज्ञात कीजिए।
-
पेड़ की ऊंचाई को पुनरावर्ती रूप से गिनें।
-
बाएँ नोड ट्री की ऊँचाई लौटाएँ यदि यह दाएँ नोड ट्री ऊँचाई से अधिक है अन्यथा दाएँ नोड ट्री ऊँचाई को दोनों में जोड़कर लौटाएँ 1.
-
नोड का आकार बढ़ाएँ।
-
-
$$size\:of\:Tree\:/\:height\:of\:Tree$$ सूत्र का उपयोग करके पेड़ के घनत्व की गणना करें।
-
पेड़ का घनत्व प्रिंट करें।
उदाहरण
आइए कोड देखें।
#include<bits/stdc++.h>
using namespace std;
struct Node {
int data;
Node *left, *right;
};
Node* newNode(int data) {
Node* node = new Node;
node->data = data;
node->left = node->right = NULL;
return node;
}
int findHeightAndSizeOfTree(Node* node, int &size) {
if (node == NULL) {
return 0;
}
int leftTreeCount = findHeightAndSizeOfTree(node->left, size);
int rightTreeCount = findHeightAndSizeOfTree(node->right, size);
size++;
return (leftTreeCount > rightTreeCount) ? leftTreeCount + 1 : rightTreeCount + 1;
}
float treeDensity(Node* root) {
if (root == NULL) {
return 0;
}
int treeSize = 0;
int treeHeight = findHeightAndSizeOfTree(root, treeSize);
return (float)treeSize/treeHeight;
}
int main() {
Node* root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
root->right->left = newNode(6);
root->right->right = newNode(7);
cout << treeDensity(root) << endl;
return 0;
} आउटपुट
यदि आप उपरोक्त प्रोग्राम को निष्पादित करते हैं, तो आपको निम्न परिणाम प्राप्त होंगे।
2.33333
निष्कर्ष
यदि ट्यूटोरियल में आपके कोई प्रश्न हैं, तो उनका टिप्पणी अनुभाग में उल्लेख करें।