พิมพ์บรรพบุรุษของโหนดใน Binary Tree แบบไม่ใช้ Recursion ใน C++

โจทย์

ให้ Binary Tree และโหนดเป้าหมาย ต้องการพิมพ์บรรพบุรุษ (Ancestors) ของโหนดนั้นแบบไม่ใช้ Recursion

Binary Tree คือต้นไม้ที่แต่ละโหนดมีลูกได้สูงสุด 2 โหนด

บรรพบุรุษ คือโหนดที่อยู่ระดับสูงกว่าโหนดเป้าหมาย

วิธีแก้ปัญหา

ใช้การท่อง Postorder แบบ Iterative พร้อม Stack เก็บบรรพบุรุษ ขั้นตอน:

1. สร้าง Stack สำหรับเก็บโหนด
2. ท่องจาก Root ไปยังโหนดเป้าหมาย พุชโหนดที่ผ่านเข้า Stack
3. เมื่อเจอโหนดเป้าหมาย หยุดการท่อง
4. พิมพ์ค่าใน Stack (เป็นบรรพบุรุษจากล่างขึ้นบน)

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

#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100

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

struct Stack {
    int size;
    int top;
    struct Node** array;
};

struct Node* insertNode(int data) {
    struct Node* node = (struct Node*) malloc(sizeof(struct Node));
    node->data = data;
    node->left = node->right = NULL;
    return node;
}

struct Stack* createStack(int size) {
    struct Stack* stack = (struct Stack*) malloc(sizeof(struct Stack));
    stack->size = size;
    stack->top = -1;
    stack->array = (struct Node**) malloc(stack->size * sizeof(struct Node*));
    return stack;
}

int isFull(struct Stack* stack) { return (stack->top + 1) == stack->size; }
int isEmpty(struct Stack* stack) { return stack->top == -1; }

void push(struct Stack* stack, struct Node* node) {
    if (isFull(stack)) return;
    stack->array[++stack->top] = node;
}

struct Node* pop(struct Stack* stack) {
    if (isEmpty(stack)) return NULL;
    return stack->array[stack->top--];
}

struct Node* peek(struct Stack* stack) {
    if (isEmpty(stack)) return NULL;
    return stack->array[stack->top];
}

void AncestorNodes(struct Node *root, int key) {
    if (root == NULL) return;
    struct Stack* stack = createStack(MAX_SIZE);
    while (1) {
        while (root && root->data != key) {
            push(stack, root);
            root = root->left;
        }
        if (root && root->data == key) break;
        if (peek(stack)->right == NULL) {
            root = pop(stack);
            while (!isEmpty(stack) && peek(stack)->right == root)
                root = pop(stack);
        }
        root = isEmpty(stack) ? NULL : peek(stack)->right;
    }
    while (!isEmpty(stack))
        printf("%d ", pop(stack)->data);
}

int main() {
    struct Node* root = insertNode(15);
    root->left = insertNode(10);
    root->right = insertNode(25);
    root->left->left = insertNode(5);
    root->left->right = insertNode(12);
    root->right->left = insertNode(20);
    root->right->right = insertNode(27);
    root->left->left->left = insertNode(1);
    root->left->right->right = insertNode(14);
    root->right->right->left = insertNode(17);
    printf("The ancestors of the given node are: ");
    AncestorNodes(root, 17);
    getchar();
    return 0;
}

ผลลัพธ์

The ancestors of the given node are: 27 25 15