C++에서 정렬된 순서로 이진 트리 수준 인쇄

이 문제에서는 이진 트리가 주어지고 모든 노드를 값의 정렬된 순서로 한 수준에서 인쇄해야 합니다.

개념을 더 잘 이해할 수 있도록 예를 들어 보겠습니다.

입력 -

출력 -

20
6 15
2 17 32 78

이 문제를 해결하려면 트리의 각 수준에 대한 정렬된 순서를 인쇄해야 합니다. 이를 위해 대기열과 두 개의 우선순위 대기열을 생성해야 합니다. NULL 구분 기호는 두 수준을 구분하는 데 사용됩니다.

예

논리를 설명하는 프로그램 -

#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;
}

출력

Elements at each Level of binary tree are
12
34 98
5 12 45 76