একটি বাইনারি গাছের ঘড়ির বিপরীত দিকের সর্পিল ট্রাভার্সাল একটি গাছের উপাদানগুলিকে এমনভাবে অতিক্রম করে যে অতিক্রম করলে তারা একটি সর্পিল তৈরি করে কিন্তু বিপরীত ক্রমে। নিচের চিত্রটি দেখায় কিভাবে বাইনারি গাছের ঘড়ির কাঁটার বিপরীত সর্পিল ট্রাভার্সাল।
একটি বাইনারি গাছের সর্পিল ট্রাভার্সালের জন্য সংজ্ঞায়িত অ্যালগরিদম নিম্নলিখিত উপায়ে কাজ করে -
দুটি ভেরিয়েবল i এবং j শুরু করা হয়েছে এবং মানগুলিকে i =0 এবং j =ভেরিয়েবলের উচ্চতা হিসাবে সমান করা হয়েছে। একটি পতাকা চেক করার জন্য ব্যবহার করা হয় যখন বিভাগটি মুদ্রিত হবে। পতাকা প্রাথমিকভাবে মিথ্যা সেট করা হয়. একটি লুপ i উদাহরণ
#include <bits/stdc++.h>
using namespace std;
struct Node {
struct Node* left;
struct Node* right;
int data;
Node(int data) {
this->data = data;
this->left = NULL;
this->right = NULL;
}
};
int height(struct Node* root) {
if (root == NULL)
return 0;
int lheight = height(root->left);
int rheight = height(root->right);
return max(1 + lheight, 1 + rheight);
}
void leftToRight(struct Node* root, int level) {
if (root == NULL)
return;
if (level == 1)
cout << root->data << " ";
else if (level > 1) {
leftToRight(root->left, level - 1);
leftToRight(root->right, level - 1);
}
}
void rightToLeft(struct Node* root, int level) {
if (root == NULL)
return;
if (level == 1)
cout << root->data << " ";
else if (level > 1) {
rightToLeft(root->right, level - 1);
rightToLeft(root->left, level - 1);
}
}
int main() {
struct Node* root = new Node(1);
root->left = new Node(2);
root->right = new Node(3);
root->left->left = new Node(4);
root->right->left = new Node(5);
root->right->right = new Node(7);
root->left->left->left = new Node(10);
root->left->left->right = new Node(11);
root->right->right->left = new Node(8);
int i = 1;
int j = height(root);
int flag = 0;
while (i <= j) {
if (flag == 0) {
rightToLeft(root, i);
flag = 1;
i++;
} else {
leftToRight(root, j);
flag = 0;
j--;
}
}
return 0;
} আউটপুট
1 10 11 8 3 2 4 5 7
