सी ++ में ओ (एन) [एक नई विधि] में बाइनरी ट्री का व्यास?

बाइनरी ट्री का व्यास प्रत्येक नोड के लिए (बाएं_ऊंचाई + दायां_ऊंचाई + 1) है। तो इस विधि में हम प्रत्येक नोड के लिए (बाएं_ऊंचाई + दायां_ऊंचाई + 1) की गणना करेंगे और परिणाम अपडेट करेंगे। यहाँ समय जटिलता O(n) रहती है।

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

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

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

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

व्यास (नोड * रूट) फ़ंक्शन रूट नोड लेता है और जांचता है कि रूट नोड शून्य है या नहीं। फिर हम INT_MIN मान के साथ ans वेरिएबल को परिभाषित करते हैं। ऊंचाई (रूट, उत्तर) से वापसी मूल्य ऊंचाई_ऑफ_ट्री चर में संग्रहीत किया जाता है। उत्तर फ़ंक्शन से वापस आ जाता है।

int diameter(Node* root){
    if (root == NULL)
        return 0;
    int ans = INT_MIN;
    int height_of_tree = height(root, ans);
    return ans;
}

ऊंचाई (नोड * रूट, int&ans) फ़ंक्शन संदर्भ द्वारा रूट नोड और ans चर लेता है। इसके बाद हम पेड़ पर प्रत्येक उपट्री लंबाई की गणना करने के लिए इनऑर्डर ट्रैवर्सल करते हैं और प्रत्येक रिकर्सिव कॉल पर ans के maxValue को दूसरे पैरामीटर के रूप में पास किया जाता है। उत्तर अधिकतम (उत्तर, 1 + बाएँ_ऊँचाई + दाएँ_ऊँचाई) है।

उदाहरण

आइए ओ (एन) विधि में बाइनरी ट्री के व्यास को खोजने के लिए निम्नलिखित कार्यान्वयन को देखें।

#include <iostream>
using namespace std;
struct Node {
    int data;
    Node* leftChild, *rightChild;
};
struct Node* newNode(int data){
   struct Node* newNode = new Node;
   newNode->data = data;
   newNode->leftChild = newNode->rightChild = NULL;
   return (newNode);
}
int height(Node* root, int& ans){
   if (root == NULL)
      return 0;
   int left_height = height(root->left, ans);
   int right_height = height(root->right, ans);
   ans = max(ans, 1 + left_height + right_height);
   return 1 + max(left_height, right_height);
}
int diameter(Node* root){
   if (root == NULL)
      return 0;
   int ans = INT_MIN;
   int height_of_tree = height(root, ans);
   return ans;
}
int main(){
    struct Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);
    printf("Diameter is %d\n", diameter(root));
    return 0;
}

आउटपुट

उपरोक्त कोड निम्न आउटपुट उत्पन्न करेगा -

Diameter is 4