行きがけ順で表示するプログラム

アルゴリズムの勉強をし始めたものです。
深さ優先探索で

　 0　
／ ＼
1 2
／＼ ／＼
3 4 5 6
／＼
8 9

の木を行きがけ順で表示（0,1,3,4,2,5,8,9,6）するC言語のプログラムを作っています。参考書を見ながら途中まで作ってみました


/* 行きがけ順で表示するプログラム */
/* 配列のデータが9個と決まっている場合 */
#include <stdio.h>
#define N 100

struct cell
{
int node;
struct cell *next;
};

void preorder(int n, struct cell **S);/* 前順 */

int main()
{
struct cell *S[N];
int root;
preorder(root, S);
}


void preorder(int n, struct cell **S)/* 前順 */
{
struct cell *q;
printf("%d", n);/* 表示 */
q = S[n];
while(q != NULL)
{
preorder(q -> node, S);/* 再帰 */
q = q -> next;
}

return;
}

ここから例えば配列のデータが1,3,5,7,9,11,13,15,17と決まっている場合、どうやってこれらのデータを設定すればいいのでしょうか？参考書を見てもアルゴリズムの部分しか書かれていなかったので完成形が見えてこないです。
よろしくお願いします。

No.6 ベストアンサー 回答者： Oh-Orange 回答日時： 2007/05/22 15:14

★アドバイス

　　　　０　
　　　／　＼
　　１　　　２
　／　＼　／　＼
３　　　４５　　６
　　　　／　＼
　　　８　　　　９
＞の木を行きがけ順で表示（0,1,3,4,2,5,8,9,6）するC言語のプログラムを作っています。参考書を見ながら途中まで作ってみました
　↑質問内容に『木』と表現しています。二分木の木でしょ。
　それなら left、right の構造体を使って書き換えて下さい。
＞次の項に書いてあったので使わないと思ったのですが実現不可能ですか？
　↑回答者 No.1 さんのお礼から問題文の次に二分木のアルゴリズムの解説をしているのでは？
＞配列のデータが1,3,5,7,9,11,13,15,17と決まっている場合、どうやってこれらのデータを設定すればいいのでしょうか？
　↑単純に二分木の構造体に順番に 1～17 のデータを登録(設定)すれば良い。
　このためには、二分木用のデータ設定関数を作ります。
・登録の手順
　(1)root の左『1』をセット
　(2)root の右『3』をセット
　(3)右の『3』に『5』をセット
　(4)右の『5』に『7』をセット
　(5)右の『7』に『9』をセット
　(6)右の『9』に『11』をセット
　(7)右の『11』に『13』をセット
　(8)右の『13』に『15』をセット
　(9)右の『15』に『17』をセット
　となります。
　配列のデータがすでに整列しているので綺麗に二分木に登録されません。→右の枝にずっと
　セットすることになってしまう。二分木の場合は、登録するデータがランダムなデータの時
　平均化して枝分かれして綺麗に登録できます。これが二分木の特徴。
・http://oshiete1.goo.ne.jp/qa2627991.html→『再帰呼び出しで求めたい経路を表示させたい！』
　↑の過去質問も参考にして下さい。
　以上。おわり。

参考URL：http://oshiete1.goo.ne.jp/qa2627991.html

No.5 回答者： asuncion 回答日時： 2007/05/22 09:15

> このことは次の項に書いてあったので使わないと思ったのですが

> 実現不可能ですか？

１つの根から２つの方向へ枝分かれするような、
今回やりたいことを実現することは、
以下お考えになっているデータ構造（単方向リスト）では
できません。

No.4 回答者： sakusaker7 回答日時： 2007/05/22 03:51

struct cell

{
int node;
struct cell *next;
};

この定義では質問で提示されている構造を表すのは無理でしょう。
どんな参考書をお使いなのかはわかりませんが、これは単方向リストで
使われるデータ構造だと思います。

参考書を読み間違えているか、参考書の出来が悪いのかいずれかではないでしょうか。

No.3 回答者： noname#50176 回答日時： 2007/05/22 01:22

#2です

＜下段の訂正＞
>再帰をループネストすると処理系によっては無限ループになります。
>せめて、

if (q == NULL) return;
preorder(q -> node, S);/* 再帰 */
q = q -> next;
return;

でした、すみません。

No.2 回答者： noname#50176 回答日時： 2007/05/22 01:01

int root=1,data[N]={3,5,7,9,11,13,15,17,0};

struct cell *S[N];

for (int i=1;i<18;i++)
{
S[i]=(cell*)malloc(sizeof(cell));
S[i]->node=data[i>>1];
}
　　　　 S[17]=0;
preorder(root, S);
return 0;

で＜1,3,5,7,9,11,13,15,17＞と出力されますが、
趣旨が違っていたらすみません。

逸脱するのですが、
while(q != NULL)
{
preorder(q -> node, S);/* 再帰 */
q = q -> next;
}
再帰をループネストすると処理系によっては無限ループになります。
せめて、
if (q != NULL) {q = q -> next;return;}
preorder(q -> node, S);/* 再帰 */
にしたほうが安全ですよ。

No.1 回答者： asuncion 回答日時： 2007/05/21 21:11

まずは、構造体の定義を見直してください。

二分木の、左部分木へのポインタと右部分木へのポインタの
２つが必要です。

この回答へのお礼

二分木とは
*left;
*right;

のことですよね。
このことは次の項に書いてあったので使わないと思ったのですが実現不可能ですか？

お礼日時：2007/05/21 22:56