データ構造の保存法について

質問

データ構造のメモリ上の状態、つまりポインターによるノード間のつながりをファイルに保存して、そのファイルを読み込むとコンピュータ上で前回のデータ構造を再現（ポインターによるつながりを再現）できる方法を探しています。
現在バイナリーツリーで上記の保存法を色々探したり考えたりしているのですが、いい方法が見つかりません。
各ノードに番号をふってファイルに保存し、次回読み込んだときに上手く工夫してやればできるかな、といった程度です。
ご存知の方がおられたら教えていただけないでしょうか？
よろしくお願いいたします。

回答No.6

noocyte · ベストアンサー

お待たせしました．読み込み用サンプルプログラムです．

> 今まで、テキストでの保存しかやったことがないのでこれを機会に
> バイナリでの保存を勉強していきたいと思います。

#5 は fwrite() を fprintf() に変えればほとんどそのままでテキストファイル用になります．
ただし，読み込み側では構文のチェックなどを行わなければならないので少々面倒です．

●#5 に対する変更
#5 で使用したデータ構造を，読み込み/書き出しで共用できるようにするため，一部変更しました．
(1) Node_t::name[] の要素数の宣言を変更：MAXNAME → 1 に変更．
読み込み時にスタックを余計に消費しないようにするため．
この変更は #5 のプログラムには影響なし．
実際には必要なサイズを確保する．名前の長さは事実上無制限になる．
#define MAXNAME は不要になったので削除．
(2) TraverseArgs_t のメンバを変更
・out メンバを，読み込みにも使用するようにしたため，名前を fp に変更．
#5 のプログラムで out を fp に変更すること．
・読み込みに必要なメンバ (nodeTable) を追加．この変更は #5 のプログラムには影響なし．

