İkili Ağacın Üst Görünüşü

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Amazon Paytm Samsung Walmart Laboratoriyaları
İkili ağac Dərinlik İlk Axtarış Ağac Ağacın keçidiBaxılıb 32

A-nın üst görünüşü ikili ağac olduqda görünən qovşaqların çoxluğudur ağac yuxarıdan baxılır. İkili bir ağac verildiyi üçün, ikili ağacın ən sol tərəfdən ən sağ üfüqi səviyyə ilə Çıxış üst görünüşü.

misal

Məsələn 1

İkili Ağacın Üst GörünüşüPin

İkili Ağacın Üst GörünüşüPin

Məsələn 2

İkili Ağacın Üst GörünüşüPin

İkili Ağacın Üst Görünüşü üçün həll növləri

  1. DFS
  2. BFS

Dərinlik İlk Axtarış (DFS) / İnorder Traversal

İkili Ağacın Üst Görünüşünə Yanaşma

Biz çıxış edirik ikili ağacın kənar keçidi və hərəkət zamanı rast gəlinən hər bir düyünün şaquli hündürlüyünü (h) və üfiqi eni (w) izləyin.

  • Müəyyən bir üfüqi genişlik səviyyəsi ilk dəfə ziyarət edildikdə, bu üfüqi səviyyə (həmin qovşaqın w dəyəri) ilə qovşaq məlumatlarını (qovşağı yuxarı görünüşdə saxlayın) və bu qovşağın şaquli hündürlüyünü eşidirik. yəni Xəritə [üfüqi genişlik -> (node.data, şaquli hündürlük)].
  • Müəyyən bir üfüqi genişlik səviyyəsi əvvəldən ziyarət edilmişdirsə, o üfüqi eni üçün uyğunlaşdırılan şaquli hündürlüyü (bu düyünün h dəyəri) yoxlayırıq. Bir cari düyünün şaquli hündürlüyü eşlenen şaquli hündürlükdən azdırsa (bu, cari düyün əvvəllər eşlenen düyünün üstündə şaquli olaraq yerləşdiyində və buna görə əvvəllər eşlenen düyünün üstünə bükülən ağacın yuxarı hissəsində görünəndə olur), onda sadəcə eşlenen dəyəri dəyişdiririk cari üfüqi enin {cari düyün məlumatı, cari düyünün üfüqi hündürlüyü}.
  • Keçid bitdikdən sonra sadəcə yuxarı görünüş node dəyərlərini daxil edin üfüqi səviyyələrinin sırası.

Aşağıda ikili ağacın hər bir düyünü üçün {üfüqi eni, şaquli hündürlüyü} təsvir edirik:

İkili Ağacın Üst GörünüşüPin

Alqoritm

  1. İkili ağacın üst görünüşünü saxlamaq üçün bir xəritə yaradın.
  2. İkili ağacın sərhəd keçidini həyata keçirin.
  3. Keçid zamanı ağac düyünlərinin hər birinin şaquli hündürlüyünü (h) və üfüqi enini (w) izləyin.
  4. Hal-hazırda ziyarət olunan düyün üçün üfüqi genişlik səviyyəsinin olub olmadığını yoxlayın.
  5. Mövcud üfüqi səviyyə ziyarət edilməyibsə, {cari üfüqi en -> (cari düyün məlumatları, cari şaquli hündürlük)} xəritəsini düzəldin.
  6. Mövcud üfüqi genişlik səviyyəsi əvvəldən ziyarət edilmişdirsə, müqayisə edin şaquli hündürlük dəyəri artıq eşlənmişdir cari düyünün şaquli hündürlüyü ilə cari üfüqi səviyyə üçün.
    1. Əgər eşlenen şaquli hündürlüyün dəyəri cari düyünün şaquli hündürlüyündən daha böyükdür (bu, cari düyün əvvəllər eşlənmiş düyünün üstündə şaquli uzandıqda və buna görə əvvəllər eşlenen düyünün üstündə yerləşən ağacın yuxarı hissəsində görünəndə olur), cari üfüqi eni üçün eşlenen dəyəri dəyişdirin {cari düyün məlumatları, cari şaquli hündürlük}. yəni {cari üfüqi genişlik -> (cari düyün məlumatları, cari şaquli hündürlük)}.
  7. Keçiddən sonra xəritədə saxlanılan üst görünüşü çıxartmaq kifayətdir.

