Chương trình C++ in đường đi từ gốc đến tất cả nút trong cây nhị phân hoàn chỉnh

In đường đi từ gốc đến tất cả nút khác trong cây nhị phân hoàn chỉnh. Cho N số phần tử 1..N, 1 là gốc. In tất cả đường đi từ gốc đến các nút.

Với nút i, con trái = 2*i, con phải = 2*i+1. Dùng backtracking lưu đường đi trong vector và in ra.

Ví dụ mã nguồn

#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;
}

Kết quả đầu ra

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