बाइनरी ट्री का एंटी-क्लॉकवाइज स्पाइरल ट्रैवर्सल एक ट्री के तत्वों को इस तरह से पार करना है कि यदि पार किया जाए तो वे एक स्पाइरल बनाते हैं लेकिन रिवर्स ऑर्डर में। निम्नलिखित आकृति दिखाती है कि बाइनरी ट्री का एंटी-क्लॉकवाइज स्पाइरल ट्रैवर्सल कैसे होता है।
बाइनरी ट्री के स्पाइरल ट्रैवर्सल के लिए परिभाषित एल्गोरिदम निम्नलिखित तरीके से काम करता है -
दो वेरिएबल i और j आरंभ किए जाते हैं और मान i = 0 और j = वेरिएबल की ऊंचाई के बराबर होते हैं। एक फ्लैग का उपयोग यह जांचने के लिए किया जाता है कि किस सेक्शन को प्रिंट करना है। फ्लैग प्रारंभ में false पर सेट होता है। एक लूप जो i < j तक काम करता है, पहले आधे को प्रिंट करता है अन्यथा अंतिम को प्रिंट करता है और फ्लैग मान को फ्लिप करता है। यह तब तक होता है जब तक पूरा बाइनरी ट्री प्रिंट नहीं हो जाता।
उदाहरण
#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
