इस ट्यूटोरियल में, हम एक प्रोग्राम पर चर्चा करेंगे जो सामान्य बाइनरी सर्च ट्री को संतुलित बाइनरी सर्च ट्री में बदलता है।
इसके लिए हमें एक तिरछा बाइनरी सर्च ट्री दिया जाएगा जो बाएं या दाएं हो सकता है। हमारा कार्य इसे निश्चित नियमों का पालन करते हुए संतुलित बाइनरी सर्च ट्री में बदलना है।
उदाहरण
#include <bits/stdc++.h>
using namespace std;
//ट्री का नोड स्ट्रक्चर
struct Node {
int data;
Node* left, *right;
};
//ट्री को ट्रैवर्स करना और नोड पॉइंटर्स को वेक्टर में स्टोर करना
void store_nodes(Node* root, vector& nodes) {
if (root == NULL)
return;
store_nodes(root->left, nodes);
nodes.push_back(root);
store_nodes(root->right, nodes);
}
//बाइनरी ट्री का निर्माण
Node* construct_tree(vector& nodes, int start, int end) {
if (start > end)
return NULL;
//मध्य तत्व को रूट बनाएं
int mid = (start + end) / 2;
Node* root = nodes[mid];
root->left = construct_tree(nodes, start, mid - 1);
root->right = construct_tree(nodes, mid + 1, end);
return root;
}
//असंतुलित BST को संतुलित BST में बदलना
Node* buildTree(Node* root) {
//दिए गए BST के नोड्स को क्रमबद्ध क्रम में स्टोर करना
vector nodes;
store_nodes(root, nodes);
int n = nodes.size();
return construct_tree(nodes, 0, n - 1);
}
//नया नोड बनाना
Node* newNode(int data) {
Node* node = new Node;
node->data = data;
node->left = node->right = NULL;
return (node);
}
//प्रीऑर्डर ट्रैवर्सल करना
void preOrder(Node* node) {
if (node == NULL)
return;
printf("%d ", node->data);
preOrder(node->left);
preOrder(node->right);
}
int main() {
Node* root = newNode(10);
root->left = newNode(8);
root->left->left = newNode(7);
root->left->left->left = newNode(6);
root->left->left->left->left = newNode(5);
root = buildTree(root);
printf("Preorder traversal of balanced BST : \n");
preOrder(root);
return 0;
}
आउटपुट
Preorder traversal of balanced BST : 7 5 6 8 10