Yuxarıdakı alqoritm aşağıda təsvir edilmişdir:

İkili Ağacın Üst GörünüşüPin İkili Ağacın Üst GörünüşüPin İkili Ağacın Üst GörünüşüPin İkili Ağacın Üst GörünüşüPin İkili Ağacın Üst GörünüşüPin İkili Ağacın Üst GörünüşüPin İkili Ağacın Üst GörünüşüPin İkili Ağacın Üst GörünüşüPin

İkili Ağacın Üst Görünüşünü çap etmək üçün tətbiqetmə

C ++ Proqramı
#include <iostream>
#include <bits/stdc++.h>
using namespace std;

// defining the tree node
class Node
{
    public : 
    int data;
    Node *left;
    Node *right;
    
    // constructor for initialization
    Node(int num)
    {
        data = num;
        left = right = NULL;
    }
};

/* the function performs inorder traversal and stores top view
of the binary tree. 
for every node encountered during the traversal we have it's : 
w -> horizontal depth(width)
h -> vertical depth(height)
*/
void inorder(Node *root,int w,int h, map<int,pair<int,int>> &Map)
{ 
    if(root == NULL) 
    return; 
    
    inorder(root->left,w-1,h+1,Map);
  
    /* check if a particular horizontal level has been visited or not */
    if(Map.find(w) == Map.end())
        Map[w] = make_pair(root->data,h); 
    
    /* 
    if particular horizontal level has been visited 
    then check if height of current node is less than
    the previous node met at same horizontal level, if this 
    is true then the current node should replace previous node
    in top view of the binary tree */
    
    else if(Map[w].second>h)
        Map[w] = make_pair(root->data,h);
    
    inorder(root->right,w+1,h+1,Map); 
} 
  
/* function should print the topView of 
 the binary tree */ 
void topView(Node *root)
{ 
    if(root ==  NULL)
    return;
    
    /* map to store node at each vertical(horizontal) distance(Level)
    i.e. stores top view */
    map<int,pair<int,int>> Map; 
  
    // obtain top view of binary tree into the Map
    inorder(root,0,0,Map); 
    
    /* traverse the map and print top view */
    for(auto i : Map)
    cout<<i.second.first<<" ";
} 

// main function to implement above functions
int main() 
{
    /*

ikili qurmaq

 tree*/
    Node *root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->right->right = new Node(5);
    root->left->right = new Node(4);
    root->left->right->right = new Node(6);
    root->left->right->right->right = new Node(7);
    root->left->right->right->right->right = new Node(8);
    
    topView(root);
    
    return 0;
}
2 1 3 5 8
Java proqramı
import java.io.*;
import java.util.*;

class tutorialCup 
{
    static class Node
    {
        int data;
        Node left;
        Node right;
        
        Node(int num)
        {
            data = num;
            left = right = null;
        }
    };
    // class definition to handle pairs
    static class pair
    {
        int nodeData;
        int height;
        
        pair(int key,int num)
        {
            nodeData = key;
            height = num;
        }
    }
    
    /* the function performs inorder traversal and stores top view
    of the binary tree. 
    for every node encountered during the traversal we have it's : 
    w -> horizontal depth(width)
    h -> vertical depth(height)
    */
    static void inorder(Node root,int w,int h, TreeMap <Integer,pair> Map)
    { 
        if(root == null) 
        return; 
        
        inorder(root.left,w-1,h+1,Map);
        
        /* check if a particular horizontal level has been visited or not */
        if(!Map.containsKey(w))
            Map.put(w,new pair(root.data,h)); 
        
        /* if particular horizontal level has been visited 
        then check if height of current node is less than
        the previous node met at same horizontal level, if this 
        is true then the current node should replace previous node
        in top view of the binary tree */
        else if(Map.get(w).height > h)
            Map.put(w,new pair(root.data,h));
        
        inorder(root.right,w+1,h+1,Map); 
    } 
      
