ধরা যাক একটি ইন্টিজার n আছে, আমাদের 1 থেকে n পর্যন্ত মান স্টোর করে স্ট্রাকচারালি ইউনিক সব বাইনারি সার্চ ট্রি জেনারেট করতে হবে। তাই যদি ইনপুট 3 হয়, তবে ট্রিগুলো হবে:
এটি সমাধান করার জন্য আমরা নিচের ধাপগুলো অনুসরণ করব:
- generate() নামে একটি রিকারসিভ ফাংশন ডিফাইন করুন, এটি low এবং high নেবে
- temp নামে একটি ট্রি নোড ডিফাইন করুন।
- যদি low > high হয়, তবে temp-এ null ইনসার্ট করুন এবং temp রিটার্ন করুন
- i = low থেকে high পর্যন্ত
- left_subtree := generate(low, i - 1)
- right_subtree := generate(i + 1, high)
- current := i
- j = 0 থেকে left_subtree-এর আকার পর্যন্ত
- k = 0 থেকে right_subtree-এর আকার পর্যন্ত
- curr_node := current মান দিয়ে একটি ট্রি নোড তৈরি করুন
- curr_node-এর লেফট := left_subtree[j]
- curr_node-এর রাইট := right_subtree[k]
- curr_node temp-এ ইনসার্ট করুন
- k = 0 থেকে right_subtree-এর আকার পর্যন্ত
- temp রিটার্ন করুন।
- প্রাথমিকভাবে generate() ফাংশন 1 এবং n মান দিয়ে কল করুন সব ট্রি জেনারেট করার জন্য।
উদাহরণ (C++):
নিচের ইমপ্লিমেন্টেশনটি দেখে আরও ভালো বুঝতে পারবেন:
#include <bits/stdc++.h> using namespace std; class TreeNode{ public: int val; TreeNode *left, *right; TreeNode(int data){ val = data; left = right = NULL; } }; void insert(TreeNode **root, int val){ queue<TreeNode*> q; q.push(*root); while(q.size()){ TreeNode *temp = q.front(); q.pop(); if(!temp->left){ if(val != NULL) temp->left = new TreeNode(val); else temp->left = new TreeNode(0); return; } else{ q.push(temp->left); } if(!temp->right){ if(val != NULL) temp->right = new TreeNode(val); else temp->right = new TreeNode(0); return; } else{ q.push(temp->right); } } } TreeNode *make_tree(vector<int> v){ TreeNode *root = new TreeNode(v[0]); for(int i = 1; i<v.size(); i++){ insert(&root, v[i]); } return root; } void tree_level_trav(TreeNode*root){ if (root == NULL) return; cout << "["; queue<TreeNode *> q; TreeNode *curr; q.push(root); q.push(NULL); while (q.size() > 1) { curr = q.front(); q.pop(); if (curr == NULL){ q.push(NULL); } else { if(curr->left) q.push(curr->left); if(curr->right) q.push(curr->right); if(curr == NULL || curr->val == 0){ cout << "null" << ", "; } else{ cout << curr->val << ", "; } } } cout << "]"<<endl; } class Solution { public: vector<TreeNode*> generate(int low, int high) { vector <TreeNode*> temp; if(low > high){ temp.push_back(NULL); return temp; } for(int i = low;i<=high;i++){ vector <TreeNode*> leftSubtree = generate(low,i-1); vector <TreeNode*> rightSubtree = generate(i+1,high); int current = i; for(int j = 0;j<leftSubtree.size();j++){ for(int k =0;k<rightSubtree.size();k++){ TreeNode* currentNode = new TreeNode(current); currentNode->left = leftSubtree[j]; currentNode->right = rightSubtree[k]; temp.push_back(currentNode); } } } return temp; } vector<TreeNode*> generateTrees(int n) { if(!n){ vector <TreeNode*> r; return r; } return generate(1,n) ; } }; main(){ Solution ob; vector<TreeNode*> v = ob.generateTrees(3); for(int i = 0; i<v.size(); i++) tree_level_trav(v[i]); }ইনপুট
3
আউটপুট
[1, 2, 3, ] [1, 3, 2, ] [2, 1, 3, ] [3, 1, 2, ] [3, 2, 1, ]
