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

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

ในที่นี้ เราจะได้รับต้นไม้ไบนารีที่มีค่าต่างกัน และเราต้องหาเส้นทางที่สั้นที่สุดจากโหนดรากไปโหนดใบในต้นไม้ไบนารีที่กำหนด

เพื่อแก้ปัญหานี้ เราสามารถใช้ queue เพื่อท่องแบบระดับ (level order traversal) ในต้นไม้ไบนารีและเก็บโหนดในเส้นทางที่สั้นที่สุด สำหรับนี้ เมื่อเราไปถึงโหนดซ้ายสุดในระดับสุดท้าย เราดึงค่าจาก queue และพิมพ์เส้นทางที่สั้นที่สุด

ตัวอย่าง

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

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

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

void print_spath(int Data, unordered_map<int, int> parent){ 
    if (parent[Data] == Data) 
        return; 
    print_spath(parent[Data], parent); 
    cout << parent[Data] << " "; 
} 

void leftmost_path(struct Node* root){ 
    queue<struct Node*> q; 
    q.push(root); 
    int LeafData = -1; 
    struct Node* temp = NULL; 
    unordered_map<int, int> parent; 
    parent[root->data] = root->data; 
    while (!q.empty()){ 
        temp = q.front(); 
        q.pop(); 
        if (!temp->left && !temp->right){ 
            LeafData = temp->data; 
            break; 
        } else{ 
            if (temp->left){ 
                q.push(temp->left); 
                parent[temp->left->data] = temp->data; 
            } 
            if (temp->right) { 
                q.push(temp->right); 
                parent[temp->right->data] = temp->data; 
            } 
        } 
    } 
    print_spath(LeafData, parent); 
    cout << LeafData << " "; 
} 

int main(){ 
    struct Node* root = create_node(21); 
    root->left = create_node(24); 
    root->right = create_node(35); 
    root->left->left = create_node(44); 
    root->right->left = create_node(53); 
    root->right->right = create_node(71); 
    root->left->left->left = create_node(110); 
    root->left->left->right = create_node(91); 
    root->right->right->left = create_node(85); 
    leftmost_path(root); 
    return 0; 
}

ผลลัพธ์

21 35 53