Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में सतत ट्री


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

यदि हम रूट से लीफ तक के पथ पर किसी भी नोड को चुनते हैं, तो

|नोड का वजन - बाएं चाइल्ड नोड का वजन| = |बाएं चाइल्ड नोड का वजन - नोड का वजन| = 1, यह दाएं चाइल्ड के लिए भी सही है

|नोड का वजन - दाएं चाइल्ड नोड का वजन| = |दाएं चाइल्ड नोड का वजन - नोड का वजन| = 1

आरेख

C++ में सतत ट्री

आइए उदाहरणों से समझते हैं।

नीचे दिया गया ट्री सतत है क्योंकि पैरेंट नोड्स और उनके चाइल्ड के बीच निरपेक्ष अंतर हमेशा 1 है।

C++ में सतत ट्री

नीचे दिया गया ट्री सतत ट्री होने के योग्य नहीं है।

C++ में सतत ट्री

ट्री के सतत होने की जांच करने का एल्गोरिदम

  • यदि रूट NULL है, तो 1 लौटाएं।
  • यदि यह एक लीफ नोड है, तो 1 लौटाएं क्योंकि ट्री उस पथ तक सतत रहा है तभी लीफ नोड पहुंचा।
  • यदि बायां उपट्री खाली है तो वर्तमान नोड की दाएं चाइल्ड के साथ सततता की जांच करें (वजन का निरपेक्ष अंतर गणना करें) और दाएं उपट्री के लिए रिकर्सिव रूप से जारी रखें।
  • यदि दायां उपट्री खाली है तो वर्तमान नोड की बाएं चाइल्ड के साथ सततता की जांच करें (वजन का निरपेक्ष अंतर गणना करें) और बाएं उपट्री के लिए रिकर्सिव रूप से जारी रखें।
  • अन्यथा बाएं और दाएं चाइल्ड के वजन के साथ निरपेक्ष अंतर की गणना करें और बाएं और दाएं उपट्री के लिए रिकर्सिव रूप से जारी रखें।

स्यूडोकोड

// फ़ंक्शन ट्री सतत है या नहीं जांचने के लिए struct btreeNode{ int data; btreeNode* left, * right; }; int isContinuous(btreeNode *root){ // यदि नोड NULL है तो 1 लौटाएं, निकास की स्थिति if (root == NULL) return 1; //यदि लीफ नोड पहुंच गया तो ट्री इस पथ के दौरान सतत होना चाहिए if (root->left == NULL && root->right == NULL) return 1; // यदि कोई बायां चाइल्ड नहीं if (root->left == NULL) return (abs(root->data - root->right->data) == 1) && isContinuous(root->right); // यदि कोई दायां चाइल्ड नहीं if (root->right == NULL) return (abs(root->data - root->left->data) == 1) && isContinuous(root->left); // निरपेक्ष अंतर की गणना return abs(root->data - root->left->data)==1 && abs(root->data - root->right->data)==1 && isContinuous(root->left) && isContinuous(root->right); }

  1. बाइनरी ट्री के दो नोड्स के बीच की दूरी खोजें C++ में बाइनरी ट्री के दो नोड्स के बीच की दूरी खोजें C++ में

    मान लीजिए हमारे पास कुछ नोड्स के साथ एक बाइनरी ट्री है। हमें दो नोड्स u और v के बीच की दूरी खोजनी है। मान लीजिए ट्री नीचे जैसा है - अब (4, 6) के बीच की दूरी = 4, पथ की लंबाई 4 है, (5, 8) के बीच की लंबाई = 5 आदि। इस समस्या को हल करने के लिए, हम LCA (निम्नतम सामान्य पूर्वज) खोजेंगे, फिर LCA से दो नोड

  1. C++ में बाइनरी ट्री में चिल्ड्रन सम गुण की जांच C++ में बाइनरी ट्री में चिल्ड्रन सम गुण की जांच

    मान लीजिए हमारे पास एक बाइनरी ट्री है। बाइनरी ट्री वैध है जब यह निम्न गुण को पूरा करता है।प्रत्येक नोड में डेटा मान अपने बाएं और दाएं बच्चों के मानों के योग के समान होना चाहिए। यदि किसी भी तरफ कोई बच्चे नहीं हैं, तो इसे 0 माना जाएगा।मान लीजिए एक ट्री नीचे जैसा मौजूद है, जो दिए गए गुण को पूरा करता है

  1. C++ में बाइनरी ट्री का एंटी-क्लॉकवाइज स्पाइरल ट्रैवर्सल C++ में बाइनरी ट्री का एंटी-क्लॉकवाइज स्पाइरल ट्रैवर्सल

    बाइनरी ट्री का एंटी-क्लॉकवाइज स्पाइरल ट्रैवर्सल एक ट्री के तत्वों को इस तरह से पार करना है कि यदि पार किया जाए तो वे एक स्पाइरल बनाते हैं लेकिन रिवर्स ऑर्डर में। निम्नलिखित आकृति दिखाती है कि बाइनरी ट्री का एंटी-क्लॉकवाइज स्पाइरल ट्रैवर्सल कैसे होता है। बाइनरी ट्री के स्पाइरल ट्रैवर्सल के लिए परिभ