In tổ tiên của nút cây nhị phân không dùng đệ quy C++

Cho cây nhị phân và một nút mục tiêu. In tất cả tổ tiên của nút đó (các nút trên đường từ gốc đến nút) mà không dùng đệ quy. Sử dụng ngăn xếp và duyệt hậu tự (postorder) lặp.

Giải thuật stack

1. Duyệt từ gốc, đẩy các nút vào stack khi đi xuống.
2. Khi tìm thấy nút mục tiêu, dừng lại.
3. In các phần tử trong stack (đây là các tổ tiên từ gần đến xa).

Ví dụ minh họa

#include <stdio.h>
#include <stdlib>

#define MAX 100

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

struct Stack {
    int top;
    Node* arr[MAX];
};

Node* newNode(int d) {
    Node* n = (Node*)malloc(sizeof(Node));
    n->data = d; n->left = n->right = NULL;
    return n;
}

void printAncestors(Node* root, int key) {
    if (!root) return;
    Stack st = {-1};
    
    while (true) {
        while (root && root->data != key) {
            st.arr[++st.top] = root;
            root = root->left;
        }
        if (root && root->data == key) break;
        
        if (st.top >= 0 && st.arr[st.top]->right == NULL) {
            root = st.arr[st.top--];
            while (st.top >= 0 && st.arr[st.top]->right == root)
                root = st.arr[st.top--];
        }
        root = (st.top < 0) ? NULL : st.arr[st.top]->right;
    }
    
    while (st.top >= 0)
        printf("%d ", st.arr[st.top--]->data);
}

int main() {
    Node* root = newNode(15);
    root->left = newNode(10);
    root->right = newNode(25);
    root->left->left = newNode(5);
    root->left->right = newNode(12);
    root->right->left = newNode(20);
    root->right->right = newNode(27);
    root->left->left->left = newNode(1);
    root->left->right->right = newNode(14);
    root->right->right->left = newNode(17);
    
    printf("To tien cua nut 17: ");
    printAncestors(root, 17);
    return 0;
}

Kết quả

To tien cua nut 17: 27 25 15