C++ में बाइनरी ट्री प्रिंट करना

मान लीजिए हमें एक बाइनरी ट्री को m×n 2D स्ट्रिंग सरणी में इन नियमों के आधार पर प्रदर्शित करना है:

पंक्ति संख्या m दी गई बाइनरी ट्री की ऊंचाई के समान होनी चाहिए।

स्तंभ संख्या n हमेशा एक विषम संख्या होनी चाहिए।

रूट नोड का मान पहली पंक्ति के ठीक बीच में रखा जाना चाहिए जहां इसे रखा जा सकता है। वह स्तंभ और पंक्ति जहां रूट नोड रहता है, शेष स्थान को दो भागों में विभाजित करेगा: बायां-नीचे का भाग और दायां-नीचे का भाग। हमें बाएं उपट्री को बाएं-नीचे के भाग में और दाएं उपट्री को दाएं-नीचे के भाग में प्रिंट करना चाहिए। यहां बायां-नीचे का भाग और दायां-नीचे का भाग समान आकार का होना चाहिए। भले ही एक उपट्री न हो जबकि दूसरी हो, हमें न होने वाले उपट्री के लिए कुछ भी प्रिंट करने की आवश्यकता नहीं है लेकिन फिर भी दूसरे उपट्री जितना बड़ा स्थान छोड़ना होगा। अब, यदि दोनों उपट्री न हों, तो हमें उन दोनों के लिए स्थान छोड़ने की आवश्यकता नहीं है।

प्रत्येक अप्रयुक्त स्थान में एक खाली स्ट्रिंग होनी चाहिए।

उपट्री को उन्हीं नियमों का पालन करते हुए प्रदर्शित करें।

इसलिए यदि इनपुट ट्री इस तरह है:

तो आउटपुट होगा:

हल का दृष्टिकोण

इसे हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे:

• fill() नामक एक अन्य विधि परिभाषित करें, जो node, matrix ret, lvl, l, r लेती है
• यदि नोड null है, तो लौटें
• ret[lvl][(l+r)/2] := नोड मान को स्ट्रिंग के रूप में
• fill(node के बाएं, ret, lvl+1, l, (l+r)/2)
• fill(node के दाएं, ret, lvl+1, (l+r+1)/2, r)
• मुख्य विधि से:
  • h := ट्री की ऊंचाई
  • leaves = 2^h - 1
  • क्रम h x leaves की मैट्रिक्स बनाएं, और इसे खाली स्ट्रिंग से भरें
  • fill(root, ret, 0, 0, leaves)
  • ret लौटाएं

उदाहरण

#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; 
    } 
}; 

int 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, , , , , ],]