Şaquli qaydada ikili bir ağac çap edin

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Akkolit Amazon BrowserStack Vadi Flipkart Grofers MakeMyTrip Netskope Walmart Laboratoriyaları
Sükut Ağac Ağacın keçidiBaxılıb 78

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

Bu problemdə kökündən bəhs edən bir göstərici verdik ikili ağac və vəzifəniz ikili ağacı şaquli qaydada çap etməkdir.

misal

Input

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

Buraxılış

4
2
1 5 6
3 8
7
9

Izahat

Şaquli qaydada ikili bir ağac çap edinPin

İkili ağacın şaquli qaydada çap edilməsi alqoritmi

  1. Elementləri fərqli qovşaqlara daxil edin.
  2. 0 məsafəni təyin edin.
  3. Kökün doğrudursa null-a bərabər olub olmadığını yoxlayın, sonra qayıdın.
  4. KeyValue xəritədə bir düymə kimi məsafənin dəyərinə qoyun.
    1. Yoxsa yoxlayın “KeyValue” sıfıra bərabərdir.
      1. Doğrudursa, a “KeyValue” yeni bir vektora və bu vektorda kök dəyəri (element) əlavə edin.
    2. Başqa bir halda, bu vektorda kök dəyəri əlavə edin, çünki artıq mövcuddur.
  5. Məsafəni qoyun və "Keyvalue" xəritədə.
  6. İlə printVerticalTree funksiyasını rekursiv olaraq çağırır “Root.left”, məsafə -1, "M"“Root.right”, məsafə +1, "M" müvafiq olaraq sol və sağ alt ağaclar üçün.
  7. Xəritəni çap edin.

Şaquli qaydada ikili bir ağacın çapı üçün izahat

İkili Ağacın şaquli qaydada çap edilməsi üçün əsas fikrimiz hər dəfə bir keçən arqument kimi keçən yenilənmiş dəyərlərlə funksiyaları rekursiv olaraq çağırmaq və xəritəmizi istədiyimiz nəticəyə görə yeniləməyə davam etməkdir.

Kök, root.right, root.left, root.left.left və s.-də qovşaqların yerləşdirilməsindən başlayaraq dəyərlərimiz girişimizdir. Bu girişləri ağacdakı ən sol elementdən başlayaraq bir-bir götürməliyik. Daha sonra vektorun hər bir göstəricisi üçün açar kimi bir tam ədədlə xəritəyə daxil edilən bir vektoru işə salırıq. Bir vektorda, bütün dəyərləri şaquli olaraq saxlayacağıq və sonra məsafələr və keyValue xəritəyə "Keyvalue" cüt.

Əsas hissə

Kökü ilk dəfə ötürdüyümüzdə sıfır dəyəri yoxdur. Sonra map.get (distance) keyValue-da saxlayacaqdır, əgər keyValue xəritədəki düymə olaraq 'məsafə' kimi boş bir vasitə olduğu aşkar edilərsə, heç bir dəyəri yoxdur, sonra bir vektor açarını başlatırıq və kök əlavə edirik. root.key-in göstərdiyi bəzi elementləri ifadə edən düymə. KeyValue sıfır deyilsə, demək olar ki, 'açar' boyunca saxlanılan bəzi mövcud dəyərlər var. Sadəcə “root.key” (göstərilən element) əlavə etməliyik.

Bütün bunlarda məsafədən daha vacib bir müddət var. Mesafə ağacdakı hər hansı bir düyünün kök düyünündən şaquli məsafəsi deməkdir, məsafələr kimi nömrələr alırıq, sol alt ağac kimi mənfi ədədlər alırıq, sağ alt ağaclar üçün də müsbət ədədlər alırıq, sağda və kökün altındakı qovşaqlarda. arqumentlərimizi rekursiv olaraq ötürdüyümüz kökündən 0 məsafədə hesab olunur. Hər dəfə məsafəni mübahisə olaraq keçdiyimiz zaman, bu nümunədə olduğu kimi bir xəritədə açar olduğu bəzi dəyərləri özümüzlə birlikdə saxlayacağımız deməkdir, -2, -1, 0, 1, 2, 3. Bunlar elementlərimizi saxlayacağımız hər bir vektor üçün açarlar.

Dəyərləri xəritədən yazdırmalıyıq, xəritədəki bütün dəyərlərin ən sol element mənasını verən -2 ilə 3 arasındakı düymələr (sıralanmış) var. Bütün elementləri şaquli şəkildə əldə edib çap edəcəyik.

Şaquli qaydada ikili bir ağacın çapı üçün tətbiqetmə

C ++ Proqramı

#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

Java Proqramı

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]

İkili bir ağacın şaquli qaydada çap edilməsi üçün mürəkkəblik analizi

Zamanın mürəkkəbliyi

O (n Logn) hara "N" ağacdakı elementlərin sayıdır.

Kosmik Mürəkkəblik

O (n) hara "N" ağacdakı elementlərin sayıdır.

References

Crack Sistemi Dizayn Müsahibələri
Translate »