C++ में बाइनरी ट्री वर्टिकल ऑर्डर ट्रैवर्सल

मान लीजिए कि एक बाइनरी ट्री है, हमें इसके नोड्स के मानों का वर्टिकल ऑर्डर ट्रैवर्सल खोजना होगा। यदि दो नोड एक ही पंक्ति और स्तंभ में हैं, तो क्रम बाएं से दाएं होना चाहिए।

तो, अगर इनपुट पसंद है,

तो आउटपुट [[9],[3,15],[20],[7]]

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• एक नक्शा परिभाषित करें मी

• फ़ंक्शन को हल करें () परिभाषित करें, यह नोड लेगा, x इसे 0 से प्रारंभ करें,

• यदि नोड शून्य है, तो -

  • वापसी

• हल करें (नोड के बाएं, x - 1)

• हल करें (नोड का दायां, x + 1)

• m[x]

  . के अंत में नोड का मान डालें

• मुख्य विधि से, निम्न कार्य करें -

• यदि रूट शून्य है, तो -

  • वापसी {}

• एक कतार को परिभाषित करें q

• q में { 0, रूट } डालें

• m[0]

  . के अंत में नोड का मान डालें

• जबकि (q खाली नहीं है), करें -

  • sz :=q का आकार

  • जबकि sz गैर-शून्य है, प्रत्येक पुनरावृत्ति में sz घटाएं, −

    . करें

    • curr :=q का पहला तत्व

    • q से तत्व हटाएं

    • नोड =वक्र का दूसरा तत्व

    • x :=वक्र का पहला तत्व

    • यदि नोड का बायां भाग शून्य नहीं है, तो -

      • q में डालें { x - 1, नोड के बाईं ओर}

      • m[x - 1]

        . के अंत में नोड के बाईं ओर

    • यदि नोड का दायां शून्य नहीं है, तो -

      • q में {x - 1, दाएँ नोड} डालें

      • m[x - 1]

        . के अंत में नोड के दाईं ओर

• एक 2डी सरणी रेट परिभाषित करें

• m do के प्रत्येक की-वैल्यू पेयर 'it' के लिए -

  • इसका मूल्य रिट में डालें

• वापसी रिट

उदाहरण

आइए एक बेहतर समझ प्राप्त करने के लिए निम्नलिखित कार्यान्वयन देखें -

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<vector<auto< > v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << "[";
      for(int j = 0; j <v[i].size(); j++){
         cout << v[i][j] << ", ";
      }
      cout << "],";
   }
   cout << "]"<<endl;
}
class TreeNode{
public:
   int val;
   TreeNode *left, *right;
   TreeNode(int data){
      val = data;
      left = NULL;
      right = NULL;
   }
};
void insert(TreeNode **root, int val){
   queue<TreeNode*> q;
   q.push(*root);
   while(q.size()){
      TreeNode *temp = q.front();
      q.pop();
      if(!temp->left){
         if(val != NULL)
            temp->left = new TreeNode(val);
         else
            temp->left = new TreeNode(0);
         return;
      }
      else{
         q.push(temp->left);
      }
      if(!temp->right){
         if(val != NULL)
            temp->right = new TreeNode(val);
         else
            temp->right = new TreeNode(0);
         return;
      }
      else{
         q.push(temp->right);
      }
   }
}
TreeNode *make_tree(vector<int< v){
   TreeNode *root = new TreeNode(v[0]);
   for(int i = 1; i<v.size(); i++){
      insert(&root, v[i]);
   }
   return root;
}
class Solution {
public:
   map<int, vector<int< > m;
   void solve(TreeNode* node, int x = 0){
      if (!node || node->val == 0)
         return;
      solve(node->left, x - 1);
      solve(node->right, x + 1);
      m[x].push_back(node->val);
   }
   static bool cmp(vector<int<& a, vector<int<& b){
      return a[0] != b[0] ? a[0] < b[0] : a[1] < b[1];
   }
   vector<vector<int< > verticalOrder(TreeNode* root){
      if (!root)
         return {};
      queue<pair > q;
      q.push({ 0, root });
      m[0].push_back(root->val);
      while (!q.empty()) {
         int sz = q.size();
         while (sz--) {
            pair<int, TreeNode*> curr = q.front();
            q.pop();
            TreeNode* node = curr.second;
            int x = curr.first;
            if (node->left && node->left->val != 0) {
               q.push({ x - 1, node->left });
               m[x - 1].push_back(node->left->val);
            }
            if (node->right && node->right->val != 0) {
               q.push({ x + 1, node->right });
               m[x + 1].push_back(node->right->val);
            }
         }
      }
      vector<vector<int< > ret;
      map<int, vector<int< >::iterator it = m.begin();
      while (it != m.end()) {
         ret.push_back(it->second);
         it++;
      }
      return ret;
   }
};
main(){
   Solution ob;
   vector<int< v = {3,9,20,NULL,NULL,15,7};
   TreeNode *root = make_tree(v);
   print_vector(ob.verticalOrder(root));
}

इनपुट

{3,9,20,NULL,NULL,15,7}

आउटपुट

[[9, ],[3, 15, ],[20, ],[7, ],]