●問題点
さっき，#5 のプログラムの問題に気付きました．(^^;)
ツリーが空 (節点が一つもない，root＝NULL) の時はクラッシュします．
つまり，空のツリーは保存できません．
現在の実装では，子節点の childExists フラグを書くようになっていますが，
それを廃止して，節点自身の nodeExists フラグを書くようにする方がいいです．
つまり，SaveSubtree() で最初に nodeExists = (node != NULL) を読み書きし，
それが偽ならば節点の読み書きをしないようにします．
(#5 と対応させるため，次の読み込みプログラムにはこの変更を行っていません．)

●読み込み用サンプルプログラム (コンパイルは通してますが，動かしてはいません．)

#include <stdio.h>
#include <stddef.h>
#include <stdlib.h>
#include <string.h>

#define MAXLINKS 4 /* １節点から出る最大リンク数 */

#define OK 0
#define FAIL (-1)

/* 節点のデータ構造の定義 */
typedef struct Node Node_t;
struct Node {
Node_t *child[2]; /* 左右の子節点へのポインタ */
Node_t *link[MAXLINKS]; /* 木の親子関係以外の節点間リンクまたは NULL．*/
/* この配列の添字がリンクIDとなる．*/
unsigned no; /* 節点番号 */

/* 以下，この節点自身のデータ */
int data;
char name[1]; /* 節点名 (の最初の１バイトのみ宣言) */
};

/* トラバース中に各節点からアクセスされる変数をまとめた構造体 */
typedef struct {
unsigned nNodes; /* トラバース中は現在までに読み込んだ節点数，トラバース後は節点の総数．*/
unsigned nLinks; /* 節点間リンクの総数 */
Node_t **nodeTable; /* 節点番号を節点へのポインタに変換するための配列 */
FILE *fp; /* ファイルの入出力ストリーム */
const char *fileName; /* ファイル名 */
} TraverseArgs_t;

/* 変数 var (ポインタ以外) をバイナリファイルから読む．*/
#define ReadVar(var, in) (fread(&(var), 1, sizeof(var), (in)) == sizeof(var))

/* node 以下の部分木を削除する．*/
void DeleteSubtree(Node_t *node)
{
if(node != NULL) {
unsigned i;

for(i = 0; i < 2; i++) DeleteSubtree(node->child[i]);
free(node);
}
}

/* 読み込みエラーのメッセージを出力する．*/
void ReadError(const TraverseArgs_t *args)
{
if((errno == 0) && feof(args->fp)) {
/* おそらく，ファイルが途中で終わってしまったためのエラー．*/
fprintf(stderr, "\"%s\": ファイルが途中で終わっています。", args->fileName);
} else {
fprintf(stderr, "\"%s\": 読み込みエラー (%s)\n", args->fileName, strerror(errno));
}
}

/* 部分木を読み，その根節点へのポインタを *pNode に返す．*/
int LoadSubtree(Node_t **pNode, TraverseArgs_t *args)
{
Node_t nodeBuf; /* 読み込んだ節点データを一時的に格納しておくためのバッファ */
Node_t *node; /* 読み込み成功時に生成される節点を指す．*/
char *name = NULL; /* 節点名を一時的に格納するバッファを指す．*/
size_t length; /* 節点名のバイト数 (終端 '\0' を含まない．) */
unsigned i;
unsigned char childExists; /* 子節点が存在しているときそのときに限り真．*/

*pNode = NULL; /* エラーの時に返す値を設定しておく．*/

/* nodeBuf を初期化する．
* nodeBuf.link[*] を NULL に，nodeBuf.name を空文字列に初期化しておく必要があるので，
* これらを memset() でまとめて行う．
*/
memset(&nodeBuf, 0, sizeof(nodeBuf));

/* 節点番号および節点自身のデータを読む．*/
if(!ReadVar(nodeBuf.no, args->fp) ||
!ReadVar(nodeBuf.data, args->fp) ||
!ReadVar(length, args->fp)) {
ReadError:
ReadError(args);
goto Error;
}
if(length > 0) {
/* 名前が空文字列でない場合 */
/* 名前用のバッファを確保する．*/
if((name = malloc(length + 1)) == NULL) {
NoMemory: /* メモリ不足 */
fprintf(stderr, "%s\n", strerror(errno));
goto Error;
}
/* 名前を読む．*/
if(fread(name, 1, length, args->fp) != length) goto ReadError;
name[length] = '\0';
}

/* 左右の子節点以下の部分木を読む．*/
for(i = 0; i < 2; i++) {
if(!ReadVar(childExists, args->fp)) goto ReadError;
if(childExists && (LoadSubtree(&nodeBuf.child[i], args) == FAIL)) goto Error;
}

/* 新しい節点を作成する．
* (下記の malloc() の引数は，本来は
* offsetof(Node_t, name[0]) + length + 1 (終端 '\0' の分)
* だが，定数を一つにまとめて書いてある．)
*/
if((node = malloc(offsetof(Node_t, name[1]) + length)) == NULL) goto NoMemory;
/* nodeBuf を *node にコピーする．*/
*node = nodeBuf;
if(name != NULL) {
/* 節点名をコピーする．*/
strcpy(node->name, name);
free(name);
}

/*読み込み成功 */
args->nNodes++; /* 読み込んだ節点数を数える．*/
*pNode = node; /* 読み込んだ部分木の根節点へのポインタを返す．*/
return OK;

Error:
if(name != NULL) free(name);
for(i = 0; i < 2; i++) DeleteSubtree(nodeBuf.child[i]);
return FAIL;
}

/* 節点番号を節点へのポインタに変換するためのテーブル (配列) を作成する．
* node 以下の部分木の各節点をテーブルに登録する．
* args->nodeTable[0 ～ args->nNodes-1] は NULL に初期化されていなければならない．
*/
int MakeNodeTable(Node_t *node, TraverseArgs_t *args)
{
if(node != NULL) {
unsigned i;

if((node->no < 1) || (node->no > args->nNodes)) {
fprintf(stderr, "節点番号 %u は範囲外です。(有効範囲：1～%u)\n",
node->no, args->nNodes);
return FAIL;
}
i = node->no - 1; /* 節点番号を配列の添字に変換．*/
if(args->nodeTable[i] != NULL) {
/* 既に同じ節点番号で別の節点が登録されている場合 */
fprintf(stderr, "節点番号 %u が重複しています。\n", node->no);
return FAIL;
}
args->nodeTable[i] = node; /* node を登録する．*/

/* node の子孫を登録する．*/
for(i = 0; i < 2; i++) {
if(MakeNodeTable(node->child[i], args) == FAIL) return FAIL;
}
}
return OK;
}

/* 節点番号を節点へのポインタに変換する．*/
Node_t *NodeNoToPointer(unsigned nodeNo, const TraverseArgs_t *args)
{
Node_t *node;

if((nodeNo < 1) || (nodeNo > args->nNodes)) {
fprintf(stderr, "節点番号 %u は範囲外です。\n", nodeNo);
return NULL;
}
if((node = args->nodeTable[nodeNo]) == NULL)
fprintf(stderr, "節点番号 %u は定義されていません。\n", nodeNo);
return node;
}

/* 全リンク情報を読む．*/
int LoadLinks(const TraverseArgs_t *args)
{
Node_t *fromNode, *toNode;
unsigned fromNodeNo, toNodeNo, linkId, i;

for(i = 0; i < args->nLinks; i++) {
/* １組のリンク情報を読む．*/
if(!ReadVar(fromNodeNo, args->fp) ||
!ReadVar(linkId, args->fp) ||
!ReadVar(toNodeNo, args->fp)) {
ReadError(args);
return FAIL;
}
if(linkId >= MAXLINKS) {
fprintf(stderr, "\"%s\", Link #%u: LinkID %u は範囲外です。\n",
args->fileName, i, linkId);
return FAIL;
}
if(((fromNode = NodeNoToPointer(fromNodeNo, args)) == NULL) ||
((toNode = NodeNoToPointer(toNodeNo, args)) == NULL))
return FAIL;
/* リンク読み込み成功：リンクを設定する．*/
fromNode->link[linkId] = toNode;
}
return OK;
}

/* バイナリツリー全体をバイナリファイルから読む．
* 出力：(1) *pRoot：ツリーの根節点へのポインタ．
* (2) *pNodes：ツリーの全節点数．
*/
int LoadTree(const char *fileName, Node_t **pRoot, unsigned *pNNodes)
{
TraverseArgs_t args;
Node_t *root = NULL; /* バイナリツリーの根節点 */

/* エラーの場合に返す値を設定しておく．*/
*pRoot = NULL;
*pNNodes = 0;

args.nNodes = 0;
args.nLinks = 0;
args.nodeTable = NULL;
//args.fp = NULL;
args.fileName = fileName;
if((args.fp = fopen(fileName, "rb")) == NULL) {
fprintf(stderr, "\"%s\" をオープンできません。(%s)\n", fileName, strerror(errno));
goto Error;
}

/* 木構造および全節点の情報を読み込むとともに，節点数を数える．*/
if(LoadSubtree(&root, &args) == FAIL) return FAIL;

/* 全リンク数を読む．*/
if(!ReadVar(args.nLinks, args.fp)) {
ReadError(&args);
goto Error;
}

if(args.nLinks > 0) {
/* リンク情報がある場合 */

/* 節点番号を節点へのポインタに変換するためのテーブルを作成する．
* 配列の全要素を NULL に初期化しておく必要があるため，
* malloc() ではなく calloc() を使用する．
*/
if((args.nodeTable = calloc(sizeof(args.nodeTable[0]), args.nLinks)) == NULL) {
/* メモリ不足 */
fprintf(stderr, "%s\n", strerror(errno));
goto Error;
}
if(MakeNodeTable(root, &args) == FAIL) goto Error;

/* リンク情報を読む．*/
if(LoadLinks(&args) == FAIL) goto Error;

free(args.nodeTable);
args.nodeTable = NULL;
}

/* 読み込み成功 */
fclose(args.fp);
return OK;

Error:
if(args.nodeTable != NULL) free(args.nodeTable);
if(args.fp != NULL) fclose(args.fp);
DeleteSubtree(root);
return FAIL;
}

回答No.8

lv4u

No.4です。回答へのお礼に

>>データ構造を扱い始めて日が浅く、データ構造を作って計算するのはできるのですが、構造の保存と読み込みがなぜか上手くできないんです。

とありますが、「データ構造を使って計算」ってことは、例えば部品展開を行って原価計算などを行うのに似たような処理でしょうか？
ちょっとアプローチを変えて、メモリ上のポインターで構成されるツリー関係を表現できるキーの値（構成）を考えてそのキーとデータ本体で表現することにしたらどうでしょうか？
例えば、２レベルのデータで、Ａの下にＡ１、Ａ２の２つのデータがあるなら、３つのデータはそれぞれ「Ａ＠＠」、「ＡＡ１」、「ＡＡ２」のキーで表現できます。（＠は未使用キー部の値とします）
このように考えてしまうと、キーの値と、データ本体をファイルに書いたり読んだりできればいいことになります。また、メモリー上の処理は、キー値とデータ本体のペアに対して、追加・削除・変更・検索等の処理が可能であればＯＫですね。

そう考えると、思い浮かぶのはＣ＋＋のＳＴＬにあるｍａｐです。以下は、サンプルとして、「全てのASCII文字とコードとの対応を書き込んで、それを表示するプログラム」ですが、こんな感じでキーとデータをメモリにマップするプログラムが簡単にできます。

// 反復子を使ってマップを巡回する
#include <iostream>
#include <map>
using namespace std;

int main()
{
map<char, int> m;
int i;

// マップにペアを挿入する
for(i=0; i<26; i++)
m.insert(pair<char, int>('A'+i, 65+i));

map<char, int>::iterator p;

// マップの内容を表示する
for(p = m.begin(); p != m.end(); p++) {
cout << p->first << " has ASCII value of ";
cout << p->second << endl;
}

return 0;
}
（ＳＴＬ標準講座　P.139より）

実際には、このプログラムの「first」がintではなく、文字列型のキーに、「second」がデータ本体になるので、構造体として表現するようになると思います。
ちょっとＳＴＬの使い方が複雑ですが、ロジックを作らなくていいので、お手軽です。参考になればいいのですが。

お礼

ご回答ありがとうございます。
mapですか。選択肢外でした。
ただ、mapだとキーのソートによってで単方向ポインタなら実現できそうですが、私が作ろうとしている双方向ポインタは無理ではないでしょうか？
あと、構造体に格納するデータは複数あるのでmapでは対応できないような気がします。
私の勘違いであれば申し訳ございません。参考意見ありがとうございました。

回答No.7

noocyte

#6 です．ちょっと訂正．

LoadTree() の中で，
> if(LoadSubtree(&root, &args) == FAIL) return FAIL;
は
if(LoadSubtree(&root, &args) == FAIL) goto Error;
に変更してください．(args.fp がクローズされないので．)

それから，
> return OK;
の前に，
*pRoot = root;
*pNNodes = args.nNodes;
を追加してください．

お礼

最後まで懇切丁寧にご回答いただき本当にありがとうございます。
まだ全て理解できていませんが、サンプルプログラムを参考にして何とかプログラムを書き上げたいと思います。
感謝しても仕切れません。この度はありがとうございました。

回答No.5

noocyte

#2 です．

> 正直なところ、保存はできたとしてどうやって読み込むのかが
> いまいち分からず難しいなと感じているのですが、

読み込みのプログラムは次回に投稿します．乞御期待．(^^)

> テキストファイルの場合は読み込みの際のファイル処理（文字列の処理）が
> 面倒なのでバイナリファイルの方が読み込みが簡単だということでしょうか？

そうです．

> その場合例えば各ノードに自身の番号とリンク先の番号を持たせ
> それをファイルに書き込むのでしょうか？

ファイルに書き込む情報としてはそうです．ただ，メモリ内のデータ構造としては，
リンク先番号ではなくリンク先節点へのポインタを持つ方が一般には高速に処理できます．
(リンク先番号から節点を検索する処理が不要なため．ただしすべての節点が配列に
なっており，その配列要素の番号が節点番号 (＋定数) に一致している場合は高速に
検索できるのでポインタでなく番号でもかまいません．)

したがって，ファイルの読み書きの際にノード番号 ⇔ 節点へのポインタの相互変換を
行う必要があります．

ツリーをファイルに書き出すサンプル・プログラムを後で示します．
その前提は次のとおりです．

・各節点は，他の節点へのリンク (ポインタ) を最大 MAXLINKS 個持つことができる．
(これにはツリーの親子関係を定義するリンクは含まない．)
・各節点固有のデータの保存方法の参考例を示すため，各節点は１個の int と１個の
文字列を持つものとする．

このプログラムは次の手順でツリーをファイルに書き出します．

(1) ツリーをトラバース (全節点を順番に渡り歩く) し，各節点に番号を振るとともに，
各節点のデータをファイルに書き出す．同時に，後で書き出すべきリンクの総数も
数えておく．

(2) 再度ツリーをトラバースし，節点間のリンク情報をすべて書き出す．最低限リンク元と
リンク先の節点の番号が必要だが，汎用性を持たせるためにもう少し情報を追加する．
今回の場合，１つの節点が他の節点へのリンクを複数持ちうるので，それらのうちの
どれなのかを識別するためのリンク ID を追加する．このリンク ID は，節点から見た
このリンクの「役割」を示す．(例：「直前の節点」，「次の節点」，「親」，「左の子」，
「右の子」など)
１組のリンク情報は次のようになる．
(a) リンク元節点番号
(b) リンク元のリンクID
(c) リンク先節点番号
(d) リンク先のリンクID：今回のプログラムでは省略する．(b) から自動的に決まる
こともある．例えば (b) が「直前の節点」ならば，(d) はその逆の「次の節点」
となる．

/* サンプル・プログラム (コンパイルは通してますが動かしてみてはいません．) */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAXLINKS 4 /* １節点から出る最大リンク数 */
#define MAXNAME 128 /* 節点名の最大バイト数 (終端 '\0' を含む) */

#define OK 0
#define FAIL (-1)

/* 節点のデータ構造の定義 */
typedef struct Node Node_t;
struct Node {
Node_t *child[2]; /* 左右の子節点へのポインタ */
Node_t *link[MAXLINKS]; /* 木の親子関係以外の節点間リンクまたは NULL．*/
/* この配列の添字がリンクIDとなる．*/
unsigned no; /* 節点番号 (初期化時０，採番後は１以上の番号) */

/* 以下，この節点自身のデータ */
int data;
char name[MAXNAME]; /* 節点名 */
};

/* トラバース中に各節点からアクセスされる変数をまとめた構造体 */
typedef struct {
unsigned nNodes; /* トラバース中は現在の節点番号，トラバース後は節点の総数．*/
unsigned nLinks; /* 節点間リンクの総数 */
FILE *out; /* ファイルへの出力ストリーム */
const char *fileName; /* ファイル名 */
} TraverseArgs_t;

/* 変数 var (ポインタ以外) をバイナリファイルに書き出す．*/
#define WriteVar(var, out) (fwrite(&(var), 1, sizeof(var), (out)) == sizeof(var))

/* node 以下の部分木について，
* (1) 各節点に番号を振り，
* (2) リンクの数を数え，
* (3) 節点のデータをファイルに書き出す．
* (#2 の SaveNode() を改名．)
*/
int SaveSubtree(Node_t *node, TraverseArgs_t *args)
{
size_t length;
unsigned i;
unsigned char childExists;

node->no = ++args->nNodes; /* node に番号を振る．*/

/* node から出ているリンクの数を数える．*/
for(i = 0; i < MAXLINKS; i++) {
if(node->link[i] != NULL) args->nLinks++;
}

/* 節点番号および node 自身のデータ (data, name) を書き出す．*/
length = strlen(node->name);
if(!WriteVar(node->no, args->out) ||
!WriteVar(node->data, args->out) ||
!WriteVar(length, args->out) ||
(fwrite(node->name, 1, length, args->out) != length)) {
WriteError:
fprintf(stderr, "\"%s\": Write error (%s)\n", args->fileName, strerror(errno));
return FAIL;
}

/* 左右の子節点 (以下の部分木) を書き出す．*/
for(i = 0; i < 2; i++) {
childExists = (node->child[i] != NULL);
/* node->child[i] が存在するか否かを書き出す．*/
if(!WriteVar(childExists, args->out)) goto WriteError;
/* node->child[i] が存在すれば，それ (以下の部分木) を書き出す．*/
if(childExists && (SaveSubtree(node->child[i], args) == FAIL)) return FAIL;
}
return OK;
}

/* node 以下の部分木について，各節点から出ているリンクを書き出す．*/
int SaveLinks(Node_t *node, TraverseArgs_t *args)
{
unsigned i;

/* node から出ているリンクを書き出す．
* 書き出すデータは，リンク元番号，リンク元リンクID，リンク先番号．
*/
for(i = 0; i < MAXLINKS; i++) {
if(node->link[i] != NULL) {
if(!WriteVar(node->no, args->out) ||
!WriteVar(i, args->out) ||
!WriteVar(node->link[i]->no, args->out)) {
fprintf(stderr, "\"%s\": Write error (%s)\n", args->fileName, strerror(errno));
return FAIL;
}
}
}

/* 左右の子節点 (以下の部分木) 内のリンクを書き出す．*/
for(i = 0; i < 2; i++) {
if((node->child[i] != NULL) && (SaveLinks(node->child[i], args) == FAIL))
return FAIL;
}
return OK;
}

/* バイナリツリー全体 (根節点 root 以下) をバイナリファイルに書き出す．*/
int SaveTree(Node_t *root, const char *fileName)
{
TraverseArgs_t args;

if((args.out = fopen(fileName, "wb")) == NULL) {
fprintf(stderr, "Can't open \"%s\" (%s)\n", fileName, strerror(errno));
return FAIL;
}
args.fileName = fileName;

/* 全節点の情報および木構造を書き出すとともに，全リンク数を数える．*/
args.nNodes = 0;
args.nLinks = 0;
if(SaveSubtree(root, &args) == FAIL) goto Error;

/* 全リンク数を書き出す．*/
if(!WriteVar(args.nLinks, args.out)) {
fprintf(stderr, "\"%s\": Write error (%s)\n", fileName, strerror(errno));
goto Error;
}

/* 全リンクを書き出す．*/
if(SaveLinks(root, &args) == FAIL) goto Error;

/* 保存成功 */
fclose(args.out);
return OK;

Error:
fclose(args.out);
unlink(fileName); /* 出来損ないのファイルを削除する．*/
return FAIL;
}

ファイルの読み込みは次回に．

お礼

お礼が遅くなり申し訳ございません。
わざわざ、新しいサンプルプログラムを書き込んで頂くなど
大変詳しいご回答していただきありがとうございます。
プログラムのソースを途中まで拝見させて頂きました。
非常に参考になる内容でとても感激しています。
今まで、テキストでの保存しかやったことがないのでこれを機会に
バイナリでの保存を勉強していきたいと思います。

> ファイルの読み込みに関しては次回に.
お忙しい中お手数をかけて大変恐縮ですが、ご厚意に甘えたいと思います。今回のサンプルプログラムを参考に、ファイルの読み込み方を再度
自分で考えてみて、結果何が足りていなかったかを確認したいと思います。よろしくお願いいたします。

回答No.4

lv4u

メモリを指すポインターは、次回、保存したファイル等から読み込んだときに当然ながら同じアドレスにはならないですよね。なので、質問者様が考えられているように、ノードに番号を振るか、そのデータのキー情報をデータと共に書き込み、次回読み込んだときに、番号orキー情報に基いてバイナリツリーとポインタを再構築すればいいような気がします。

データ構造を作る技術がおありでしょうから、以上のことはあまり難しくはないと思いますけど・・・。

もちろん、読み込むごとにツリーの再構築の作業が必要ですが、検索が早くなるわけですので、それは仕方ない気がします。

お礼

お礼が遅くなり申し訳ございません。
ご回答していただきありがとうございます。
データ構造を扱い始めて日が浅く、データ構造を作って計算するのはできるのですが、構造の保存と読み込みがなぜか上手くできないんです。
アドバイスを参考にし、頑張りたいと思います。

回答No.3

keibou21

#1です

前者の回答は#2がされていますので、後者の回答を。

>XMLを用いる場合、データ構造を保存したファイルをXMLで読み込むこ
>とになると思うのですが、その後C言語で計算、解析をすることはでき
>るのでしょうか？つまり、XMLとCを上手く連携させることはできるの
>でしょうか？
Yes.
XMLは単なるテキストファイルですので、XMLの構文解釈を行いデータを取得するパーサを自作するなり既存のパーサを使用すれば可能です。
（既存のパーサは"xml　パーサ"や"xml　パーサ　フリー"のキーワードでググってみるといろいろ出てきます）
要はXMLで記述された外部ファイルを扱えるようにCでプログラムしないといけないってことです。

お礼

前回に引き続きご回答頂きありがとうございます。
アドバイスして頂いたとおり、"xml　パーサ"でググってみました。
C++で使えるXMLパーサには「Xerces-C++」というのがあるみたいですね。解説サイトや解説本を探して勉強してみようかと思います。
どうもありがとうございました。

回答No.2

noocyte

バイナリツリーを保存するのであれば，次のようにすれば簡単にできます．

/* バイナリツリーの節点 */
typedef struct Node Node_t;
struct Node {
Node_t *child[2]; /* 左右の子節点へのポインタまたは NULL */

/* 以下，この節点自身のデータ */
:
:
};

/* node 以下の部分木を out に保存する．*/
int SaveNode(const Node_t *node, FILE *out)
{
unsigned i;

(node 自身のデータを out に書く);

for(i = 0; i < 2; i++) {
(node->child[i] == NULL か否かを out に書く);
if(node->child[i] != NULL) {
/* node->child[i] 以下の部分木を保存する．*/
if(SaveNode(node->child[i]), out) == FAIL)
return FAIL;
}
}
return OK;
}

