इस ट्यूटोरियल में, हम सीखेंगे कि बाइनरी ट्री का घनत्व एक ही ट्रैवर्सल में कैसे खोजा जाए।
बाइनरी ट्री का घनत्व ट्री के आकार को ट्री की ऊंचाई से विभाजित करके प्राप्त किया जाता है।
बाइनरी ट्री का आकार दिए गए बाइनरी ट्री में मौजूद नोड्स की कुल संख्या है।
बाइनरी ट्री की ऊंचाई रूट नोड से लीफ नोड की अधिकतम गहराई है।
समस्या को हल करने के चरण देखते हैं।
डमी डेटा के साथ बाइनरी ट्री इनिशियलाइज़ करें।
ट्री का आकार और ऊंचाई खोजें।
ट्री की ऊंचाई को रिकर्सिवली गिनें।
यदि लेफ्ट ट्री की ऊंचाई राइट ट्री की ऊंचाई से अधिक है तो लेफ्ट ट्री की ऊंचाई लौटाएं अन्यथा राइट ट्री की ऊंचाई लौटाएं और दोनों में 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
निष्कर्ष
यदि ट्यूटोरियल में आपके कोई प्रश्न हैं, तो उन्हें कमेंट सेक्शन में बताएं।
