عمودي ترتيب ۾ ثاني وڻ کي پرنٽ ڪيو


تڪليف جي سطح وچولو
بار بار پڇڻ ۾ قبول ڪريو Amazon برائوزر اسٽيڪ Dell فلپٽٽ گرافس MakeMyTrip جو آهي نيٽپسڪو والارٽ ليبز
هاش وڻن وڻ ٽرانسورس

هن مسئلي ۾ ، اسان هڪ پوائنٽر کي ڏنو آهي بنيادي جي جڙڻ کي ظاهر ڪندي بائنري وڻ ۽ توهان جو ڪم عمودي ترتيب ۾ بائنري وڻ کي پرنٽ ڪرڻ آهي.

مثال

پٽ

           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. جيڪڏهن صحيح ، پوء هڪ شروعات ڪريو "اهم ويليو" نئين ویکٹر ۾ ۽ روٽ ويليو (عنصر) کي ویکٹر ۾ شامل ڪريو.
    2. ايلس ، روٽ ويليو کي ویکٹر ۾ شامل ڪريو ڇاڪاڻ ته پهريان کان موجود آهي.
  5. فاصلو ۽ ”اهم ويليو“ نقشي تي.
  6. Recursively callintVerticalTree فنڪشن سان “روٽ. کاٻي”فاصلو -1 ، "م" ۽ "روٽو. صحيح"، فاصلو +1 ، "م" کاٻي ۽ سا subي ذيلي قسمن لاءِ.
  7. نقشو ڇپايو.

عمودي ترتيب ۾ ثنائي وڻ جي پرنٽ لاءِ وضاحت

اسان جو بنيادي خيال بائنري وڻ کي عمودي ترتيب سان ڇپائڻ لاءِ آهي هر وقت دليل طور تبديل ٿيندڙ قيمتن سان ڪم کي بار بار سڏائڻ ۽ دڳ طور اسان جي نقشي کي اپڊيٽ ڪرڻ جي لاءِ اسان کي چاهيون ٿا.

شروعات ، روٽ ، رائي ، رائيٽ.ايل ، root.left.left ۽ نوڊز ۾ نوڊس جي داخل ٿيڻ سان ، اسان وٽ اسان جا قدر اسان جي انپٽ جي طور تي آهن. اسان کي ان آيتن کي هڪ هڪ ڪرڻ گهرجي ، وڻ ۾ کاٻي پاسي کان عنصر شروع ڪندي. اسان هڪ ویکٹر جي شروعات ڪريون ٿا جنهن کان پوءِ نقشي ۾ انجيڪر جي هر انڊيڪس جي چاٻي طور انٽيگر سان داخل ڪئي وئي آهي. هڪ ویکٹر ۾ ، اسان سڀني قدرن کي عمدي طور تي ذخيرو ڪرڻ وارا آهيون ۽ پوءِ نقشي ۾ فاصلو ۽ ڪي ويل ويليو جئين طور تي رکون ٿا ”اهم ويليو“ جوڙو.

مکيه حصو

جڏهن اسان پهريون ڀيرو روٽ کي پاس ڪري رهيا آهيون ، اهو صحيح قيمت نه آهي. پوءِ map.get (فاصلي) ڪيلي ويليو ۾ ذخيرو ڪندو ، جيڪڏهن ڪيٻي ويل ڪوئل سمجهيو وڃي ته نقش جي طور تي 'فاصلو' جي طور تي ان جو ڪوبه قدر نه هوندو ، اسان ويڪٽر جي ڪييو ويليويو کي پيل ڪريو ۽ روٽ کي شامل ڪريون. چاٻي جنهن جو مطلب ڪجهه عنصر جنهن ۾ root.key اشارو ڪري رهيو آهي. جيڪڏهن ڪييو ويليو خالي نه آهي ان جو مطلب آهي ته اڳ ۾ ئي ڪجهه موجود ڪي قدر آهن جيڪي ان سان گڏ ذخيرو ٿيل آهن. اسان کي انهي کي شامل ڪرڻ جي ضرورت آهي “root.key” (اهو عنصر جيڪو ظاهر ڪيو پيو وڃي).

انهي سڀني ۾ ، هڪ وڌيڪ اهم اصطلاح آهي جيڪو مفاصلو آهي. فاصلو جو مطلب روٽ نوڊ کان وڻ ۾ ڪنهن به نوڊ جو عمودي فاصلو ، اسان فاصل طور نمبر حاصل ڪندا آهيون ، جيئن هڪ نن aي سبري وانگر اسان کي منفي نمبر ملندا آهن ۽ صحيح ذيلي وڻن لاءِ اسان مثبت نمبر حاصل ڪندا آهيون ۽ سا theي ۽ صحيح جا forاڻ کان هيٺ. سمجهيو وڃي ٿو روٽ کان 0 مفاصلي تي ، جنهن کي اسان پنهنجو دليل طور ڌارين حوالي ڪندا آهيون. هر وقت اسان هڪ دليل جي طور تي فاصلو وڃون ٿا ، انهي جو مطلب آهي ته اسان انهي سان گڏ ڪجهه اقدار کي محفوظ ڪرڻ وڃي رهيا آهيون جيڪا هڪ نقشي ۾ اهم ثابت ٿي ويندي آهي ، مثال طور ، -2 ، -1 ، 0 ، 1 ، 2 ، 3. ھي ھر ھڪ ویکٹر جون ڪنجيون آھن جنھن ۾ اسان پنھنجا عنصر محفوظ ڪرڻ وارا آھيون.

اسان کي نقشي کان ويليو پرنٽ ڪرڻ گهرجن ، نقشي ۾ موجود سڀني قدرن ۾ ڪيچ آهن (ترتيب ٿيل) کاٻي پاسي کان شروع ٿيندڙ عنصر مطلب آهي - 2 کان 3 جنهن جي معني آهي سا rightي پاسي وارو عنصر. اسان سڀني عنصرن کي عمدي طور تي حاصل ڪنداسين ۽ ان کي پرنٽ ڪيو.

عمودي ترتيب ۾ ثنائي وڻ جي پرنٽ لاءِ عمل درآمد

سي ++ پروگرام

#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]

عمودي ترتيب ۾ ثنائي وڻ جي پرنٽ لاءِ پيچيدگي تجزيو

وقت جي پيچيدگي

اي (اين لوگ) جتي “ن” هڪ وڻ ۾ عنصرن جو تعداد آهي.

خلائي پيچيدگي

اي (ن) جتي “ن” هڪ وڻ ۾ عنصرن جو تعداد آهي.

حوالا