একটি বাইনারি ট্রি দেওয়া আছে। লেভেল অর্ডার ট্রাভার্সাল (BFS) করতে হবে। উদাহরণ ট্রি:
ট্রাভার্সাল সিকোয়েন্স: [10, 5, 16, 8, 15, 20, 23]
সমাধান: কিউ ব্যবহার। রুট কিউতে পুশ। কিউ খালি না হওয়া পর্যন্ত: ফ্রন্ট আইটেম পপ করে প্রিন্ট, লেফট ও রাইট চাইল্ড থাকলে কিউতে পুশ।
উদাহরণ (C++)
#include<iostream>
#include<queue>
using namespace std;
class node{
public:
int h_left, h_right, bf, value;
node *left, *right;
};
class tree{
private:
node *get_node(int key);
public:
node *root;
tree(){
root = NULL;
}
void levelorder_traversal(node *r);
node *insert_node(node *root, int key);
};
node *tree::get_node(int key){
node *new_node = new node;
new_node->h_left = 0; new_node->h_right = 0;
new_node->bf = 0;
new_node->value = key;
new_node->left = NULL; new_node->right = NULL;
return new_node;
}
void tree::levelorder_traversal(node *root){
queue <node*> que;
node *item;
que.push(root);
while(!que.empty()){
item = que.front();
cout << item->value << " ";
if(item->left != NULL) que.push(item->left);
if(item->right != NULL) que.push(item->right);
que.pop();
}
}
node *tree::insert_node(node *root, int key){
if(root == NULL) return (get_node(key));
if(key < root->value) root->left = insert_node(root->left, key);
else if(key > root->value) root->right = insert_node(root->right, key);
return root;
}
main(){
node *root;
tree my_tree;
my_tree.root = my_tree.insert_node(my_tree.root, 10);
my_tree.root = my_tree.insert_node(my_tree.root, 5);
my_tree.root = my_tree.insert_node(my_tree.root, 16);
my_tree.root = my_tree.insert_node(my_tree.root, 20);
my_tree.root = my_tree.insert_node(my_tree.root, 15);
my_tree.root = my_tree.insert_node(my_tree.root, 8);
my_tree.root = my_tree.insert_node(my_tree.root, 23);
cout << "Level-Order Traversal: ";
my_tree.levelorder_traversal(my_tree.root);
}
ইনপুট
[10,5,16,null,8,15,20,null,null,null,null,null,null,null,23]
আউটপুট
Level-Order Traversal: 10 5 16 8 15 20 23