    /* function should print the topView of 
     the binary tree */ 
    static void topView(Node root)
    { 
        if(root == null)
        return;
        
        /* map to store node at each vertical(horizontal) distance(Level)
        i.e. stores top view */
        TreeMap<Integer,pair> Map = new TreeMap<>();
      
        // obtain top view of binary tree into the Map
        inorder(root,0,0,Map); 
        
        /* traverse the map and print top view */
        for (Map.Entry<Integer, pair> i : Map.entrySet()) 
            System.out.print(i.getValue().nodeData+" ");
    } 
    
    /* main function to implement above function */
    public static void main (String[] args) 
    {
        /* construct the binary tree */
        Node root = new Node(1);  
        root.left = new Node(2);
        root.right = new Node(3);
        root.right.right = new Node(5);
        root.left.right = new Node(4);
        root.left.right.right = new Node(6);
        root.left.right.right.right = new Node(7);
        root.left.right.right.right.right = new Node(8);
        
        topView(root);
    }
}
2 1 3 5 8

İkili Ağacın Üst Görünüşü üçün Mürəkkəblik Təhlili

  1. Zamanın mürəkkəbliyi: T (n) = O (n)
  2. Məkan Mürəkkəbliyi: A (n) = O (n), ən pis hal ağac əyildikdə əldə edilir.

Genişlik ilk axtarış (BFS) / Səviyyə sifarişinin keçməsi

İkili Ağacın Üst Görünüşünə Yanaşma

İkili ağacın BFS-sini yerinə yetiririk. Bu yanaşmanın arxasındakı fikir budur ki, BFS zamanı ağacın müəyyən bir üfüqi səviyyə aşağıdakı bütün üfüqi səviyyələrdən əvvəl keçilir, buna görə şaquli izləməli deyilik. ağacın hər birinin hündürlüyü qovşaqlar. Sadəcə ağac qovşaqlarının hər birinin üfüqi dərinliyini / genişliyini izləyirik.

Biz yerinə yetiririk BFS ağacın keçməsi. Traversal zamanı, cari düyünün üfüqi eni ziyarət edilməyibsə, cari üfiqi səviyyə ilə cari node məlumatlarını müqayisə edirik. yəni {cari üfüqi səviyyə -> cari düyün məlumatları}. Bu Xəritəçəkmə bir xəritədə saxlanılır. Keçidin sonunda, sadəcə xəritədə saxlanılan üst görünüşü çıxardırıq.

Aşağıda ikili ağacın hər bir düyünü üçün {üfüqi eni, şaquli hündürlüyü} təsvir edirik:

Pin

Alqoritm

  1. BFS keçidi üçün qovşaqları və uyğun üfüqi genişlikləri saxlayan bir növbə yaradın.
  2. Açarın üfüqi enində və eşlenen dəyərin düyün məlumatları olduğu ikili ağacın üst görünüşünü saxlayan bir xəritə yaradın.
  3. Verilən ikili ağacın BFS keçidini həyata keçirin.
  4. Hal-hazırda ziyarət olunan düyün üçün üfüqi eninin əvvəlcədən ziyarət edilib-edilmədiyini yoxlayın.
  5. Üfüqi genişlik ilk dəfə ziyarət olunursa, cari üfüqi genişliyi cari düyün məlumatlarına uyğunlaşdırın.
  6. Keçiddən sonra xəritədə saxlanılan üst görünüşü çıxarın.

Yuxarıda alqoritm aşağıda təsvir edilmişdir:

Pin Pin Pin Pin Pin Pin Pin Pin Pin

İkili Ağacın Üst Görünüşü üçün Tətbiq

C ++ Proqramı
#include <iostream>
#include <bits/stdc++.h>
using namespace std;

// defining the tree node
class Node
{
    public : 
    int data;
    Node *left;
    Node *right;
    
    // constructor for initialization
    Node(int num)
    {
        data = num;
        left = right = NULL;
    }
};