/* バイナリツリー全体 (根節点 root 以下) を保存する．*/
int SaveBinaryTree(const Node_t *root, const char *filename)
{
FILE *out;
int result;

if((out = fopen(filename, "w")) == NULL) {
fprintf(stderr, "Can't open \"%s\" (%s)\n", filename, strerror(errno));
return FAIL;
}
result = SaveNode(root, out);
fclose(out);
return result;
}

バイナリツリー以外の一般の木構造の場合は，最初の子節点
(以下の部分木) を書き出す前に子節点の個数を書いておき，
後はその個数だけ子節点 (以下の部分木) を書き出せば OK．

以上のように木構造の場合は，節点間のつながりを明示的に
書き出す必要はありませんが，木構造以外の有向グラフ
(２箇所以上から参照されている節点やループを含むもの)
の場合は節点間のリンクを明示的に書き出す必要があります．

バイナリファイルにするかテキストファイルにするかという問題もあります．
バイナリファイルの方がプログラムは簡単ですが，ファイルを
他の CPU や OS に持って行くときには互換性の問題が生じます．
テキストファイルだとその心配がない反面，読み込みの際に
構文解析を行わなければならず，プログラムは面倒です．

お礼

ご回答ありがとうございます。
保存法に関して大変参考になりました。

私が考えているバイナリーツリーは逆に辿る必要があり、隣接する節点間は双方向アクセスを可能にしなければならないので、１つの節点が最大で３箇所以上から参照されます。つまり、仰られた内容から判断すると、節点間のリンクを明示的に書き出す必要があることになると思うのですが、その場合例えば各ノードに自身の番号とリンク先の番号を持たせそれをファイルに書き込むのでしょうか？

