如何在不使用指针或引用的情况下迭代二叉树？

Question

可以在不使用指针或引用的情况下遍历列表。 在某些情况下，这消除了实际拥有该列表的需要。 考虑下面的代码，

int i; 
for (i = 0; i < 10; ++i) 
printf("%i ", i % 2); 

它直接输出该列表0 1 0 1 0 1 0 1 0 1，而无需实际存储在存储器中的列表中。

怎么能用二叉树做类似的事情？

请在下面的代码中显示一个实现tree_iterator，new_root_tree_iterator和traverse_tree_iterator的方法，其中up​​per_boundary_of_tree类似于列表示例中的数字10，并且我不知道如何定义。

人们遇到了我所说的upper_boundary_of_tree的问题。树的上边界不会用数字10表示。我不知道如何表示树的某个上边界。这是问题的一部分。树的上边界类似于上面列表代码中使用数字10的方式，因为它在相同的函数中标记了停止迭代的位置，但这绝对不是一回事。

如果你需要，你也可以有一个free_tree_iterator函数。

tree_iterator i = new_root_tree_iterator(); 
while (traverse_tree_iterator(&i, upper_boundary_of_tree)) 
foobar(i); 

这一直困扰着我一段时间。

Answer 1

要打印树结构的符号而不构建树，类似于打印序列而不是构建列表的方式，首先必须确定符号的外观。

你能写下一个例子吗？

例如，一个类似Lisp的符号？

（（1 2）（3 4））;;这是一棵树

此外，给定10的上限，这意味着将有十个编号的叶节点，你应该打印哪些二叉树？

直列表是一个简并二叉树，所以实际上你简单的for循环基本上满足了作业问题。

Answer 2

您无法遍历不存在的数据。第一个例子中显示的是一个循环，打印0或1次10次。遍历数组（或任何其他数据结构）的想法是以某种方式处理每个元素，例如计算数组元素的总和。

换句话说，第一个例子是模拟迭代10个元素的数组，它们是零和一个，一个接一个。所以，在每次迭代中，您都会根据其索引预测值。

如果要计算二叉树中子节点的索引，可以使用heap分配公式：2n + 1和2n + 2分别计算左右节点的索引，其中n为0-基于指数。根据计算的指标，您可以模拟节点的值。