二分木のレベル順走査


難易度 ミディアム
よく聞かれる Amazon (アマゾン) Apple ブルームバーグ Cisco Facebook マイクロソフト
二分木 幅優先探索 キュー

レベルオーダートラバーサル 与えられた 二分木 二分木のBFSと同じです。 私たちはすでに知っていますか 実際に何 BFS ありますか? そうでない場合は、気分が悪くなる必要はありません。記事全体を読んで、 前の記事 より良い理解のために。 BFSは、次のノードにアクセスするレベル順トラバーサルです。 二分木 すべてのレベルで左から右へ。

BFSの例を次に示します。

二分木のレベル順走査

すべてのレベルから左から右に移動し、値を出力します。

二分木のレベル順走査

上記のツリーのBFSは0,1,2,3,4,5,6、XNUMX、XNUMX、XNUMX、XNUMX、XNUMX、XNUMXです。

の使用により キューのデータ構造、 レベル順の走査を見つけます。 ルートから開始し、ルートをBFSに挿入し、そのノードのすべてのネイバーをキューに挿入します。 その後、ノードをキューからポップし、訪問されていない場合はBFSに追加し、すべての隣接ノード(訪問されていない)をキューに追加します。 キューのサイズがnullに等しくなくなるまで、これを繰り返します。

二分木のレベル順トラバーサルの実装

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

時間の複雑さ

オン) ここで、Nは指定されたバイナリツリー内のノードの数です。

スペースの複雑さ

O(max_level) ここで、max_levelは、バイナリの任意のレベルの要素の最大数を指します。 ツリー.

リファレンス