C++에서 단일 큐를 사용하는 트리의 지그재그 레벨 순서 순회

이 문제에서는 이진 트리가 제공됩니다. 우리의 임무는 트리의 지그재그 레벨 순서 순회를 인쇄하는 것입니다. 이 순회에서는 단일 대기열만 사용합니다.

문제를 이해하기 위해 예를 들어보겠습니다.

출력 -

3    1    7    2    8    9    5

단일 대기열을 사용하여 이 문제를 해결하기 위해 대기열 및 방향 플래그와 함께 추가 분리 플래그를 고소합니다.

이제 레벨별로 트리 레벨을 탐색하고 루트 요소를 삽입하고 이제 큐의 모든 요소에 대해 삽입하여 해당 자식 노드를 큐에 삽입합니다. NULL이 발생하면 방향을 확인한 다음 지정된 방향으로 요소를 순회합니다. 그런 다음 마지막 NULL을 방문할 때까지 계속 삽입합니다.

예시

우리 솔루션을 설명하는 프로그램

#include <bits/stdc++.h>
using namespace std;
struct Node {
   int data;
   struct Node *left, *right;
};
struct Node* insertNode(int data) {
   struct Node* node = new struct Node;
   node->data = data;
   node->left = node->right = NULL;
   return (node);
}
void zigZagTraversal(struct Node* root, int n){
   struct Node* queue[2 * n];
   int top = -1;
   int front = 1;
   queue[++top] = NULL;
   queue[++top] = root;
   queue[++top] = NULL;
   int prevFront = 0, count = 1;
   while (1) {
      struct Node* curr = queue[front];
      if (curr == NULL) {
         if (front == top)
            break;
         else {
            if (count % 2 == 0) {
               for (int i = prevFront + 1; i < front; i++)
                  cout<<queue[i]->data<<"\t";
            }
            else {
               for (int i = front - 1; i > prevFront; i--)
                  cout<<queue[i]->data<<"\t";
            }
            prevFront = front;
            count++;
            front++;
            queue[++top] = NULL;
            continue;
         }
      }
      if (curr->left != NULL)
         queue[++top] = curr->left;
      if (curr->right != NULL)
         queue[++top] = curr->right;
      front++;
   }
   if (count % 2 == 0) {
      for (int i = prevFront + 1; i < top; i++)
         cout<<queue[i]->data<<"\t";
   }
   else {
      for (int i = top - 1; i > prevFront; i--)
         cout<<queue[i]->data<<"\t";
   }
}
int main() {
   struct Node* root = insertNode(3);
   root->left = insertNode(1);
   root->right = insertNode(7);
   root->left->left = insertNode(5);
   root->left->right = insertNode(9);
   root->right->left = insertNode(8);
   root->right->right = insertNode(2);
   cout<<"Zig Zag traversal of the tree is :\n";
   zigZagTraversal(root, 7);
   return 0;
}

출력

Zig Zag traversal of the tree is :
3    1    7    2    8    9    5