递归和遍历二叉树

Question

我有以下树结构：

这个显示了 3 个级别。我的实际问题将有 8 到 12 个级别。我有以下程序，我相信它会以正确的顺序遍历树。两个 children 节点向 parent 节点报告。如果我们都知道 children，我们就可以找到 parent。本质上我们想从右到左，从下到上遍历树。数字表示需要遍历节点的顺序。

这是我相信可以完成此任务的代码：

#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 循环方法或递归方法哪个更快

Answer 1

您可以通过以下步骤递归执行此操作 p(n, level)：

如果level > 0，首先打印子树
- 为左子树调用n = p(n, level - 1)
- 为右子树调用n = p(n, level - 1)
然后打印 n 和 return 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

您要查找的内容称为 In-Order 遍历。它通常与树中的级别数无关，因为它是 Depth-First Traversal.

一般遵循以下算法

递归遍历左子树
访问根节点
递归遍历右子树

Here is a link for more information

完全可以并通常推荐使用遍历树的迭代方法。虽然对于小树来说它的影响并没有真正感受到，但是对于大的递归遍历占用指数数量的内存space。 Here is an example of in-order traversal using a stack on geekforgeeks

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

递归和遍历二叉树

recursion and traversing a binomial tree

c

recursion

binomial-heap