İkili Ağacın Səviyyə Sifarişinin Keçməsi

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Amazon alma Bloomberg Cisco Facebook microsoft
İkili ağac Genişlik İlk Axtarış Queue AğacBaxılıb 29

Səviyyə Sifarişinin Dəyişməsi bir verilmiş ikili ağac ikili ağacın BFS ilə eynidir. Onsuz da bilirikmi? əslində nədir BFS nədir? yoxsa onda özünüzü pis hiss etməyinizə ehtiyac yoxdur, sadəcə bütün məqaləni oxuyun və bizimkini ziyarət edin əvvəlki məqalələr daha yaxşı başa düşmək üçün. BFS, a düymələrini ziyarət etdiyimiz bir səviyyə sifarişidir ikili ağac hər səviyyədə soldan sağa.

Budur BFS nümunəsi:

İkili Ağacın Səviyyə Sifarişinin KeçməsiPin

Hər səviyyədən soldan sağa hərəkət edirik və dəyərləri çap edirik:

İkili Ağacın Səviyyə Sifarişinin KeçməsiPin

Yuxarıdakı ağacın BFS-si 0,1,2,3,4,5,6-dır.

İstifadəsi ilə Sıra məlumat strukturu, səviyyə sifarişinin keçidini tapırıq. Kökdən başlayırıq, sonra BFS-yə kök əlavə edirik və həmin düyünün bütün qonşularını növbəyə əlavə edirik. Bundan sonra düyünü növbədən çıxarın və ziyarət edilmədiyi təqdirdə BFS-yə əlavə edin və hamısını qonşu (dəvət olunmamış) növbəyə əlavə edin. Növbənin ölçüsü null-a bərabər olmayanadək təkrarlayın.

İkili Ağacın Səviyyə Sifarişinin Keçməsi üçün İcra

/*C++ Implementation to prin the BFS of given binary tree*/ 
#include<bits/stdc++.h> 
using namespace std; 
/*Structure of Node of BT which contain pointer to left child and right child and a data for node.*/ 
struct Node{ 
       int data; 
       struct Node* left;// for left child; 
       struct Node* right;// for right child; 
       Node(int value)// create a node using new Node; 
       { 
         data=value; 
         left=NULL; 
         right=NULL; 
       } 
}; 
/*Function which print level order of the given tree*/ 
void level_order(Node* root) 
{ 
    if(root==NULL) 
    { 
       return; 
    } 
    queue<Node*> q; 
    q.push(root); 
    while(!q.empty()) 
    { 
       Node* temp=q.front(); 
       cout<<temp->data<<" "; 
       q.pop(); 
       if(temp->left!=NULL) 
       { 
          q.push(temp->left); 
       } 
       if(temp->right!=NULL) 
       { 
           q.push(temp->right); 
       } 
    } 
    cout<<endl; 
} 
int main() 
{ 
     /*construct tree*/ 
     Node* root= new Node(0);//root node; 
     root->left= new Node(1); 
     root->right= new Node(2); 
     root->left->left= new Node(3); 
     root->left->right= new Node(4); 
     root->right->left= new Node(5); 
     root->right->right= new Node(6); 
     cout<<"Level order traversal of BT: "; 
     level_order(root); 
     return 0; 
}
Level order traversal of BT: 0 1 2 3 4 5 6

Zamanın mürəkkəbliyi

O (N) burada N - verilən ikili ağacdakı qovşaq sayı.

Kosmik Mürəkkəblik

O (max_level) burada max_level ikili səviyyənin istənilən səviyyəsindəki maksimum element sayına aiddir ağac.

References

Translate »