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

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ừ nút gốc của cây nhị phân đến tất cả các nút khác có trong cây nhị phân đã cho.

Trong chương trình này, chúng ta sẽ được cung cấp một số N, biểu thị số phần tử có mặt trong cây nhị phân từ 1 đến N; 1 là nút gốc của cây nhị phân. Do đó, nhiệm vụ của chúng ta là in tất cả các đường dẫn có thể có từ nút gốc đến các phần tử khác có trong cây nhị phân.

Để giải chương trình này, chúng ta biết rằng đối với nút I đã cho, nút con bên trái của nó có thể được tính là 2 * i và nút con bên phải của nó có thể được tính là 2 * i + 1. Sau đó, chúng tôi có thể sử dụng backtracking để lưu trữ đường dẫn của phần tử cụ thể đó trong một vectơ và sau đó in cuối cùng tất cả các đường dẫn có thể có.

Ví dụ

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

Đầu ra