এই টিউটোরিয়ালে, আমরা একটি প্রোগ্রাম নিয়ে আলোচনা করব যা একটি সাধারণ বাইনারি সার্চ ট্রি (BST) কে ব্যালেন্সড বাইনারি সার্চ ট্রিতে রূপান্তর করে।
এখানে আমাদের একটি স্কিউড (skewed) বাইনারি সার্চ ট্রি দেওয়া থাকবে যেটি বাম বা ডান দিকে ঝুকে থাকতে পারে। আমাদের কাজ হলো নির্দিষ্ট নিয়ম মেনে সেটিকে একটি ব্যালেন্সড বাইনারি সার্চ ট্রিতে রূপান্তর করা।
উদাহরণ
#include <bits/stdc++.h> using namespace std; //ট্রির নোড স্ট্রাকচার struct Node{ int data; Node* left, *right; }; //ট্রি ট্রাভার্স করে নোড পয়েন্টারগুলো //ভেক্টর 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); } //বাইনারি ট্রি কনস্ট্রাক্ট করা Node* construct_tree(vector<Node*> &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<Node *> 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
