C++ में एक ही ट्रैवर्सल में बाइनरी ट्री का घनत्व (Density of Binary Tree)

बाइनरी ट्री का घनत्व इसके आकार को इसकी ऊंचाई से विभाजित करके गणना किया जाता है। बाइनरी ट्री घनत्व = आकार/ऊंचाई।

आइए पहले उस स्ट्रक्ट को परिभाषित करें जो एक ट्री नोड को दर्शाता है जिसमें डेटा और इसके बाएं और दाएं चाइल्ड नोड होते हैं। यदि यह बनाया जाने वाला पहला नोड है तो यह रूट नोड है अन्यथा चाइल्ड नोड।

struct Node { 
    int data; 
    struct Node *leftChild, *rightChild; 
};

इसके बाद हम createNode(int data) फंक्शन बनाते हैं जो एक int मान लेता है और इसे नोड के डेटा सदस्य को असाइन करता है। फंक्शन बने हुए स्ट्रक्ट Node का पॉइंटर वापस करता है। साथ ही, नव निर्मित नोड के बाएं और दाएं चाइल्ड को null पर सेट किया जाता है।

Node* createNode(int data){ 
    Node* node = new Node; 
    node->data = data; 
    node->leftChild = node->rightChild = NULL; 
    return node; 
}

हमारा treeDensity(Node *root) फंक्शन रूट नोड लेता है और जांचता है कि यह null है या नहीं। यह फिर size वेरिएबल घोषित करता है और इसे 0 पर सेट करता है। heightAndSize(root, size) फंक्शन का वापसी मान height वेरिएबल को असाइन किया जाता है। ऊंचाई और आकार के बीच फ्लोट विभाजन फिर वापस किया जाता है।

float treeDensity(Node* root){ 
    if (root == NULL) 
        return 0; 
    int size = 0; 
    int height = heightAndSize(root, size); 
    return (float)size / height; 
}

अगला, heightAndSize(Node* node, int &size) रूट नोड और size वेरिएबल का रेफरेंस लेता है। यदि रूट नोड null है तो 0 वापस किया जाता है। प्रत्येक सबट्री की ऊंचाई रिकर्सिव रूप से गणना की जाती है और प्रत्येक रिकर्सन पर आकार बढ़ाया जाता है। हम फिर बाएं या दाएं सबट्री में से बड़े को वापस करते हैं।

int heightAndSize(Node* node, int &size){ 
    if (node==NULL) 
        return 0; 
    int left = heightAndSize(node->leftChild, size); 
    int right = heightAndSize(node->rightChild, size); 
    size++; 
    return (left > right) ? ++left : ++right; 
}

उदाहरण

एक ही ट्रैवर्सल में बाइनरी ट्री घनत्व खोजने के लिए निम्नलिखित कार्यान्वयन देखें:

#include <iostream> 
using namespace std; 

struct Node{ 
    int data; 
    Node *leftChild, *rightChild; 
}; 

Node* createNode(int data){ 
    Node* node = new Node; 
    node->data = data; 
    node->leftChild = node->rightChild = NULL; 
    return node; 
} 

int heightAndSize(Node* node, int &size){ 
    if (node==NULL) 
        return 0; 
    int left = heightAndSize(node->leftChild, size); 
    int right = heightAndSize(node->rightChild, size); 
    size++; 
    return (left > right) ? ++left : ++right; 
} 

float treeDensity(Node* root){ 
    if (root == NULL) 
        return 0; 
    int size = 0; 
    int height = heightAndSize(root, size); 
    return (float)size / height; 
} 

int main(){ 
    Node* root = createNode(7); 
    root->leftChild = createNode(9); 
    root->rightChild = createNode(11); 
    cout<< "The density of the above given binary tree is "<<treeDensity(root); 
    return 0; 
}

आउटपुट

उपरोक्त कोड निम्नलिखित आउटपुट देगा:

The density of the above given binary tree is 1.5