再帰呼び出しで求めたい経路を表示させたい！

質問

以前も「すべての経路を求めるには」というような質問をして再帰呼び出しにより無事解決することが出来ました。
しかし、少しわからないところがあります。

例えばaはb1とb2に接続されていてb1とb2はそれぞれc1,c2とc3,c4に接続されているとします。すべての経路は全部で４本ですね。
これを再帰呼び出しの中にprintf文を用いて表示させたところ

a->b1->c1
c2
b2->c3
c4

というような感じで表示されたと思います。これは再帰呼び出しの性質で分岐があった以前の場所へ戻って探索を続けるからだというのは理解できました。しかし、実際は

a->b1->c1
a->b1->c2
a->b2->c3
a->b2->c4

というように表示させたいです。何かこれを記憶するための変数が必要だと思うのですが、それを用いて上のように表示させるほう方法が思いつきません。
さらに、a->b2->c3というように特定の経路だけを選択して表示させたいです。アドバイスよろしくお願いします！

回答No.1

Oh-Orange · ベストアンサー

★アドバイス(回答？)
・『記憶するための変数』が必要だと思う。→考え方は正解です。
・最初にサンプルを紹介します。
・ほぼ、『答え』なので、なぜ？ってのを自分で解読してみて下さい。

/* このファイルで使用する定数 */
#define FLG_NULL 　(0)
#define FLG_LEFT 　(1)
#define FLG_RIGHT　(2)

/* 再帰呼び出しで経路を表示するサンプル */
void MySearch( struct node_t *top, struct node_t *find )　←findが特定経路のポインタ
{
　static char history[ 7 + 1 ];　←記憶するための変数
　static char *depth = history;　←記憶する現在の位置

　if ( top != NULL ){
　　if ( top->left != NULL ){
　　　*depth++ = FLG_LEFT;
　　　MySearch( top->left, find );
　　　*(--depth) = FLG_NULL;
　　}
　　if ( top->right != NULL ){
　　　*depth++ = FLG_RIGHT;
　　　MySearch( top->right, find );
　　　*(--depth) = FLG_NULL;
　　}
　　if ( (top->left == NULL) || (top->right == NULL) ){
　　　if ( (find == top) || (find == NULL) ){　←特定の経路だけ表示、find=NULL なら全て表示
　　　　int no;

　　　　printf( "a" );

　　　　for ( no = 0 ; history[no] != FLG_NULL ; no++ ){
　　　　　printf( "->%c%d", ('b' + no), history[no] );
　　　　}
　　　　printf( "\n" );
　　　}
　　}
　}
}

●図式例
a->b1[L]->c1[L] → a->b1->c1
a->b1[L]->c2[R] → a->b1->c2
a->b2[R]->c3[L] → a->b2->c1　←※
a->b2[R]->c4[R] → a->b2->c2　←※

最後に:
・上記のサンプルでは『※』印が、『c3』『c4』になりません。少しだけ工夫が必要です。
・工夫のヒントとして、カウンタ変数を static で用意して、単純に出力した順番に通し
　番号を表示させれば良い。→質問者さんには、ここを宿題にします。
・解説はワザとしません。解読して理解してみて下さい。
・以上。おわり。

お礼

回答ありがとうございます！！
自分には知識と理解が足りないせいか少し理解に苦しんでいます^^;
しかし、なんとか参考にして解読したいと思います。しっかり考えて分からないならまた質問したいと思います。
参考になりました！！