二叉樹的層級順序遍歷


難度級別
經常問 亞馬遜 蘋果 彭博社 思科 Facebook Microsoft微軟
二叉樹 廣度優先搜索 隊列

級別順序遍歷 給定的 二叉樹 與二叉樹的BFS相同。 我們是否已經知道 到底是什麼 BFS 是什麼? 如果不是這樣,則不必感到難過,只需閱讀整篇文章,然後訪問我們的 以前的文章 以便更好地理解。 BFS是一個級別順序遍歷,其中我們訪問一個 二叉樹 從左到右在每個級別。

這是BFS的示例:

二叉樹的層級順序遍歷

我們在每個級別上從左向右移動並打印值:

二叉樹的層級順序遍歷

上面的樹的BFS為0,1,2,3,4,5,6、XNUMX、XNUMX、XNUMX、XNUMX、XNUMX、XNUMX。

通過使用 隊列數據結構, 我們發現水平順序遍歷。 我們從root開始,然後將root插入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表示二進制的任何級別中的最大元素數 .

參考