ধরুন আমাদের একটি পূর্ণসংখ্যা n আছে, আমাদেরকে 1 থেকে n পর্যন্ত মান সংরক্ষণ করে এমন সমস্ত কাঠামোগতভাবে অনন্য বাইনারি অনুসন্ধান ট্রি তৈরি করতে হবে। সুতরাং যদি ইনপুট 3 হয়, তাহলে গাছগুলি হবে −
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- generate() নামক একটি পুনরাবৃত্ত ফাংশন সংজ্ঞায়িত করুন, এটি কম এবং বেশি লাগবে
- টেম্প নামে একটি ট্রি নোড সংজ্ঞায়িত করুন।
- যদি কম> উচ্চ হয়, তাহলে টেম্পে নাল ঢোকান এবং টেম্প রিটার্ন করুন
- আমার জন্য নিম্ন থেকে উচ্চ পরিসরে
- left_subtree :=generate(low, i – 1)
- right_subtree :=generate(i + 1, high)
- কারেন্ট :=i
- j-এর জন্য রেঞ্জ 0 থেকে বাম_সাবট্রির মাপ
- k এর জন্য রেঞ্জ 0 থেকে ডান_সাবট্রির মাপ
- curr_node :=মান কারেন্ট সহ একটি ট্রি নোড তৈরি করুন
- curr_node এর বাম :=left_subtree[j]
- curr_node এর ডানে :=right_subtree[k]
- টেম্পে curr_node ঢোকান
- k এর জন্য রেঞ্জ 0 থেকে ডান_সাবট্রির মাপ
- রিটার্ন টেম্প।
- প্রাথমিকভাবে 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, ]