सी ++ में बाइनरी ट्री का विकर्ण ट्रैवर्सल?

ढलान -1 की रेखाओं के बीच से गुजरने वाले नोड्स पर विचार करना। बाइनरी ट्री का विकर्ण ट्रैवर्सल इन पंक्तियों के बीच मौजूद उन सभी नोड्स को ट्रैवर्स और प्रिंट करना होगा।

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

struct Node {
   int data;
   struct Node *leftChild, *rightChild;
};

आगे हम अपना createNode(int data) फंक्शन बनाते हैं जो एक इंट वैल्यू लेता है और इसे नोड के डेटा मेंबर को असाइन करता है। फ़ंक्शन पॉइंटर को बनाए गए स्ट्रक्चर नोड पर लौटाता है। साथ ही, नव निर्मित नोड के बाएँ और दाएँ बच्चे को शून्य पर सेट किया गया है।

struct Node* newNode(int data){
   struct Node* node = new Node();
   node->data = data;
   node->leftChild = node->rightChild = NULL;
   return node;
}

traverseDiagonal(Node* root, int गहराई, map> &myMap) फ़ंक्शन हमारे रूट नोड, वर्तमान गहराई और एक नक्शा लेता है जिसमें int मान कुंजी के रूप में और int के वेक्टर मान के रूप में होते हैं। हम इस फ़ंक्शन के संदर्भ के रूप में myMap पास करते हैं। फ़ंक्शन तब जांचता है कि रूट शून्य है या नहीं और यदि ऐसा नहीं है तो हम तत्व रूट-> डेटा को हमारे वेक्टर डेटा संरचना के पीछे वर्तमान गहराई पर धक्का देते हैं क्योंकि हम इनऑर्डर ट्रैवर्सल करते हैं।

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 के वेक्टर मान के रूप में होते हैं। यह नक्शा तब रूट नोड और वर्तमान गहराई के साथ ट्रैवर्सडायगोनल को पास किया जाता है।

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){
      m[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