โปรแกรม C++ พิมพ์เส้นทางจากรากไปทุกโหนดใน Complete Binary Tree

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

ในโปรแกรมนี้ เราจะได้รับตัวเลข N แสดงจำนวนสมาชิกในต้นไม้ไบนารีจาก 1 ถึง N โดย 1 เป็นโหนดรากของต้นไม้ไบนารี ดังนั้นงานของเราคือพิมพ์เส้นทางทั้งหมดที่เป็นไปได้จากโหนดรากไปยังสมาชิกอื่นๆ ในต้นไม้ไบนารี

เพื่อแก้โปรแกรมนี้ เรารู้ว่าสำหรับโหนด i โหนดลูกซ้ายคำนวณได้จาก 2*i และโหนดลูกขวาคำนวณได้จาก 2*i+1 เราสามารถใช้ backtracking เก็บเส้นทางของสมาชิกเฉพาะใน vector แล้วพิมพ์เส้นทางทั้งหมดที่เป็นไปได้

ตัวอย่าง

#include <iostream> 
#include <vector> 
using namespace std; 

// คำนวณเส้นทางทั้งหมดจากโหนดราก
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); 
} 

// พิมพ์เส้นทางทั้งหมดจากโหนดราก
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; 
}

ผลลัพธ์