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

質問

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

　 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 · ベストアンサー

★アドバイス
　　　　０　
　　　／　＼
　　１　　　２
　／　＼　／　＼
３　　　４５　　６
　　　　／　＼
　　　８　　　　９
＞の木を行きがけ順で表示（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

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

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

回答No.4

sakusaker7

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

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

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

回答No.3

noname#50176

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

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

でした、すみません。

回答No.2

noname#50176

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

まずは、構造体の定義を見直してください。
二分木の、左部分木へのポインタと右部分木へのポインタの
２つが必要です。

お礼

二分木とは
*left;
*right;

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