मान लीजिए कि हमें इन नियमों के आधार पर m*n 2D स्ट्रिंग सरणी में एक बाइनरी ट्री प्रदर्शित करना है -
- पंक्ति संख्या m दिए गए बाइनरी ट्री की ऊंचाई के समान होनी चाहिए।
- कॉलम संख्या n हमेशा एक विषम संख्या होनी चाहिए।
- रूट नोड का मान पहली पंक्ति के ठीक बीच में रखा जाना चाहिए जिसे इसे रखा जा सकता है। स्तंभ और पंक्ति जहां रूट नोड रहता है, शेष स्थान को दो भागों में अलग कर देगा। ये बाएँ-नीचे भाग और दाएँ-नीचे भाग हैं। हमें लेफ्ट सबट्री को लेफ्ट-बॉटम पार्ट में प्रिंट करना चाहिए और राइट सबट्री को राइट-बॉटम पार्ट में प्रिंट करना चाहिए। यहाँ बाएँ-नीचे भाग और दाएँ-निचले भाग का आकार समान होना चाहिए। यहां तक कि अगर एक सबट्री कोई नहीं है जबकि दूसरा नहीं है, हमें किसी भी सबट्री के लिए कुछ भी प्रिंट करने की आवश्यकता नहीं है, लेकिन फिर भी दूसरे सबट्री के लिए स्पेस को उतना ही बड़ा छोड़ना होगा। अब, यदि दो उपवृक्ष कोई नहीं हैं, तो हमें उन दोनों के लिए स्थान छोड़ने की आवश्यकता नहीं है।
- प्रत्येक अप्रयुक्त स्थान में एक खाली स्ट्रिंग होनी चाहिए।
- समान नियमों का पालन करते हुए उप-वृक्ष प्रदर्शित करें।
तो अगर इनपुट ट्री जैसा है -
तब आउटपुट होगा -
| | | | 1 | | | |
| | 2 | | | | 3 | |
| | | 4 | | | | |
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- भरने () नामक एक अन्य विधि को परिभाषित करें, यह नोड, मैट्रिक्स रिट, एलवीएल, एल और आर मान लेगा
- यदि नोड शून्य है, तो वापस आएं
- ret[lvl, (l + r)/2] :=नोड वैल स्ट्रिंग के रूप में
- भरें(नोड के बाएं, सेवानिवृत्त, lvl+1, l, (l+r)/2)
- भरें (नोड का दायां, रिट, एलवीएल+1, (एल+आर+1)/2, आर)
- मुख्य विधि से निम्नलिखित करें -
- h :=पेड़ की ऊंचाई
- पत्तियां =2^एच - 1
- एच x पत्तियों के क्रम का एक मैट्रिक्स बनाएं, और इसे रिक्त स्ट्रिंग्स से भरें
- भरें(रूट, रेट, 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, , , , , ],]