इस ट्यूटोरियल में, हम एक क्यू डेटा संरचना का उपयोग करके एक बाइनरी ट्री को थ्रेडेड बाइनरी ट्री में बदलने के लिए एक प्रोग्राम पर चर्चा करेंगे।
इसके लिए हमें एक बाइनरी ट्री प्रदान किया जाएगा। हमारा काम कतार डेटा संरचना की मदद से तेज इनऑर्डर ट्रैवर्सल के लिए अतिरिक्त मार्ग जोड़कर उस विशेष बाइनरी ट्री को थ्रेडेड बाइनरी ट्री में बदलना है।
उदाहरण
#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