इस ट्यूटोरियल में, हम एक सामान्य बाइनरी सर्च ट्री को संतुलित बाइनरी सर्च ट्री में बदलने के लिए एक प्रोग्राम पर चर्चा करेंगे।
इसके लिए हमें बाएं या दाएं एक तिरछा बाइनरी सर्च ट्री प्रदान किया जाएगा। हमारा काम नियमों के एक निश्चित सेट का पालन करते हुए इसे एक संतुलित बाइनरी सर्च ट्री में बदलना है।
उदाहरण
#include <bits/stdc++.h>
using namespace std;
//node structure of tree
struct Node{
int data;
Node* left, *right;
};
//traversing tree and storing node pointers
//in vector nodes
void store_nodes(Node* root, vector<Node*> &nodes){
if (root==NULL)
return;
store_nodes(root->left, nodes);
nodes.push_back(root);
store_nodes(root->right, nodes);
}
//constructing binary tree
Node* construct_tree(vector<Node*> &nodes, int start,
int end){
if (start > end)
return NULL;
//make the middle element to be the root
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;
}
//converting an unbalanced BST to a balanced BST
Node* buildTree(Node* root){
//storing nodes of given BST in sorted order
vector<Node *> nodes;
store_nodes(root, nodes);
int n = nodes.size();
return construct_tree(nodes, 0, n-1);
}
//creation of new node
Node* newNode(int data){
Node* node = new Node;
node->data = data;
node->left = node->right = NULL;
return (node);
}
//performing preorder traversal
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