数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究使用 C++ 打印完全二叉树中从根节点到所有节点的路径的程序
在本教程中，我们将讨论一个程序，该程序用于打印从二叉树的根节点到给定二叉树中所有其他节点的路径。
在这个程序中，我们将得到一个数字 N，表示二叉树中存在的元素数量从 1 到 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
更新于: 2019年11月1日
153 次查看
广告