सी++ में एक ट्रैवर्सल में बाइनरी ट्री का घनत्व?

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

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

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

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

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

हमारा वृक्ष घनत्व (नोड * रूट) फ़ंक्शन रूट नोड लेता है और जांचता है कि यह शून्य है या नहीं। यह तब आकार चर घोषित करता है और इसे 0 पर सेट करता है। ऊंचाई और आकार (रूट, आकार) फ़ंक्शन का वापसी मान ऊंचाई चर को सौंपा गया है। फिर ऊंचाई और आकार के बीच किए गए फ्लोट डिवीजन को वापस कर दिया जाता है।

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

इसके बाद, ऊंचाई और आकार (नोड * नोड, int और आकार) रूट नोड और आकार चर का संदर्भ लेता है। यदि रूट नोड शून्य है, तो 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