अनुलंब क्रमाने बायनरी ट्री प्रिंट करा


अडचण पातळी मध्यम
वारंवार विचारले एकत्रित ऍमेझॉन ब्राउझर स्टॅक डेल फ्लिपकार्ट ग्रॉफर्स मेकमायट्रिप नेटस्कोप वॉलमार्ट लॅब
हॅश झाड ट्री ट्रॅव्हर्सल

या समस्येमध्ये आम्ही मूळ दर्शविणारा एक पॉईंटर दिला आहे बायनरी ट्री आणि आपले कार्य उभ्या क्रमाने बायनरी ट्री मुद्रित करणे आहे.

उदाहरण

इनपुट

           1
        /    \ 
      2         3
    / \      /  \
  4    5    6    7
               \     \ 
                8      9

उत्पादन

4
2
1 5 6
3 8
7
9

स्पष्टीकरण

अनुलंब क्रमाने बायनरी ट्री प्रिंट करा

अनुलंब क्रमाने बाइनरी ट्री प्रिंट करण्यासाठी अल्गोरिदम

  1. वेगवेगळ्या नोड्सवर घटक घाला.
  2. 0 पर्यंत अंतर सेट करा.
  3. जर रूट शून्य असल्यास बरोबर आहे का ते तपासा तर परत या.
  4. नकाशामध्ये की म्हणून व्हॅल्यूला अंतरांच्या मूल्यावर सेट करा.
    1. तपासा “की व्हॅल्यू” शून्य आहे.
      1. खरे असल्यास, प्रारंभ करा a “की व्हॅल्यू” नवीन वेक्टरवर जा आणि त्या वेक्टरमध्ये रूट व्हॅल्यू (एलिमेंट) जोडा.
    2. अन्यथा, त्या वेक्टरमध्ये मूळ मूल्य जोडा कारण आधीपासून विद्यमान आहे.
  5. अंतर ठेवा आणि “कळ” नकाशावर.
  6. सह वारंवार प्रिंटवेर्टिकलट्री फंक्शन कॉल करते “Root.left”, अंतर -1, "M" आणि “Root.right”, अंतर +1, "M" अनुक्रमे डावी आणि उजवी उपशीर्षे करीता.
  7. नकाशा मुद्रित करा.

अनुलंब क्रमाने बाइनरी ट्री प्रिंट करण्यासाठी स्पष्टीकरण

उभ्या ऑर्डरमध्ये बायनरी ट्री प्रिंट करण्याची आमची मुख्य कल्पना म्हणजे प्रत्येक वेळी वितर्क म्हणून उत्तीर्ण केलेल्या अद्ययावत मूल्यांसह कार्ये पुन्हा पुन्हा कॉल करणे आणि आम्हाला पाहिजे असलेल्या आउटपुटनुसार आपला नकाशा अद्यतनित करणे होय.

रूट, रूट, राइट, रूट.लेफ्ट, रूट.लेफ्ट.लेफ्ट आणि इतर काही ठिकाणी नोड्सच्या सहाय्याने प्रारंभ करुन आपल्याकडे इनपुट म्हणून आपली व्हॅल्यूज आहेत. झाडेतील सर्वात डावीकडील घटकापासून सुरुवात करुन आपल्याला हे इनपुट एक-एक करून घेणे आवश्यक आहे. आम्ही वेक्टरला आरंभ करतो जो नंतर वेक्टरच्या प्रत्येक अनुक्रमणिकेसाठी पूर्णांक असलेल्या नकाशामध्ये घातला जातो. एका वेक्टरमध्ये आपण सर्व व्हॅल्यूज अनुलंब संचयित करणार आहोत आणि नंतर नकाशामध्ये अंतर आणि की व्हॅल्यू ठेवू. “कळ” जोडी

मुख्य भाग

जेव्हा आपण प्रथम रूट पास करतो तेव्हा त्यास शून्य किंमत नसते. नंतर नकाशे.गेट (अंतर) कीवॅल्यूमध्ये संचयित करेल, जर की व्हॅल्यूला काही अंतर नसले तर त्यास काही मूल्य नसते म्हणून किल्यू 'अंतर' म्हणून आढळले तर आपण वेक्टर की व्हॅल्यू आरंभ करून रूट जोडू. की ज्याचा अर्थ असा आहे की ज्यावर root.key सूचित करीत आहे. की व्हॅल्यू शून्य नसल्यास याचा अर्थ असा की तेथे आधीपासूनच अस्तित्वात असलेली काही मूल्ये 'की' सह एकत्रित केलेली आहेत. आम्हाला फक्त ते “रूट.की” (सूचित केले जाणारे घटक) जोडण्याची आवश्यकता आहे.

