พิมพ์โหนดใบ (Leaf Nodes) ใน Binary Tree จากซ้ายไปขวา ใช้ Stack เดียวใน C++

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

ผ่านฟังก์ชัน push() แทรกโหนดของ Binary Tree และผ่าน pop() แสดงโหนดใบ

โหนดใบ (Leaf nodes) คือโหนดปลายที่ left และ right pointer เป็น NULL หมายถึงโหนดนั้นไม่ใช่โหนดผู้ปกครอง (parent node)

ตัวอย่าง

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

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

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

อัลกอริทึม

START
ขั้นตอนที่ 1: สร้างตัวแปรโหนดแบบโครงสร้าง
    ประกาศ int data
    ประกาศ pointer แบบ node ด้วย *left, *right
ขั้นตอนที่ 2: ฟังก์ชันแทรกโหนด พารามิเตอร์ val
    ประกาศตัวแปร node ด้วย malloc
    ตั้ง node->data = val
    ตั้ง node->left = node->right = NULL
    return node
ขั้นตอนที่ 3: ฟังก์ชัน void leaf(Node *ptr)
    สร้าง vector stack<Node*> stck
    Loop While 1
        ถ้า ptr
            stck.push(ptr)
            ptr = ptr->left
        มิฉะนั้น
            ถ้า stck.empty() break
            มิฉะนั้น
                ถ้า stck.top()->right == NULL
                    ptr = stck.top()
                    stck.pop()
                    ถ้า ptr->left == NULL พิมพ์ ptr->data
                Loop While ptr == stck.top()->right
                    ptr = stck.top()
                    stck.pop()
                    ถ้า stck.empty() break
                ถ้า !stck.empty() ptr = stck.top()->right
                มิฉะนั้น ptr = NULL
            จบถ้า
        จบถ้า
    จบลูป
ขั้นตอนที่ 4: ใน main()
    เรียก New ส่งค่าที่ต้องการแทรก Node* root = New(12)
    เรียก leaf(root)
STOP

ตัวอย่างโค้ด

#include <bits/stdc++.h>
using namespace std;

struct Node {
    Node* left;
    Node* right;
    int data;
};

Node* New(int val) {
    Node* node = new Node();
    node->left = node->right = NULL;
    node->data = val;
    return node;
}

void leaf(Node* ptr) {
    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();
                    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