उन नोड्स पर विचार करना जो ढलान -1 की रेखाओं के बीच से गुजर रहे हैं। बाइनरी ट्री का विकर्ण ट्रैवर्सल उन सभी नोड्स को पार करके प्रिंट करना होगा जो इन रेखाओं के बीच मौजूद हैं।
आइए पहले उस स्ट्रक्ट को परिभाषित करें जो एक ट्री नोड को दर्शाता है जिसमें डेटा और इसके बाएं और दाएं चाइल्ड नोड होते हैं। यदि यह बनाया जाने वाला पहला नोड है तो यह रूट नोड है अन्यथा चाइल्ड नोड।
struct Node {
int data;
struct Node *leftChild, *rightChild;
};
इसके बाद हम createNode(int data) फंक्शन बनाते हैं जो एक int मान लेता है और इसे नोड के डेटा सदस्य को असाइन करता है। फंक्शन बने हुए स्ट्रक्ट Node का पॉइंटर वापस करता है। साथ ही, नव निर्मित नोड के बाएं और दाएं चाइल्ड को null पर सेट किया जाता है।
struct Node* newNode(int data){
struct Node* node = new Node();
node->data = data;
node->leftChild = node->rightChild = NULL;
return node;
}
traverseDiagonal(Node* root, int depth, map<int, vector<int>> &myMap) फंक्शन हमारा रूट नोड, वर्तमान गहराई और एक मैप लेता है जिसमें int मान कुंजी के रूप में और int का वेक्टर मान के रूप में होता है। हम myMap को इस फंक्शन में रेफरेंस द्वारा पास करते हैं। फंक्शन फिर जांचता है कि रूट null है या नहीं और यदि नहीं है तो हम इनऑर्डर ट्रैवर्सल करते हुए वर्तमान गहराई पर अपने वेक्टर डेटा स्ट्रक्चर के पीछे रूट->डेटा तत्व को पुश करते हैं।
void traverseDiagonal(Node* root, int depth, map<int, vector<int>> &m){
if(root){
m[depth].push_back(root->data);
हम फिर ट्री का रिकर्सिव इनऑर्डर ट्रैवर्सल करते हैं विकर्ण दूरी को ट्रैक करते हुए और जब भी हम ट्री के बाएं चाइल्ड को पार करते हैं तो गहराई में 1 जोड़ते हैं। जब हम ट्री के दाएं चाइल्ड को पार करते हैं तो गहराई में कुछ नहीं जोड़ते।
traverseDiagonal(root->leftChild, depth+1, myMap); traverseDiagonal(root->rightChild, depth, myMap);
अगला, हमारे मुख्य फंक्शन में हम createNode(data) फंक्शन का उपयोग करके ट्री बनाते हैं।
Node *root = createNode(10); root->leftChild = createNode(5); root->rightChild = createNode(15); root->leftChild->leftChild = createNode(4); root->leftChild->rightChild = createNode(6); root->rightChild->rightChild = createNode(17); root->rightChild->rightChild->leftChild = createNode(16);
हम फिर एक मैप myMap घोषित करते हैं जिसमें int कुंजी के रूप में और int का वेक्टर मान के रूप में होता है। यह मैप फिर रूट नोड और वर्तमान गहराई के साथ traverseDiagonal को पास किया जाता है।
map<int, vector<int>> myMap; traverseDiagonal(root, 0, myMap);
मैप myMap मानों से भर जाने के बाद हम रेंज-आधारित फॉर लूप का उपयोग करके इस पर पुनरावृति करते हैं और उन विकर्ण मानों को प्रिंट करते हैं।
for(auto k: myMap){
for(auto Nodes: k.second)
cout<<Nodes<<" ";
cout<<endl;
}
उदाहरण
बाइनरी ट्री के विकर्ण ट्रैवर्सल को खोजने के लिए निम्नलिखित कार्यान्वयन देखें।
#include <iostream>
#include <map>
#include <vector>
using namespace std;
struct Node{
int data;
Node *leftChild, *rightChild;
};
Node* createNode(int data){
Node* node = new Node();
node->data = data;
node->leftChild = node->rightChild = NULL;
return node;
}
void traverseDiagonal(Node* root, int depth, map<int, vector<int>> &myMap){
if(root){
myMap[depth].push_back(root->data);
traverseDiagonal(root->leftChild, depth+1, myMap);
traverseDiagonal(root->rightChild, depth, myMap);
}
}
int main(){
Node *root = createNode(10);
root->leftChild = createNode(5);
root->rightChild = createNode(15);
root->leftChild->leftChild = createNode(4);
root->leftChild->rightChild = createNode(6);
root->rightChild->rightChild = createNode(17);
root->rightChild->rightChild->leftChild = createNode(16);
map<int, vector<int>> myMap;
traverseDiagonal(root, 0, myMap);
for(auto k: myMap){
for(auto Nodes: k.second)
cout<<Nodes<<" ";
cout<<endl;
}
}
आउटपुट
उपरोक्त कोड निम्नलिखित आउटपुट देगा:
10 15 17 5 6 16 4