C++에서 하나의 스택을 사용하여 왼쪽에서 오른쪽으로 이진 트리의 리프 노드 인쇄

프로그램은 이진 트리의 리프 노드를 왼쪽에서 오른쪽으로 인쇄해야 하지만 문제는 하나의 스택만 사용하는 것입니다.

push() 함수를 통해 이진 트리의 노드를 삽입하고 pop() 작업을 통해 잎 노드를 표시합니다.

리프 노드는 왼쪽 및 오른쪽 포인터가 NULL인 끝 노드로 특정 노드가 부모 노드가 아님을 의미합니다.

예시

Input : 12 21 32 41 59 33 70
Output : 41 59 33 70

스택은 LIFO 구조인 데이터 구조로, 상단 포인터가 삽입된 마지막 요소를 가리키므로 리프 노드가 스택의 마지막에 삽입되고 다른 노드보다 먼저 스택에서 튀어 나오거나 제거됩니다. 스택 구조당.

아래 코드는 주어진 알고리즘의 STL을 사용한 C++ 구현을 보여줍니다.

알고리즘

START
   Step 1 -> create node variable of type structure
      Declare int data
      Declare pointer of type node using *left, *right
   Step 2 -> create function for inserting node with parameter as val
      Declare node variable of node using malloc
      Set node->data = val
      Set node->left = node->right = NULL
      return node
   step 3 -> Declare Function void leaf(Node *ptr)
      create vector stack<Node*>stck
      Loop While 1
      IF ptr
         Stck.push(ptr)
         Ptr = ptr->left
      Else
         IF (stck.empty())
            Break
         Else
            IF (stck.top()->right == NULL)
               Set ptr = stck.top()
               Set stck.pop()
               IF ptr->left = NULL
                  Print ptr->data
            End
            Loop While ptr == stck.top()->right
               Set ptr = stck.top()
               Call stck.pop()
               IF stck.empty()
                  Break
               End
               IF !stck.empty()
                  Set ptr = tck.top()->right
               Else
                  Set ptr = NULL
               EndIF
            End
         End
      End
   Step 4-> In main()
      Call New passing value user want to insert as Node* root = New(12)
      Call leaf(root)
STOP

예시

#include <bits/stdc++.h>
using namespace std;
// Structure of a node
struct Node {
   Node* left;
   Node* right;
   int data;
};
//Function to create a new node
Node* New(int val) {
   Node* node = new Node();
   node->left = node->right = NULL;
   node->data = val;
   return node;
}
// leaf node using stack
void leaf(Node* ptr) {
   // stack that will store nodes
   stack<Node*> stck;
   while (1) {
      if (ptr) {
         stck.push(ptr);
         ptr = ptr->left;
      } else {
         if (stck.empty())
            break;
         else {
            if (stck.top()->right == NULL) {
               ptr = stck.top();
               stck.pop();
               // Print the leaf node
               if (ptr->left == NULL)
                  printf("%d ", ptr->data);
            }
            while (ptr == stck.top()->right) {
               ptr = stck.top();
               stck.pop();
               if (stck.empty())
                  break;
            }
            if (!stck.empty())
               ptr = stck.top()->right;
            else
               ptr = NULL;
         }
      }
   }
}
int main() {
   printf("leaf nodes at end level are : ");
   Node* root = New(12);
   root->left = New(21);
   root->right = New(32);
   root->left->left = New(41);
   root->left->right = New(59);
   root->right->left = New(33);
   root->right->right = New(70);
   leaf(root);
   return 0;
}

출력

위의 프로그램을 실행하면 다음과 같은 출력이 생성됩니다.

leaf nodes at end level are : 41 59 33 70