พิมพ์ลีฟโหนดในไบนารีทรีจากซ้ายไปขวาโดยใช้หนึ่งสแต็กใน C++

โปรแกรมควรพิมพ์ leaf nodes ของไบนารีทรีจากซ้ายไปขวา แต่ปัญหาคือการใช้สแต็กเดียวเท่านั้น

ผ่านฟังก์ชัน push() แทรกโหนดของไบนารีทรีและผ่านการดำเนินการป๊อป () จะแสดงโหนดลีฟ

Leaf nodes เป็นโหนดปลายที่มีตัวชี้ซ้ายและขวาเป็น NULL ซึ่งหมายความว่าโหนดนั้นไม่ใช่โหนดหลัก

ตัวอย่าง

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

Stack เป็นโครงสร้างข้อมูลซึ่งเป็นโครงสร้าง LIFO โดยที่ตัวชี้บนจะชี้ไปที่องค์ประกอบสุดท้ายที่แทรกเข้าไป ดังนั้นโหนดปลายสุดจะถูกแทรกเข้าไปในสแต็กสุดท้าย และพวกมันจะโผล่ออกมาหรือนำออกจากสแต็กก่อนโหนดอื่นตาม ต่อโครงสร้างสแต็ก

โค้ดด้านล่างแสดงการใช้งาน C++ โดยใช้ STL ของอัลกอริทึมที่กำหนด

อัลกอริทึม

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