Zig Zag Mức độ duyệt qua của một cây bằng cách sử dụng một hàng đợi trong C ++

Trong bài toán này, chúng ta được đưa ra một cây nhị phân. Nhiệm vụ của chúng ta là in đường đi ngang theo thứ tự ngoằn ngoèo của cây. Đối với truyền tải này, chúng tôi sẽ chỉ sử dụng một hàng đợi duy nhất.

Hãy lấy một ví dụ để hiểu vấn đề,

Đầu ra -

3    1    7    2    8    9    5

Để giải quyết vấn đề này bằng cách sử dụng một hàng đợi, chúng tôi sẽ kiện thêm một cờ phân tách cùng với cờ hàng đợi và cờ hướng.

Bây giờ, chúng ta sẽ duyệt qua cấp độ cây theo cấp độ, chèn phần tử gốc, bây giờ chèn cho mọi phần tử của hàng đợi, hãy chèn nút con của nó vào hàng đợi. Nếu gặp phải NULL, chúng ta sẽ kiểm tra hướng và sau đó đi ngang các phần tử theo hướng đã cho. Sau đó, chúng tôi sẽ tiếp tục chèn cho đến khi chúng tôi truy cập NULL cuối cùng.

Ví dụ

Chương trình minh họa giải pháp của chúng tôi,

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

Đầu ra

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