ในบทช่วยสอนนี้ เราจะพูดถึงโปรแกรมที่จะพิมพ์พาธจากโหนดรูทของไบนารีทรีไปยังโหนดอื่นๆ ทั้งหมดที่มีอยู่ในไบนารีทรีที่กำหนด
ในโปรแกรมนี้ เราจะได้รับหมายเลข N ซึ่งแสดงถึงจำนวนองค์ประกอบที่มีอยู่ในไบนารีทรีตั้งแต่ 1 ถึง N 1 เป็นโหนดรูทของไบนารีทรี ดังนั้น งานของเราคือพิมพ์เส้นทางที่เป็นไปได้ทั้งหมดจากโหนดรูทไปยังองค์ประกอบอื่นๆ ที่มีอยู่ในไบนารีทรี
เพื่อแก้ปัญหานี้ เรารู้ว่าสำหรับโหนด I ลูกด้านซ้ายสามารถคำนวณได้เป็น 2*i และลูกด้านขวาสามารถคำนวณได้เป็น 2*i+1 จากนั้นเราสามารถใช้การย้อนรอยเพื่อเก็บเส้นทางขององค์ประกอบนั้นในเวกเตอร์ แล้วพิมพ์เส้นทางที่เป็นไปได้ทั้งหมดในขั้นตอนสุดท้าย
ตัวอย่าง
#include <iostream>
#include <vector>
using namespace std;
//calculating all the possible paths from the root node
void calc_allpath(vector<int> paths, int nth_node, int kth_node){
if (kth_node > nth_node)
return;
paths.push_back(kth_node);
for (int i = 0; i < paths.size(); i++)
cout << paths[i] << " ";
cout << endl;
calc_allpath(paths, nth_node, kth_node * 2);
calc_allpath(paths, nth_node, kth_node * 2 + 1);
}
//printing all the possible paths from the root node
void print_allpath(int nth_node){
vector<int> paths;
calc_allpath(paths, nth_node, 1);
}
int main(){
int nth_node = 9;
print_allpath(nth_node);
return 0;
} ผลลัพธ์
1 1 2 1 2 4 1 2 4 8 1 2 4 9 1 2 5 1 3 1 3 6 1 3 7
