In các đường đi gốc-đến-lá không dùng đệ quy trong C++

Cho cây nhị phân, chương trình tìm tất cả đường đi từ gốc đến lá nhưng không dùng đệ quy.

Ta duyệt cây lặp (iterative) do ràng buộc không dùng đệ quy. Dùng STL map lưu gốc, khi tìm thấy nút lá qua duyệt theo cấp độ, in đường đi từ gốc đến lá nhờ con trỏ map trỏ đến nút gốc.

Các đường đi từ gốc đến lá:

10 → 3 → 140 
10 → 3 → 162 
10 → 211 → 100 
10 → 211 → 146

Chương trình in tất cả các đường đi này.

Thuật toán

BẮT ĐẦU
BƯỚC 1: CẤU TRÚC NÚT: struct Node { Node *left, *right; int data; }
BƯỚC 2: HÀM TẠO NÚT newnode(int data)
BƯỚC 3: HÀM TÍNH ĐƯỜNG ĐI calculatePath(Node* curr, map<Node*, Node*> first)
    TẠO stack<Node*> stk
    WHILE (curr) { stk.push(curr); curr = first[curr]; }
    WHILE !stk.empty() { curr = stk.top(); stk.pop(); IN curr->data; }
BƯỚC 4: HÀM TÌM NÚT LÁ leaf(Node* root)
    NẾU root == NULL TRẢ VỀ
    TẠO stack<Node*> stc, stc.push(root)
    TẠO map<Node*, Node*> prnt, prnt[root] = NULL
    WHILE !stc.empty()
        curr = stc.top(); stc.pop()
        NẾU !(curr->left) && !(curr->right) GỌI calculatePath(curr, prnt)
        NẾU curr->right { prnt[curr->right] = curr; stc.push(curr->right); }
        NẾU curr->left { prnt[curr->left] = curr; stc.push(curr->left); }
KẾT THÚC

Ví dụ mã C++

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

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

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

void calculatePath(Node* curr, map<Node*, Node*> first) { 
    stack<Node*> stk; 
    while (curr) { 
        stk.push(curr); 
        curr = first[curr]; 
    } 
    while (!stk.empty()) { 
        curr = stk.top(); 
        stk.pop(); 
        cout << curr->data << " "; 
    } 
    cout << endl; 
} 

void leaf(Node* root) { 
    if (root == NULL) return; 
    stack<Node*> stc; 
    stc.push(root); 
    map<Node*, Node*> prnt; 
    prnt[root] = NULL; 
    while (!stc.empty()) { 
        Node* curr = stc.top(); 
        stc.pop(); 
        if (!(curr->left) && !(curr->right)) 
            calculatePath(curr, prnt); 
        if (curr->right) { 
            prnt[curr->right] = curr; 
            stc.push(curr->right); 
        } 
        if (curr->left) { 
            prnt[curr->left] = curr; 
            stc.push(curr->left); 
        } 
    } 
} 

int main() { 
    Node* root = newNode(67); 
    root->left = newNode(34); 
    root->right = newNode(89); 
    root->left->left = newNode(23); 
    root->left->right = newNode(95); 
    root->right->left = newNode(12); 
    leaf(root); 
    return 0; 
}

Kết quả

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

67 34 23 
67 34 95 
67 89 12