ในบทช่วยสอนนี้ เราจะพูดถึงโปรแกรมเพื่อพิมพ์เส้นทางรากที่สั้นที่สุดไปยังเส้นทางใบแรกในต้นไม้ไบนารี
ในสิ่งนี้ เราจะได้รับไบนารีทรีที่มีค่าต่างกัน และเราต้องหาเส้นทางที่สั้นที่สุดจากโหนดรูทไปยังโหนดลีฟในทรีไบนารีที่กำหนด
เพื่อแก้ปัญหานี้ เราสามารถใช้คิวเพื่อดำเนินการตามระดับในไบนารีทรีและเก็บโหนดในเส้นทางที่สั้นที่สุด สำหรับสิ่งนี้ เมื่อเราไปถึงโหนดซ้ายสุดสำหรับระดับสุดท้าย เราจะดึงค่าจากคิวและพิมพ์เส้นทางที่สั้นที่สุด
ตัวอย่าง
#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
