इस समस्या में, हमें एक बाइनरी ट्री दिया गया है। और हमें ट्री के रूट से लीफ तक के सभी पथों को प्रिंट करना है। साथ ही, नोड्स की सापेक्ष स्थितियों को दिखाने के लिए अंडरस्कोर "_" जोड़ना है।
विषय को बेहतर ढंग से समझने के लिए एक उदाहरण लेते हैं -
इनपुट -
आउटपुट -
_ _ 3 _ 9 1 _3 9 _7 3 _ 4 _ _ 2 3 9 4 1 7 6 2 3 _ 4 6
इस समस्या को हल करने के लिए, हम ट्री के तत्वों के ऊर्ध्वाधर क्रम की अवधारणा का उपयोग करेंगे।
इसके आधार पर, हम रूट से लीफ तक का पथ प्रिंट करेंगे।
एल्गोरिदम
चरण 1: प्रीऑर्डर ट्रैवर्सल का उपयोग करके बाइनरी ट्री को पार करें। और ट्रैवर्सल पर क्रम के आधार पर क्षैतिज दूरी की गणना करें। रूट की क्षैतिज दूरी 0 है और ऊपर दिए गए आरेख के अनुसार संसाधित की जाती है। चरण 2: और लीफ नोड पर ट्रैवर्स करने पर, अंत में अंडरस्कोर "_" के साथ पथ प्रिंट करें।
उदाहरण
#include<bits/stdc++.h> using namespace std; #define MAX_PATH_SIZE 1000 struct Node{ char data; Node *left, *right; }; Node * newNode(char data){ struct Node *temp = new Node; temp->data = data; temp->left = temp->right = NULL; return temp; } struct PATH{ int horizontalDistance; char key; }; void printPath(vector < PATH > path, int size){ int minimumhorizontalDistance = INT_MAX; PATH p; for (int it=0; it<size; it++){ p = path[it]; minimumhorizontalDistance = min(minimumhorizontalDistance, p.horizontalDistance); } for (int it=0; it < size; it++){ p = path[it]; int noOfUnderScores = abs(p.horizontalDistance -minimumhorizontalDistance); for (int i = 0; i < noOfUnderScores; i++) cout<<"_ "; cout<<p.key<<endl; } cout<<"\nNext Path\n"; } void printAllRtLPaths(Node *root, vector < PATH > &AllPath, int horizontalDistance, int order ){ if(root == NULL) return; if (root->left == NULL && root->right == NULL){ AllPath[order] = (PATH { horizontalDistance, root->data }); printPath(AllPath, order+1); return; } AllPath[order] = (PATH { horizontalDistance, root->data }); printAllRtLPaths(root->left, AllPath, horizontalDistance-1, order+1); printAllRtLPaths(root->right, AllPath, horizontalDistance+1, order+1); } void printRootToLeafPath(Node *root){ if (root == NULL) return; vector<PATH> Allpaths(MAX_PATH_SIZE); printAllRtLPaths(root, Allpaths, 0, 0); } int main(){ Node *root = newNode('3'); root->left = newNode('9'); root->right = newNode('4'); root->left->left = newNode('1'); root->left->right = newNode('7'); root->right->left = newNode('6'); root->right->right = newNode('2'); printRootToLeafPath(root); return 0; } आउटपुट
_ _ 3 _ 9 1 Next Path _ 3 9 _ 7 Next Path 3 _ 4 6 Next Path 3 _ 4 _ _ 2
