এই টিউটোরিয়ালে, আমরা একটি সাধারণ বাইনারি সার্চ ট্রিকে সুষম বাইনারি সার্চ ট্রিতে রূপান্তর করার একটি প্রোগ্রাম নিয়ে আলোচনা করব।
এর জন্য আমাদের বাম বা ডানে একটি তির্যক বাইনারি অনুসন্ধান গাছ দেওয়া হবে। আমাদের কাজ হল একটি নির্দিষ্ট নিয়ম মেনে এটিকে একটি সুষম বাইনারি সার্চ ট্রিতে রূপান্তর করা৷
৷উদাহরণ
#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
