हमें अलग-अलग नोड्स के एक बाइनरी ट्री और बाइनरी ट्री के दो नोड्स दिए गए हैं, जिसका बाइनरी ट्री में पथ हम प्रिंट करना चाहते हैं।
उदाहरण के लिए - हम नोड 140 से 211 के बीच के पाथ को प्रिंट करना चाहते हैं, इसलिए इसका आउटपुट इस तरह होना चाहिए -
Output: 140->3->10->211
विचार दो नोड्स के लिए रूट नोड बनाने के लिए पथ ढूंढना है और उन्हें दो अलग-अलग वैक्टर या सरणियों में संग्रहीत करना है, जैसे कि पथ 1 और पथ 2।
अब, दो अलग-अलग मामले सामने आते हैं -
- यदि दो नोड रूट नोड्स के अलग-अलग उप-वृक्षों में हैं -जब दो नोड अलग-अलग उप-वृक्षों में होते हैं जैसे एक बाएँ में और दूसरा दाएँ में। इस मामले में, यह स्पष्ट है कि रूट नोड नोड 1 से नोड 2 के पथ के बीच में स्थित होगा। इसलिए, पाथ1 को उल्टे क्रम में प्रिंट करें और फिर पाथ2 को प्रिंट करें।
-
यदि नोड्स एक ही सबट्री में हैं - जब दोनों नोड्स एक ही सबट्री में हों जो या तो लेफ्ट सबट्री में हो या राइट सबट्री में हो। इस मामले में, आपको रूट से पथ का निरीक्षण करने की आवश्यकता है दो नोड्स में एक चौराहे बिंदु होगा जिसके पहले रूट नोड से दोनों नोड्स के लिए पथ सामान्य है। हमें उपरोक्त मामले की तरह उस बिंदु से प्रतिच्छेदन बिंदु और प्रिंट नोड्स ढूंढना होगा।
एल्गोरिदम
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