Chương trình C++ in đường đi gốc đến lá không dùng đệ quy

In đường đi từ gốc đến tất cả các nút lá trong cây nhị phân không dùng đệ quy. Ví dụ cây có 4 lá → 4 đường đi.

Dùng phương pháp lặp: duyệt preorder với stack, lưu con trỏ cha trong map. Khi gặp lá, dùng con trỏ cha in đường đi ngược về gốc.

Ví dụ mã nguồn

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

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

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

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

void preorder_traversal(Node* root) {
    if (root == NULL)
        return;
    stack<Node*> nodeStack;
    nodeStack.push(root);
    map<Node*, Node*> parent;
    parent[root] = NULL;
    while (!nodeStack.empty()) {
        Node* current = nodeStack.top();
        nodeStack.pop();
        if (!(current->left) && !(current->right))
            print_cpath(current, parent);
        if (current->right) {
            parent[current->right] = current;
            nodeStack.push(current->right);
        }
        if (current->left) {
            parent[current->left] = current;
            nodeStack.push(current->left);
        }
    }
}

int main() {
    Node* root = create_node(101);
    root->left = create_node(82);
    root->right = create_node(23);
    root->left->left = create_node(34);
    root->left->right = create_node(55);
    root->right->left = create_node(29);
    preorder_traversal(root);
    return 0;
}

Kết quả đầu ra

101 82 34
101 82 55
101 23 29