ZigZag Tree Traversal 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 cây nhị phân ở dạng ngoằn ngoèo.

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

Đường chạy ngoằn ngoèo của cây nhị phân ở trên là

3    5    1    8    7    0    4

Để giải quyết vấn đề này, chúng ta cần duyệt cây nhị phân theo cấp độ. Thứ tự chuyển tải sẽ được lật sau mỗi cấp độ.

Bây giờ, chúng ta sẽ sử dụng hai ngăn xếp (hiện tại và tiếp theo) và một giá trị cho thứ tự. Đầu tiên, chúng ta sẽ duyệt qua nút từ các nút hiện tại và nguồn cấp dữ liệu từ nút con bên trái sang nút con bên phải để thứ tự ngược lại sẽ được trả về. Một lần nữa đảo ngược so với hiện tại. Biến thứ tự đóng một vai trò quan trọng trong việc hiển thị mặt nào sẽ được in.

Ví dụ

Chương trình cho thấy việc triển khai giải pháp của chúng tôi,

#include <iostream>
#include <stack>
using namespace std;
struct Node {
   int data;
   struct Node *left, *right;
};
void zigZagTreeTraversal(struct Node* root){
   if (!root)
      return;
   stack<struct Node*> currentlevel;
   stack<struct Node*> nextlevel;
   currentlevel.push(root);
   bool LtR = true;
   while (!currentlevel.empty()) {
      struct Node* temp = currentlevel.top();
      currentlevel.pop();
      if (temp) {
         cout<<temp->data<<"\t";
         if (LtR) {
            if (temp->left)
               nextlevel.push(temp->left);
            if (temp->right)
               nextlevel.push(temp->right);
         }
         else {
            if (temp->right)
               nextlevel.push(temp->right);
            if (temp->left)
               nextlevel.push(temp->left);
         }
      }
      if (currentlevel.empty()) {
         LtR = !LtR;
         swap(currentlevel, nextlevel);
      }
   }
}
struct Node* insertNode(int data){
   struct Node* node = new struct Node;
   node->data = data;
   node->left = node->right = NULL;
   return (node);
}
int main() {
   struct Node* root = insertNode(3);
   root->left = insertNode(1);
   root->right = insertNode(5);
   root->left->left = insertNode(8);
   root->left->right = insertNode(7);
   root->right->left = insertNode(0);
   root->right->right = insertNode(4);
   cout << "ZigZag traversal of the given binary tree is \n";
   zigZagTreeTraversal(root);
   return 0;
}

Đầu ra

ZigZag traversal of the given binary tree is
3    5    1    8    7    0    4