c - 递归和遍历二叉树
问题描述
我有以下树结构:
这显示了 3 个级别。我的实际问题将有 8 到 12 个级别。我有以下程序,我相信它会以正确的顺序遍历树。两个子节点向一个父节点报告。如果我们知道两个孩子,我们可以找到父母。本质上,我们想要从右到左,从下到上遍历树。数字表示需要遍历节点的顺序。
这是我相信可以实现此目的的代码:
#include <stdio.h>
int main(void)
{
for (int i = 0; i < 2; i++)
{
for (int j = 0; j < 2; j++)
{
for (int k = 0; k < 2; k++)
{
printf("k loop: %d ", i * 7 + j * 3 + k);
}
printf("\n");
printf("j loop: %d \n", i * 7 + j * 3 + 2);
}
printf("i loop: %d \n", i * 7 + 6);
}
printf("final node: %d\n", 2 * 2 * 2 * 2 - 2);
}
这不是很漂亮,也不是很可扩展,因为我需要为每个附加级别添加另一个 for 循环。
三个问题:
- 我将如何使用递归来做到这一点?
- 有没有更可扩展的方式来做到这一点而无需递归?
- for 循环方法或递归方法会更快
解决方案
您可以通过以下步骤递归地执行此操作p(n, level)
:
- 如果
level > 0
,首先打印子树- 调用
n = p(n, level - 1)
左子树 - 调用
n = p(n, level - 1)
右子树
- 调用
- 然后打印
n
并返回n+1
这是一个幼稚的实现:
#include <stdio.h>
int p(int n, int level) {
if (level > 0) {
n = p(n, level - 1);
n = p(n, level - 1);
}
printf("%i\n", n);
return n + 1;
}
// initial call for a depth of 8:
int main() {
p(0, 8);
return 0;
}
推荐阅读
- terraform - 将公共 IP 输出与服务器名称连接起来
- reactjs - 在 jsx 中使用 react 渲染嵌套对象
- waf - Waf 任务应该使用变体目录
- javascript - 为什么我的 React 路由器只加载默认路由?
- tensorflow - Tensorflow GPU 无法识别我的 GPU
- java - Hibernate Select distinct with order by another table
- javascript - 减少与过滤和映射
- intellij-idea - intellij 理念中的新 Kotlin 类
- facebook - 授权码未通过移动应用程序交换为令牌 facebook
- pip - 如何在我的 Mac 上修复与 127.0.0.1 的 pip 连接?