C++를 사용하여 완전한 이진 트리의 루트에서 모든 노드까지의 경로를 인쇄하는 프로그램

<시간/>

이 튜토리얼에서는 이진 트리의 루트 노드에서 주어진 이진 트리에 있는 다른 모든 노드까지의 경로를 인쇄하는 프로그램에 대해 논의할 것입니다.

이 프로그램에서 1에서 N까지 이진 트리에 있는 요소의 수를 나타내는 숫자 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;
}

출력