ポインタや参照を使用せずにバイナリツリーを反復処理する方法はありますか？

Question

ポインタや参照を使わずにリストを反復処理することができます。 場合によっては、実際にリストを持つ必要がなくなります。 が直接、実際にメモリ内にリストを格納することなく、リスト0 1 0 1 0 1 0 1 0 1を出力し、次のコード、

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

を考えます。

バイナリツリーで同様のことを行うにはどうすればよいですか？

次のコードでは、tree_iterator、new_root_tree_iterator、およびtraverse_tree_iteratorを実装する方法を示してください。ここで、upper_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番リーフノードがあるでしょう意味、10の上限を与え、木も

ですか？

ストレートリストが縮退バイナリ木ですので、実際にループのためのあなたのシンプルは、基本的には宿題の問題を満たしています。

Answer 2

存在しないデータを反復処理することはできません。最初の例で示されているのは、0または1の10回の印刷を行うループです。配列（または他のデータ構造）を反復するという考え方は、配列要素の合計を計算するなどの方法で各要素を処理することです。

言い換えれば、最初の例では、別の次の0と1である10個の要素、一つのアレイ上に反復をエミュレートしています。したがって、各反復で、そのインデックスに基づいて値を予測しています。

バイナリツリーの子ノードのインデックスを計算する場合は、の配分式を使用できます.2n + 1と2n + 2は、それぞれ左ノードと右ノードのインデックスを計算します.nは0〜ベースインデックス。計算されたインデックスに基づいて、ノードの値をエミュレートできます。