โปรแกรม C++ พิมพ์เส้นทางรากไปใบทุกเส้นทางโดยไม่ใช้ Recursion

ในบทช่วยสอนนี้ เราจะพูดถึงโปรแกรมพิมพ์เส้นทางจากโหนดรากไปยังโหนดใบทั้งหมดในต้นไม้ไบนารีที่กำหนด

ตัวอย่าง สมมติเรามีต้นไม้ไบนารีดังนี้

ในต้นไม้ไบนารีนี้ มีโหนดใบ 4 โหนด ดังนั้นเราสามารถมีเส้นทาง 4 เส้นทางจากโหนดรากไปโหนดใบ

เพื่อแก้ปัญหานี้ เราจะใช้วิธีแบบทำซ้ำ (iterative) ขณะทำ preorder traversal ของต้นไม้ไบนารี เราสามารถเก็บพอยน์เตอร์พาเรนต์ใน map ได้ เมื่อเจอโหนดใบระหว่างการท่อง เราสามารถพิมพ์เส้นทางจากรากได้ง่ายๆ โดยใช้พาเรนต์พอยน์เตอร์

ตัวอย่าง

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

// ทำ preorder traversal
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; 
}

ผลลัพธ์

101 82 34 
101 82 55 
101 23 29