In các nút lá trong cây nhị phân từ trái sang phải bằng một ngăn xếp trong C ++

Chương trình nên in các nút lá của cây nhị phân từ trái sang phải nhưng thách thức liên quan đến việc chỉ sử dụng một ngăn xếp

Thông qua hàm push (), các nút chèn của cây nhị phân và thông qua thao tác pop () hiển thị các nút lá.

Các nút lá là các nút kết thúc có con trỏ trái và phải là NULL, có nghĩa là nút cụ thể đó không phải là nút cha.

Ví dụ

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

Ngăn xếp là một cấu trúc dữ liệu là một cấu trúc LIFO trong đó con trỏ trên cùng sẽ trỏ đến các phần tử cuối cùng được chèn vì vậy các nút lá sẽ được chèn vào cuối cùng vào ngăn xếp và chúng sẽ được bật ra hoặc loại bỏ khỏi ngăn xếp trước bất kỳ nút nào khác như mỗi cấu trúc ngăn xếp.

Đoạn mã dưới đây cho thấy việc triển khai C ++ bằng cách sử dụng STL của thuật toán đã cho.

Thuật toán

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

Ví dụ

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

Đầu ra

Nếu chúng ta chạy chương trình trên thì nó sẽ tạo ra kết quả sau.

leaf nodes at end level are : 41 59 33 70