พิมพ์เส้นทาง Root-to-Leaf ทั้งหมดใน Binary Tree โดยไม่ใช้ Recursion ใน C++

กำหนด Binary Tree โปรแกรมต้องหาเส้นทางหลายเส้นทางจากรากไปยังใบ (root-to-leaf) หมายถึงพิมพ์เส้นทางทั้งหมด แต่ข้อท้าทายคือต้องทำโดยไม่ใช้ Recursion

เราจะท่องต้นไม้แบบ Iterative เนื่องจากข้อจำกัดคือห้ามใช้ Recursion เพื่อให้บรรลุเป้าหมายนี้ เราสามารถใช้ STL map ที่จะจัดเก็บโหนดราก (root element) และเมื่อพบโหนดใบผ่าน Level Order Traversal จะพิมพ์เส้นทางจากรากไปใบ เนื่องจากมี map pointer ที่ชี้ไปยังโหนดราก

ในต้นไม้ข้างต้น มีเส้นทางหลายเส้นทางจากรากไปใบ:

10 -> 3 -> 140
10 -> 3 -> 162
10 -> 211 -> 100
10 -> 211 -> 146

ดังนั้น โปรแกรมต้องพิมพ์เส้นทางทั้งหมดที่กำหนดไว้เป็นผลลัพธ์ของ Binary Tree ที่ให้มา

อัลกอริทึม

START
ขั้นตอนที่ 1: สร้างโครงสร้างโหนด struct Node { Node *left, *right; int data; }
ขั้นตอนที่ 2: ฟังก์ชันสร้างโหนด newnode(int data)
ขั้นตอนที่ 3: ฟังก์ชันคำนวณเส้นทาง calculatePath(Node* curr, map<Node*, Node*> first)
    สร้าง stack<Node*> stk
    Loop While (curr)
        stk.push(curr)
        curr = first[curr]
    End
    Loop While !stk.empty()
        curr = stk.top()
        stk.pop()
        พิมพ์ curr->data
    End
ขั้นตอนที่ 4: ฟังก์ชันหาโหนดใบ leaf(Node* root)
    ถ้า root = NULL Return
    สร้าง stack<Node*> stc, stc.push(root)
    สร้าง map<Node*, Node*> prnt, prnt[root] = NULL
    Loop while !stc.empty()
        Node* curr = stc.top(), stc.pop()
        ถ้า !(curr->left) && !(curr->right)
            calculatePath(curr, prnt)
        ถ้า curr->right
            prnt[curr->right] = curr, stc.push(curr->right)
        ถ้า curr->left
            prnt[curr->left] = curr, stc.push(curr->left)
    End
STOP

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

#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;
}

ผลลัพธ์

67 34 23
67 34 95
67 89 12