የሁለትዮሽ ዛፍ ደረጃ ማቋረጥ


የችግር ደረጃ መካከለኛ
ውስጥ በተደጋጋሚ ተጠየቀ አማዞን ፓም ብሉምበርግ Cisco ፌስቡክ የ Microsoft
ሁለትዮሽ ዛፍ ስፌት የመጀመሪያ ፍለጋ ተራ ዛፍ

ደረጃ ማዘዋወር ከተሰጠ ሁለትዮሽ ዛፍ ከ ‹ቢኤፍኤስ› ሁለትዮሽ ዛፍ ጋር ተመሳሳይ ነው ፡፡ ስለ ቀድሞው አውቀናልን? በእውነቱ 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

የጊዜ ውስብስብነት

ኦ (ኤን) በተሰጠው የሁለትዮሽ ዛፍ ውስጥ የአንጓዎች ቁጥር N የት ነው።

የቦታ ውስብስብነት

ኦ (ከፍተኛ_ደረጃ) max_level በየትኛውም የሁለትዮሽ ደረጃ ውስጥ ከፍተኛውን የንጥሎች ብዛት የሚያመለክት ዛፍ.

ማጣቀሻዎች