या सर्वांमध्ये आणखी एक महत्त्वाची पद आहे जी अंतर आहे. अंतर म्हणजे रूट नोडपासून झाडाच्या कोणत्याही नोडचे अनुलंब अंतर, आपल्याला अंतराच्या रूपात संख्या मिळते, डावीक उपशाखा म्हणून आपल्याला नकारात्मक संख्या मिळतात आणि उजव्या उपखंडांसाठी आपल्याला सकारात्मक संख्या मिळतात आणि मुळाच्या खाली उजवीकडील नोड्स मिळतात. मूळ पासून 0 अंतरावर मानले जाते, जे आम्ही आमचे युक्तिवाद पुनरावृत्ती म्हणून पास करतो. प्रत्येक वेळी आपण वितर्क म्हणून अंतर पार केल्यावर याचा अर्थ असा होतो की आम्ही यासह काही मूल्ये संचयित करणार आहोत जी या उदाहरणाप्रमाणे -2, -1, 0, 1, 2, These. प्रत्येक वेक्टरसाठी या की आहेत ज्यामध्ये आपण आपले घटक संग्रहित करणार आहोत.

आम्हाला नकाशे वरून मूल्ये मुद्रित करण्याची आवश्यकता आहे, नकाशामधील सर्व मूल्यांमध्ये डावीकडील घटकांपासून प्रारंभ होणार्‍या की (क्रमवारी लावलेले) आहेत -2 ते 3 म्हणजे उजवीकडील घटक. आपल्याला सर्व घटक अनुलंब दिसेल आणि ते प्रिंट करू.

अनुलंब क्रमाने बाइनरी ट्री प्रिंट करण्यासाठी अंमलबजावणी

सी ++ प्रोग्राम

#include <iostream>
#include <vector>
#include <map>
using namespace std;

struct Node
{
    int key;
    Node *left, *right;
};
struct Node* newNode(int key)
{
    struct Node* node = new Node;
    node->key = key;
    node->left = node->right = NULL;
    return node;
}
void printVerticalTree(Node* root, int distance, map<int, vector<int>> &mymap)
{
    if (root == NULL)
        return;

    mymap[distance].push_back(root->key);

    printVerticalTree(root->left, distance-1, mymap);

    printVerticalTree(root->right, distance+1, mymap);
}
void printVerticalOrder(Node* root)
{
    map < int,vector<int> > mymap;
    int distance = 0;
    printVerticalTree(root, distance,mymap);
    map< int,vector<int> > :: iterator it;
    for (it=mymap.begin(); it!=mymap.end(); it++)
    {
        for (int i=0; i<it->second.size(); ++i)
            cout << it->second[i] << " ";
        cout << endl;
    }
}
int main()
{
    Node *root = newNode(3);
    root->left = newNode(4);
    root->right = newNode(6);
    root->left->left = newNode(8);
    root->left->right = newNode(11);
    root->right->left = newNode(14);
    root->right->right = newNode(17);
    root->right->left->right = newNode(18);
    root->right->right->right = newNode(25);
    cout << "Vertical order traversal is \n";
    printVerticalOrder(root);
    return 0;
}
Vertical order traversal is
8
4
3 11 14
6 18
17
25

जावा कार्यक्रम

import java.util.TreeMap;
import java.util.Vector;
import java.util.Map.Entry;

class printBinarytreeVertical
{
    static class Node
    {
        int key;
        Node left;
        Node right;
        Node(int data)
        {
            key = data;
            left = null;
            right = null;
        }
    }
    static void printVerticalTree(Node root, int distance, TreeMap<Integer,Vector<Integer>> map)
    {

        if(root == null)
        {
            return;
        }
        Vector<Integer> keyValue = map.get(distance);
        if(keyValue == null)
        {
            keyValue = new Vector<>();
            keyValue.add(root.key);
        }
        else
            keyValue.add(root.key);

        map.put(distance, keyValue);

        printVerticalTree(root.left, distance-1, map);

        printVerticalTree(root.right, distance+1, map);
    }
    static void printVerticalOrder(Node root)
    {
        TreeMap<Integer,Vector<Integer>> m = new TreeMap<>();
        int distance =0;
        printVerticalTree(root,distance,m);
        for (Entry<Integer, Vector<Integer>> getentry : m.entrySet())
        {
            System.out.println(getentry.getValue());
        }
    }
    public static void main(String[] args)
    {
        Node root = new Node(3);
        root.left = new Node(4);
        root.right = new Node(6);
        root.left.left = new Node(8);
        root.left.right = new Node(11);
        root.right.left = new Node(14);
        root.right.right = new Node(17);
        root.right.left.right = new Node(18);
        root.right.right.right = new Node(25);
        System.out.println("Vertical Order traversal is");
        printVerticalOrder(root);
    }
}
Vertical Order traversal is
[8]
[4]
[3, 11, 14]
[6, 18]
[17]
[25]

अनुलंब ऑर्डरमध्ये बायनरी ट्री प्रिंट करण्यासाठी जटिलता विश्लेषण

वेळ कॉम्प्लेक्सिटी

ओ (एन लॉगन) जेथे “एन” झाडामध्ये घटकांची संख्या आहे.

स्पेस कॉम्प्लेक्सिटी

O (n) जेथे “एन” झाडामध्ये घटकांची संख्या आहे.

संदर्भ