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

出力

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