โปรแกรม C++ พิมพ์เส้นทางจากรากไปโหนดที่กำหนดในต้นไม้ไบนารี

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

สำหรับต้นไม้ไบนารีที่มีโหนดต่างกัน เราต้องพิมพ์เส้นทางเต็มเพื่อไปถึงโหนดที่กำหนดจากโหนดรากของต้นไม้ไบนารี

เพื่อแก้ปัญหานี้ เราจะใช้การเรียกซ้ำ (recursion) ขณะท่องต้นไม้ไบนารี เราจะค้นหาแบบเรียกซ้ำเพื่อหาสมาชิกที่ต้องการ พร้อมกับเก็บเส้นทางเพื่อไปถึงสมาชิกที่ค้นหา

ตัวอย่าง

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

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

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

// ตรวจสอบว่าเส้นทางจากรากไปสมาชิกมีอยู่หรือไม่
bool is_path(Node *root, vector<int>& arr, int x){ 
    if (!root) 
        return false; 
    arr.push_back(root->data); 
    if (root->data == x) 
        return true; 
    if (is_path(root->left, arr, x) || is_path(root->right, arr, x)) 
        return true; 
    arr.pop_back(); 
    return false; 
} 

// พิมพ์เส้นทางจากโหนดรากไปสมาชิก
void print_path(Node *root, int x){ 
    vector<int> arr; 
    if (is_path(root, arr, x)){ 
        for (int i = 0; i < arr.size() - 1; i++) 
            cout << arr[i] << " -> "; 
        cout << arr[arr.size() - 1]; 
    } else 
        cout << "Path doesn't exists" << endl; 
} 

int main(){ 
    struct Node *root = create_node(13); 
    root->left = create_node(21); 
    root->right = create_node(43); 
    root->left->left = create_node(34); 
    root->left->right = create_node(55); 
    root->right->left = create_node(68); 
    root->right->right = create_node(79); 
    int x = 68; 
    print_path(root, x); 
    return 0; 
}

ผลลัพธ์

13 -> 43 -> 68