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

C++ प्रोग्राम: बाइनरी ट्री में किन्हीं दो नोड्स के बीच पथ प्रिंट करना


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

C++ प्रोग्राम: बाइनरी ट्री में किन्हीं दो नोड्स के बीच पथ प्रिंट करना

उदाहरण के लिए - हम नोड 140 से 211 के बीच का पथ प्रिंट करना चाहते हैं तो इसका आउटपुट होना चाहिए -

Output: 140->3->10->211

विचार यह है कि रूट नोड्स से दो नोड्स तक के पथ ढूंढें और उन्हें दो अलग-अलग वेक्टर या सरणी में स्टोर करें जैसे path1 और path2।

अब, दो अलग-अलग मामले उत्पन्न होते हैं -

  • यदि दो नोड्स रूट नोड्स के अलग-अलग सबट्री में हैं - जब दो नोड्स अलग-अलग सबट्री में हों जैसे एक बाएं में और दूसरा दाएं में। इस मामले में, यह स्पष्ट है कि रूट नोड नोड1 से नोड2 तक के पथ के बीच में होगा। इसलिए, path1 को रिवर्स ऑर्डर में प्रिंट करें और फिर path2 को।
  • यदि नोड्स एक ही सबट्री में हैं - जब दोनों नोड्स एक ही सबट्री में हों जो बाएं सबट्री या दाएं सबट्री में से कोई भी हो सकता है। इस मामले में, आपको रूट से दो नोड्स तक के पथ का निरीक्षण करना होगा जिसमें रूट नोड से दोनों दो नोड्स के लिए सामान्य पथ का एक इंटरसेक्शन पॉइंट होगा। हमें इंटरसेक्शन पॉइंट ढूंढना होगा और ऊपर के मामले की तरह उस बिंदु से नोड्स प्रिंट करने होंगे।

एल्गोरिदम

START STEP 1-> DEFINE A struct Node    WITH int data AND Node *left, *right; STEP 2-> DEFINE A TREE STRUCTURE struct Node* tree(int data)FUNCTION bool path(Node* root, vector& arr, int x) STEP 1-> IF root IS NULL    RETURN false    END IF STEP 2-> arr.push_back(root->data)    IF root->data == x THEN       RETURN true    END IF STEP 3-> IF path(root->left, arr, x) || path(root->right, arr, x) THEN,    RETURN true STEP 4-> arr.pop_back()    return false END FUNCTION FUNCTION void printPath(Node* root, int n1, int n2) STEP 1-> DEFINE A vector<int> path1 STEP 2-> DEFINE A vector<int> path2 STEP 3-> CALL FUNCTION path(root, path1, n1) STEP 4-> CALL FUNCTION path(root, path2, n2) STEP 5-> DEFINE AND SET intersection = -1, i = 0, j = 0 STEP 6-> LOOP WHILE i != path1.size() || j != path2.size()    IF i == j && path1[i] == path2[j]       INCREMENT i BY 1       INCREMENT j BY 1    ELSE       SET intersection = j - 1       BREAK;    END IF END WHILE STEP 7-> LOOP FOR i = path1.size() – 1 AND i > intersection AND i--PRINT path1[i]    END FOR STEP 8-> LOOP FOR i = intersection AND i < path2.size() AND i++    PRINT path2[i] END FOR

उदाहरण

#include <bits/stdc++.h> using namespace std; // structure of a node of binary tree struct Node {    int data;    Node *left, *right; }; struct Node* tree(int data){    struct Node* newNode = new Node;    newNode->data = data;    newNode->left = newNode->right = NULL;    return newNode; } bool path(Node* root, vector<int>& arr, int x){    if (!root)       return false;    // push the node's value in 'arr'    arr.push_back(root->data);    // if it is the required node    // return true    if (root->data == x)       return true;    if (path(root->left, arr, x) || path(root->right, arr, x))       return true;    arr.pop_back();    return false; } // Function to print the path between // any two nodes in a binary tree void printPath(Node* root, int n1, int n2){    // vector to store the path    vector<int> path1;    vector<int> path2;    path(root, path1, n1);    path(root, path2, n2);    int intersection = -1;    int i = 0, j = 0;    while (i != path1.size() || j != path2.size()) {       if (i == j && path1[i] == path2[j]) {          i++;          j++;       } else {          intersection = j - 1;          break;       }    }    // Print the required path    for (int i = path1.size() - 1; i > intersection; i--)       cout << path1[i] << " ";    for (int i = intersection; i < path2.size(); i++)       cout << path2[i] << " "; } int main(){    // binary tree formation    struct Node* root = tree(1);    root->left = tree(2);    root->left->left = tree(4);    root->left->left->left = tree(6);    root->left->right = tree(5);    root->left->right->left = tree(7);    root->left->right->right = tree(8);    root->right = tree(3);    root->right->left = tree(9);    root->right->right = tree(10);    int node1 = 5;    int node2 = 9;    printPath(root, node1, node2);    return 0; }

आउटपुट

यह प्रोग्राम आउटपुट प्रिंट करेगा -

5 2 1 3 9

  1. C++ प्रोग्राम: बाइनरी ट्री में पहला सबसे छोटा रूट-टू-लीफ पथ प्रिंट करना C++ प्रोग्राम: बाइनरी ट्री में पहला सबसे छोटा रूट-टू-लीफ पथ प्रिंट करना

    दिए गए बाइनरी ट्री में प्रोग्राम को दिए गए कई पथों में से रूट से लीफ तक का सबसे छोटा पथ ढूंढना होगा। चूंकि हम ट्री को बाएं से दाएं ट्रैवर्स करते हैं, इसलिए यदि रूट से लीफ तक कई सबसे छोटे पथ हैं तो प्रोग्राम ट्री के बाएं तरफ पहले ट्रैवर्स किए गए सबसे छोटे पथ को प्रिंट करेगा। हम एक कतार (queue) का उपय

  1. C++ प्रोग्राम: ट्री के विषम लेवल पर नोड्स प्रिंट करना C++ प्रोग्राम: ट्री के विषम लेवल पर नोड्स प्रिंट करना

    दिए गए बाइनरी ट्री में, प्रोग्राम को ट्री के विषम लेवल पर नोड्स प्रिंट करने होंगे और बाइनरी ट्री के लेवल 1 से n तक शुरू होते हैं। चूंकि कुछ उल्लेख नहीं है, दो दृष्टिकोणों में से एक को लागू किया जा सकता है यानी रिकर्सन या इटरेशन। चूंकि हम एक रिकर्सिव दृष्टिकोण का उपयोग कर रहे हैं, प्रोग्राम एक फ़ंक्श

  1. C++ प्रोग्राम: बाइनरी ट्री में सभी नोड्स के लेवल प्रिंट करना C++ प्रोग्राम: बाइनरी ट्री में सभी नोड्स के लेवल प्रिंट करना

    दिए गए बाइनरी ट्री में, कार्य 1 से n तक शुरू होने वाले प्रत्येक कुंजी से जुड़े लेवल को प्रिंट करना है जो एक नोड में संग्रहीत है। उपरोक्त ट्री में नोड्स हैं - 10 at level 1 3 and 211 at level 2 140, 162, 100 and 146 at level 3 दिए गए कुंजी के लिए प्रोग्राम को उस विशेष कुंजी का लेवल प्रिंट करना होगा।