ধরুন আমাদের এই নিয়মগুলির উপর ভিত্তি করে একটি m*n 2D স্ট্রিং অ্যারেতে একটি বাইনারি ট্রি প্রদর্শন করতে হবে -
- সারি নম্বর m প্রদত্ত বাইনারি গাছের উচ্চতার সমান হওয়া উচিত।
- কলাম সংখ্যা n সর্বদা একটি বিজোড় সংখ্যা হওয়া উচিত।
- রুট নোডের মান প্রথম সারির ঠিক মাঝখানে রাখতে হবে। কলাম এবং সারি যেখানে রুট নোড থাকে, বাকি স্থানটিকে দুটি ভাগে বিভক্ত করবে। এগুলি হল বাম-নীচের অংশ এবং ডান-নিচের অংশ। আমাদের বাম-নীচের অংশে বাম সাবট্রি প্রিন্ট করা উচিত এবং ডান-নিচের অংশে ডান সাবট্রি প্রিন্ট করা উচিত। এখানে বাম-নীচের অংশ এবং ডান-নিচের অংশের আকার একই হওয়া উচিত। এমনকি একটি সাবট্রি অন্যটি না থাকলেও, আমাদের কোনটি সাবট্রির জন্য কিছু প্রিন্ট করার দরকার নেই তবে এখনও অন্য সাবট্রির জন্য যতটা বড় জায়গা ছেড়ে দেওয়া দরকার। এখন, যদি দুটি সাবট্রি একটিও না হয়, তাহলে আমাদের উভয়ের জন্য জায়গা ছেড়ে দেওয়ার দরকার নেই৷
- প্রতিটি অব্যবহৃত স্থানে একটি খালি স্ট্রিং থাকা উচিত।
- একই নিয়ম অনুসরণ করে সাবট্রি দেখান।
তাই যদি ইনপুট ট্রি −
এর মত হয়
তারপর আউটপুট হবে −
| ৷ | ৷ | ৷ | 1 | ৷ | ৷ | ৷ |
| ৷ | 2 | ৷ | ৷ | ৷ | 3 | ৷ |
| ৷ | ৷ | 4 | ৷ | ৷ | ৷ | ৷ |
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- ফিল() নামক আরেকটি পদ্ধতি সংজ্ঞায়িত করুন, এটি নোড, ম্যাট্রিক্স রেট, lvl, l এবং r মান নেবে
- যদি নোড শূন্য হয়, তাহলে ফিরে আসুন
- ret[lvl, (l + r)/2] :=স্ট্রিং হিসাবে নোড ভাল
- ভরন(নোডের বামে, ret, lvl+1, l, (l+r)/2)
- পূর্ণ করুন(নোডের ডানদিকে, ret, lvl+1, (l+r+1)/2, r)
- প্রধান পদ্ধতি থেকে অনুসরণ করুন −
- h :=গাছের উচ্চতা
- পাতা =2^h – 1
- ক্রম h x পাতার একটি ম্যাট্রিক্স তৈরি করুন এবং এটি ফাঁকা স্ট্রিং দিয়ে পূরণ করুন
- পূর্ণ করুন(root, ret, 0, 0, পাতা)
- রিটার্ন রিটার্ন
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<vector<auto> > v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << "[";
for(int j = 0; j <v[i].size(); j++){
cout << v[i][j] << ", ";
}
cout << "],";
}
cout << "]"<<endl;
}
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;
}
class Solution {
public:
int getHeight(TreeNode* node){
if(!node)return 0;
return 1 + max(getHeight(node->left), getHeight(node->right));
}
void fill(TreeNode* node, vector<vector<string>>& ret, int lvl, int l, int r){
if(!node || node->val == 0)return;
ret[lvl][(l + r) / 2] = to_string(node->val);
fill(node->left, ret, lvl + 1, l, (l + r) / 2);
fill(node->right, ret, lvl + 1, (l + r + 1) / 2, r);
}
vector<vector<string>> printTree(TreeNode* root) {
int h = getHeight(root);
int leaves = (1 << h) - 1;
vector < vector <string> > ret(h, vector <string>(leaves, ""));
fill(root, ret, 0, 0, leaves);
return ret;
}
};
main(){
vector<int> v = {1,2,3,NULL,4};
Solution ob;
TreeNode *root = make_tree(v);
print_vector(ob.printTree(root));
} ইনপুট
[1,2,3,null,4]
আউটপুট
[[, , , 1, , , , ], [, 2, , , , 3, , ], [, , 4, , , , , ],]
