Trong bài toán này, chúng ta được đưa ra một cây nhị phân và chúng ta phải in tất cả các nút ở một mức theo thứ tự sắp xếp của các giá trị của chúng.
Hãy lấy một ví dụ để hiểu rõ hơn về khái niệm này,
Đầu vào -
Đầu ra -
20 6 15 2 17 32 78
Để giải quyết vấn đề này, chúng ta cần in một thứ tự đã sắp xếp của từng cấp độ của cây. Đối với điều này, chúng ta cần tạo một hàng đợi và hai hàng đợi ưu tiên. Dấu phân tách NULL được sử dụng để phân tách hai cấp độ.
Ví dụ
Chương trình minh họa logic -
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
struct Node {
int data;
struct Node *left, *right;
};
void printLevelElements(Node* root){
if (root == NULL)
return;
queue<Node*> q;
priority_queue<int, vector<int>, greater<int> > current_level;
priority_queue<int, vector<int>, greater<int> > next_level;
q.push(root);
q.push(NULL);
current_level.push(root->data);
while (q.empty() == false) {
int data = current_level.top();
Node* node = q.front();
if (node == NULL) {
q.pop();
if (q.empty())
break;
q.push(NULL);
cout << "\n";
current_level.swap(next_level);
continue;
}
cout << data << " ";
q.pop();
current_level.pop();
if (node->left != NULL) {
q.push(node->left);
next_level.push(node->left->data);
}
if (node->right != NULL) {
q.push(node->right);
next_level.push(node->right->data);
}
}
}
Node* insertNode(int data){
Node* temp = new Node;
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
int main(){
Node* root = insertNode(12);
root->left = insertNode(98);
root->right = insertNode(34);
root->left->left = insertNode(76);
root->left->right = insertNode(5);
root->right->left = insertNode(12);
root->right->right = insertNode(45);
cout << "Elements at each Level of binary tree are \n";
printLevelElements(root);
return 0;
} Đầu ra
Elements at each Level of binary tree are 12 34 98 5 12 45 76