C++의 지그재그 트리 순회

이 문제에서는 이진 트리가 제공됩니다. 우리의 임무는 이진 트리를 지그재그 형태로 인쇄하는 것입니다.

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

위의 이진 트리의 지그재그 순회는

3    5    1    8    7    0    4

이 문제를 해결하려면 이진 트리 수준을 수준별로 탐색해야 합니다. 순회 순서는 각 레벨 후에 반전됩니다.

이제 두 개의 스택(현재 및 다음)과 하나의 값을 주문에 사용합니다. 먼저 현재 노드에서 노드를 탐색하고 왼쪽 자식에서 오른쪽 자식으로 노드를 공급하여 역순이 반환되도록 합니다. 다시 전류에서 역전됩니다. 순서 변수는 인쇄할 면을 표시하는 데 중요한 역할을 합니다.

예

솔루션 구현을 보여주는 프로그램,

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

출력

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