এই টিউটোরিয়ালে, আমরা একটি কিউ ডেটা স্ট্রাকচার ব্যবহার করে একটি বাইনারি ট্রিকে থ্রেডেড বাইনারি ট্রিতে রূপান্তর করার একটি প্রোগ্রাম নিয়ে আলোচনা করব৷
এই জন্য, আমাদের একটি বাইনারি গাছ প্রদান করা হবে. আমাদের কাজ হল একটি কিউ ডেটা স্ট্রাকচারের সাহায্যে দ্রুত ইনঅর্ডার ট্রাভার্সালের জন্য অতিরিক্ত রুট যোগ করে সেই নির্দিষ্ট বাইনারি ট্রিটিকে একটি থ্রেডেড বাইনারি ট্রিতে রূপান্তর করা।
উদাহরণ
#include <iostream>
#include <queue>
using namespace std;
//node structure for threaded tree
struct Node {
int key;
Node *left, *right;
bool isThreaded;
};
//putting the inorder pattern into a queue
void convert_queue(Node* root, std::queue<Node*>* q){
if (root == NULL)
return;
if (root->left)
convert_queue(root->left, q);
q->push(root);
if (root->right)
convert_queue(root->right, q);
}
//traversing the queue and making threaded tree
void create_threadedtree(Node* root, std::queue<Node*>* q){
if (root == NULL)
return;
if (root->left)
create_threadedtree(root->left, q);
q->pop();
if (root->right)
create_threadedtree(root->right, q);
//if right pointer in NUll, point it to
//inorder successor
else {
root->right = q->front();
root->isThreaded = true;
}
}
//finally taking the tree and converting it into threaded
void createThreaded(Node* root){
std::queue<Node*> q;
convert_queue(root, &q);
create_threadedtree(root, &q);
}
Node* leftMost(Node* root){
while (root != NULL && root->left != NULL)
root = root->left;
return root;
}
//performing inorder traversal of threaded tree
void inOrder(Node* root){
if (root == NULL)
return;
Node* cur = leftMost(root);
while (cur != NULL) {
cout << cur->key << " ";
//if threaded node, move to inorder successor
if (cur->isThreaded)
cur = cur->right;
else
cur = leftMost(cur->right);
}
}
Node* newNode(int key){
Node* temp = new Node;
temp->left = temp->right = NULL;
temp->key = key;
return temp;
}
int main(){
Node* root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
root->right->left = newNode(6);
root->right->right = newNode(7);
createThreaded(root);
cout << "Traversing threaded tree :\n";
inOrder(root);
return 0;
} আউটপুট
Traversing threaded tree : 4 2 5 1 6 3 7
