Абход парадку ўзроўню бінарнага дрэва


Узровень складанасці серада
Часта пытаюцца ў амазонка яблык Bloomberg Cisco facebook Microsoft
Двайковае дрэва Шырыня Першы пошук чаргу дрэва

Абход парадку ўзроўню дадзенасці бінарнае дрэва гэта тое ж самае, што і BFS бінарнага дрэва. Мы ўжо ведаем пра што на самой справе BFS гэта? калі не, то не трэба адчуваць сябе дрэнна, проста прачытайце ўвесь артыкул і наведайце наш папярэднія артыкулы для лепшага разумення. BFS - гэта абход парадку ўзроўню, пры якім мы наведваем вузлы a бінарнае дрэва злева направа на кожным узроўні.

Вось прыклад BFS:

Абход парадку ўзроўню бінарнага дрэва

Мы рухаемся злева направа з кожнага ўзроўню і друкуем значэнні:

Абход парадку ўзроўню бінарнага дрэва

BFS вышэйзгаданага дрэва складае 0,1,2,3,4,5,6.

Пры выкарыстанні Структура дадзеных чаргі, мы знаходзім абход узроўневага парадку. Мы пачынаем з каранёвай сістэмы, пасля чаго ўстаўляем корань у BFS і ўстаўляем усіх суседзяў гэтага вузла ў чаргу. Пасля гэтага выгрузіце вузел з чаргі і дадайце яго ў BFS, калі яго не наведалі, і дадайце ў чаргу ўвесь сусед (не наведваны). Паўтарайце, пакуль памер чаргі не будзе роўны нулю.

Рэалізацыя для абходу парадку ўзроўню бінарнага дрэва

/*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

Складанасць часу

O (N) дзе N - колькасць вузлоў у дадзеным двайковым дрэве.

Касмічная складанасць

O (максімальны_уровень) дзе max_level адносіцца да максімальнай колькасці элементаў на любым узроўні двайковай сістэмы дрэва.

Спасылкі