In nút lá của cây nhị phân từ trái sang phải dùng một stack (C++)

Chương trình in các nút lá của cây nhị phân từ trái sang phải nhưng chỉ dùng một stack.

Dùng push() chèn nút, pop() lấy nút lá ra hiển thị.

Nút lá là nút cuối có con trỏ left và right là NULL (không phải nút cha).

Ví dụ

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

Stack là cấu trúc LIFO, con trỏ top trỏ đến phần tử chèn cuối. Nút lá được chèn cuối vào stack và sẽ được pop ra trước các nút khác.

Thuật toán

BẮT ĐẦU
BƯỚC 1: CẤU TRÚC NÚT: data, *left, *right
BƯỚC 2: HÀM TẠO NÚT New(val) TRẢ VỀ node*
BƯỚC 3: HÀM void leaf(Node *ptr)
    TẠO stack<Node*> stck
    WHILE 1
        NẾU ptr: stck.push(ptr); ptr = ptr->left
        NGƯỢC LẠI
            NẾU stck.empty() BREAK
            NGƯỢC LẠI
                NẾU stck.top()->right == NULL
                    ptr = stck.top(); stck.pop()
                    NẾU ptr->left == NULL IN ptr->data
                WHILE ptr == stck.top()->right
                    ptr = stck.top(); stck.pop()
                    NẾU stck.empty() BREAK
                NẾU !stck.empty() ptr = stck.top()->right
                NGƯỢC LẠI ptr = NULL
BƯỚC 4: TRONG main(): TẠO CÂY, GỌI leaf(root)
KẾT THÚC

Ví dụ mã C++

#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("Các nút lá ở cấp cuối: "); 
    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; 
}

Kết quả

Chạy chương trình cho kết quả:

Các nút lá ở cấp cuối: 41 59 33 70