Trong hướng dẫn này, chúng ta sẽ thảo luận về một chương trình in đường dẫn từ gốc đến lá ngắn nhất đầu tiên trong Cây nhị phân.
Trong phần này, chúng ta sẽ được cung cấp một cây nhị phân với các giá trị khác nhau và chúng ta phải tìm đường đi ngắn nhất từ nút gốc đến nút lá trong một cây nhị phân đã cho.
Để giải quyết vấn đề này, chúng ta có thể sử dụng một hàng đợi để thực hiện duyệt thứ tự mức trong cây nhị phân và lưu trữ các nút trong đường đi ngắn nhất. Đối với điều này, khi chúng tôi đến nút ngoài cùng bên trái của cấp cuối cùng, chúng tôi lấy các giá trị từ hàng đợi và in ra đường dẫn ngắn nhất.
Ví dụ
#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;
} Đầu ra
21 35 53