// function to obtain top-view of the binary tree
void topView(Node *root)
{
    if(root == NULL)
    return;
    
    /* map to store node at each vertical(horizontal) distance(Level)
    i.e. stores top view */
    map<int,int> Map;
    queue<pair<Node*,int>> q;
    
    q.push({root,0});
    
    // obtain top view of binary tree into the Map
    while(!q.empty())
    {
        auto top = q.front();
        q.pop();
        
        Node *curr = top.first;
        int horizontalLevel = top.second;
        
        /* if the current horizontal Level has not been
        visited then the first node encountered at this horizontal 
        level during level order traversal should be displayed 
        in top view of the tree */
        if(Map.find(horizontalLevel) == Map.end())
        Map[horizontalLevel] = curr->data;
        
        if(curr->left)
        q.push({curr->left,horizontalLevel-1});
        
        if(curr->right)
        q.push({curr->right,horizontalLevel+1});
    }
    
    // print the top view in order of horizontal Level
    for(auto i : Map)
    cout<<i.second<<" ";
}

// main function to implement above functions
int main() 
{
    /* construct the binary tree*/
    Node *root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->right->right = new Node(5);
    root->left->right = new Node(4);
    root->left->right->right = new Node(6);
    root->left->right->right->right = new Node(7);
    root->left->right->right->right->right = new Node(8);
    
    topView(root);    
    return 0;
}
2 1 3 5 8
Java proqramı
import java.io.*;
import java.util.*;

class tutorialCup 
{
    static class Node
    {
        int data;
        Node left;
        Node right;
        
        Node(int num)
        {
            data = num;
            left = right = null;
        }
    };
    // class definition to handle pairs
    static class pair
    {
        int nodeData;
        int height;
        
        pair(int key,int num)
        {
            nodeData = key;
            height = num;
        }
    }
    
    /* the function performs inorder traversal and stores top view
    of the binary tree. 
    for every node encountered during the traversal we have it's : 
    w -> horizontal depth(width)
    h -> vertical depth(height)
    */
    static void inorder(Node root,int w,int h, TreeMap <Integer,pair> Map)
    { 
        if(root == null) 
        return; 
        
        inorder(root.left,w-1,h+1,Map);
        
        /* check if a particular horizontal level has been visited or not */
        if(!Map.containsKey(w))
            Map.put(w,new pair(root.data,h)); 
        
        /* if particular horizontal level has been visited 
        then check if height of current node is less than
        the previous node met at same horizontal level, if this 
        is true then the current node should replace previous node
        in top view of the binary tree */
        else if(Map.get(w).height > h)
            Map.put(w,new pair(root.data,h));
        
        inorder(root.right,w+1,h+1,Map); 
    } 
      
    /* function should print the topView of 
     the binary tree */ 
    static void topView(Node root)
    { 
        if(root == null)
        return;
        
        /* map to store node at each vertical(horizontal) distance(Level)
        i.e. stores top view */
        TreeMap<Integer,pair> Map = new TreeMap<>();
      
        // obtain top view of binary tree into the Map
        inorder(root,0,0,Map); 
        
        /* traverse the map and print top view */
        for (Map.Entry<Integer, pair> i : Map.entrySet()) 
            System.out.print(i.getValue().nodeData+" ");
    } 
    
    /* main function to implement above function */
    public static void main (String[] args) 
    {
        /* construct the binary tree */
        Node root = new Node(1);  
        root.left = new Node(2);
        root.right = new Node(3);
        root.right.right = new Node(5);
        root.left.right = new Node(4);
        root.left.right.right = new Node(6);
        root.left.right.right.right = new Node(7);
        root.left.right.right.right.right = new Node(8);
        
        topView(root);
    }

}
2 1 3 5 8

İkili Ağacın Üst Görünüşü üçün Mürəkkəblik Təhlili

  1. Zamanın mürəkkəbliyi: T (n) = O (n)
  2. Məkan Mürəkkəbliyi: A (n) = O (n), ən pis hal ağac əyildikdə əldə edilir.

References

Translate »
1