>バイナリファイルにするかテキストファイルにするかという問題もあります．

正直なところ、保存はできたとしてどうやって読み込むのかがいまいち分からず難しいなと感じているのですが、テキストファイルの場合は読み込みの際のファイル処理（文字列の処理）が面倒なのでバイナリファイルの方が読み込みが簡単だということでしょうか？

色々質問して申し訳ありませんが、よろしくお願いいたします。

回答No.1

keibou21

XMLを使うと楽にできちゃうと思います。

> 現在バイナリーツリーで上記の保存法を色々探したり考えたりしているのですが、いい方法が見つかりません。
> 各ノードに番号をふってファイルに保存し、次回読み込んだときに上手く工夫してやればできるかな、といった程度です。
この方法でも可能です。

お礼

ご回答ありがとうございます。
XMLを早速調べてみたのですが、簡単にツリー構造をタグで表現できそうな感じですね。勉強してみます。

補足

質問内容に不足がありましたので、この場を借りて補足させていただきます。
C言語で書いたプログラムである計算を行い、計算結果を双方向のバイナリーツリーの各ノードに格納し、データ構造をファイルに保存し、必要なときに読み込んでノード内のデータを再度計算するもしくは解析することを考えています。ノードの数は多くて数千個位です。
また、「各ノードに番号をふって・・・」という方法でデータ構造を再構築する場合、上手く工夫するやり方が全く思いつかないのですが、いい方法をご存知でないでしょうか？

XMLを用いる場合、データ構造を保存したファイルをXMLで読み込むことになると思うのですが、その後C言語で計算、解析をすることはできるのでしょうか？つまり、XMLとCを上手く連携させることはできるのでしょうか？
理解が浅いため的外れな質問かもしれませんが、よろしくお願いいたします。