程序使用C ++打印从根到完整二叉树中所有节点的路径

Z时代
2024-01-10
分类：综合

在本教程中，我们将讨论一个程序，以打印从二叉树的根节点到给定二叉树中存在的所有其他节点的路径。

在此程序中，我们将得到一个数字N，表示存在于二叉树中的元素数从1到N；1是二叉树的根节点。因此，我们的任务是打印从根节点到二叉树中存在的各种其他元素的所有可能路径。

为了解决该程序，我们知道对于给定的节点I，其左子节点可以计算为2 * i，其右子节点可以计算为2 * i + 1。然后，我们可以使用回溯将特定元素的路径存储在矢量中，然后最终打印所有可能的路径。

示例

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