C++ এ বাইনারি ট্রি ভার্টিক্যাল অর্ডার ট্রাভার্সাল

ধরুন একটি বাইনারি ট্রি আছে, আমাদের এর নোডের মানগুলির উল্লম্ব ক্রম ট্রাভার্সাল খুঁজে বের করতে হবে। দুটি নোড একই সারি এবং কলামে থাকলে, ক্রমটি বাম থেকে ডানে হওয়া উচিত।

সুতরাং, যদি ইনপুট মত হয়,

তাহলে আউটপুট হবে [[9],[3,15],[20],[7]]

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• একটি মানচিত্র m

  সংজ্ঞায়িত করুন

• একটি ফাংশন সল্ভ() সংজ্ঞায়িত করুন, এটি নোড নেবে, x এটি 0 দিয়ে আরম্ভ করুন,

• যদি নোড নাল হয়, তাহলে −

  • ফেরত

• সমাধান (নোডের বাম, x - 1)

• সমাধান (নোডের ডানদিকে, x + 1)

• m[x]

  এর শেষে নোডের মান সন্নিবেশ করান

• প্রধান পদ্ধতি থেকে, নিম্নলিখিতগুলি করুন -

• যদি মূল শূন্য হয়, তাহলে −

  • ফেরত {}

• একটি সারি q

  সংজ্ঞায়িত করুন

• q

  -এ { 0, root } ঢোকান

• m[0]

  এর শেষে নোডের মান সন্নিবেশ করান

• যখন (q খালি নয়), −

  করুন

  • sz :=q এর আকার

  • যখন sz অ-শূন্য, প্রতিটি পুনরাবৃত্তিতে sz হ্রাস করুন, −

    করুন

    • curr :=q এর প্রথম উপাদান

    • q

      থেকে উপাদান মুছুন

    • নোড =curr এর দ্বিতীয় উপাদান

    • x :=curr এর প্রথম উপাদান

    • যদি নোডের বাম অংশ শূন্য না হয়, তাহলে −

      • q

        -এ { x - 1, নোডের বামে} সন্নিবেশ করান

      • m[x - 1]

        এর শেষে নোডের বাম দিকে

    • যদি নোডের ডানদিকে শূন্য না হয়, তাহলে −

      • q

        -এ { x - 1, নোডের ডানদিকে} সন্নিবেশ করুন

      • m[x - 1]

        এর শেষে নোডের ডানদিকে

• একটি 2D অ্যারে ret সংজ্ঞায়িত করুন

• প্রতিটি কী-মানের জোড়ার জন্য m do −

  এর 'it'

  • ret

    -এ এর মান সন্নিবেশ করান

• রিটার্ন রিটার্ন

উদাহরণ

আরো ভালোভাবে বোঝার জন্য নিচের বাস্তবায়নটি দেখি -

#include  namespace ব্যবহার করে std;void print_vector(vector v){ cout <<"["; for(int i =0; i 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); প্রত্যাবর্তন } অন্য{ q.push(temp->left); } if(!temp->right){ if(val !=NULL) temp->right =new TreeNode(val); else temp->right =new TreeNode(0); প্রত্যাবর্তন } অন্য{ q.push(temp->ডান); } }}TreeNode *make_tree(vector m; void solve(TreeNode* node, int x =0){ if (!node || node->val ==0) রিটার্ন; সমাধান (নোড->বাম, x - 1); সমাধান (নোড->ডান, x + 1); m[x].push_back(নোড->ভাল); } স্ট্যাটিক বুল cmp(ভেক্টর verticalOrder(TreeNode* root){ if (!root) রিটার্ন {}; সারি <জোড়া> q; q.push({ 0, root }); m[0].push_back(root->val); যখন (!q.empty()) { int sz =q.size(); যখন (sz--) { pair 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); } } } ভেক্টর<ভেক্টর ret; মানচিত্র::iterator it =m.begin(); যখন (এটি !=m.end()) { ret.push_back(it->সেকেন্ড); এটা++; } রিটার্ন রিটার্ন; }};প্রধান(){সমাধান ob; ভেক্টর 
ইনপুট
 
{3,9,20,NULL,NULL,15,7}
 
আউটপুট
 <প্রে>[[9, ],[3, 15, ],[20, ],[7, ],]