如何在不使用指針或引用的情況下迭代二叉樹？

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-基於指數。根據計算的指標，您可以模擬節點的值。