c - 递归和遍历二叉树

Question

我有以下树结构：

这显示了 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 循环。

三个问题：

1. 我将如何使用递归来做到这一点？
2. 有没有更可扩展的方式来做到这一点而无需递归？
3. for 循环方法或递归方法会更快

Answer 1

您可以通过以下步骤递归地执行此操作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;
}

Answer 2

1. 您要查找的内容称为In-Order Traversal。它通常与树中的级别数无关，因为它是一种深度优先遍历。

一般遵循以下算法

1. 递归遍历左子树
2. 访问根节点
3. 递归遍历右子树

这是获取更多信息的链接

---

2. 使用树遍历的迭代方法是完全可能的，并且通常被推荐。虽然对于小树来说，它的效果并没有真正感受到，但对于大型递归遍历来说，它占用了指数级的内存空间。 这是在geekforgeeks上使用堆栈的按顺序遍历的示例

---

3. 虽然你不会在小树上注意到它，但递归方法总是比迭代慢。