二分探索木からソートした連結リストを得たい

Question

現在、事前に作成した二分探索木を通りがけ順で走査し、それを元にソートされた連結リストを得る関数を実装しています。

おおまかな実装は、

List *sort_tree(List *tree,List *next);

引数は、部分木の根ノードを指すポインタ・末尾ノードにつなぐノードへのポインタ
戻り値は、連結リストの先頭を指すポインタ
として実装したいと考えています。
しかし、通りがけ順で走査するところまでは理解できるのですが、それを連結リストとしてつなげていくプログラムがわからないので、どなたか教えていただけると幸いです。

※ちなみに、Listは自作の構造体で以下のように定義されています。

typedef struct seiseki_list List;
struct seiseki_list{
	float gpa;/*累積GPA*/
	int credit;/*累積単位数*/
	char name[200];/*名前（アルファベット）*/
	List *next; /*次のセルへのポインタ*/
	List *left,*right;/*二分探索木で用いる部分木へのポインタ*/
};

Comments

[Zuishin]

なにがわからないのかわかりません。
探索して見つけたものを次々にリストに放り込んでいくだけではないのですか？

[Kassy11]

通りがけ順で探索してその順番通りに連結リストとしてつないでいきたいのですが、再帰的な処理に慣れていないこともありどのようなコードを書けばいいのか全くわからない状態です。（ヒントなどをいただけるとありがたいです（汗））

[Zuishin]

まず、リストに何か要素を入れることはできるのですか？

[Kassy11]

このプログラムの大きな流れとして、
①コマンドライン引数でソートしたいメンバ名・入力ファイル名・出力ファイル名
②入力関数で入力ファイルを読み込み連結リストとしてつなぐ
③出来上がった連結リストをもとに、コマンドライン引数で受け取ったメンバで二分探索木をつくる
→ここまでは実装済み
④二分探索木を通りがけ順で走査してソート済みの連結リストをつくる
→ここを実装中
⑤出力関数で出力ファイルに書き込む
という感じです。

[Zuishin]

このプログラム以前に、リストに要素を挿入することはできるんでしょうか？

[Kassy11]

入力ファイルを読み込み連結リストを得るだけなので挿入はできないかと思います

[Zuishin]

では、この質問の問題を解決することは不可能になります。どこかに誤解があるかもしれないので、よく見直してください。

[Kassy11]

なぜでしょうか？
挿入ではなく、もとの連結リストを破壊してソート済みの連結リストを得ようとしているのですが‥

[Zuishin]

挿入と削除のできるリストを実装するところから始めてください。

[jimbe]

以前のご質問の続きと考えて宜しいでしょうか.
以前はnextで繋がったリストからright/leftでツリーを構成しましたが, 今度はそのツリーから改めて, nextによる(ソートされた)リストを得ようと言うわけですね.

[Kassy11]

返信遅れました、そういうことです！

[jimbe]

でしたら, 前回のご質問へのリンクと, そこからこのご質問に至るまでに作成されたコードとその結果等をご提示頂けると良いかと思います.
このご質問からご覧になった方には経緯が分かりませんし, コードの無いご質問では「やって欲しいことを丸投げしている」と受け取られかねません.

Answer 1

Zuishin さんが最初におっしゃった通り, ツリーの訪問中にリストに追加するだけです.

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

typedef struct seiseki_list List;
struct seiseki_list{
  float gpa;/*累積GPA*/
  int credit;/*累積単位数*/
  char name[200];/*名前（アルファベット）*/
  List *next; /*次のセルへのポインタ*/
  List *left,*right;/*二分探索木で用いる部分木へのポインタ*/
};

void append(List *list, List *node) {
  while(list->next != NULL) list = list->next;
  list->next = node;
  node->next = NULL;
}

void visit(List *list, List *node) {
  if(node == NULL) return;
  visit(list, node->right);
  append(list, node);
  visit(list, node->left);
}

List *sort_tree(List *tree, List *next) {
  List top; //nextのみをリストの最初のノードを指すために使用
  top.next = NULL;
  visit(&top, tree);
  append(&top, next);
  return top.next;
}

void setTest(List *dst, char *name, List *right, List *left) {
  strcpy(dst->name, name);
  dst->right = right;
  dst->left = left;
}

int main() {
  List datas[8], end, *list;

  setTest(&datas[0], "A", &datas[1], &datas[2]);
  setTest(&datas[1], "B", &datas[3], &datas[4]);
  setTest(&datas[2], "C", &datas[5], NULL     );
  setTest(&datas[3], "D", NULL     , NULL     );
  setTest(&datas[4], "E", &datas[7], &datas[6]);
  setTest(&datas[5], "F", NULL,      NULL     );
  setTest(&datas[6], "G", NULL,      NULL     );
  setTest(&datas[7], "H", NULL,      NULL     );

  setTest(&end, "end", NULL, NULL);

  list = sort_tree(datas, &end);

  // D B H E G A F C end なら OK
  for(; list != NULL; list=list->next) printf("%s\n", list->name); 

  return 0;
}

Comments

[Kassy11]

https://gyazo.com/5ffb1841e80362ba947ca13505ee1827
この図のようにはじめは根を表すポインタとNULLを引数にわたしてソートを行いたいのですが、appendのwhile文のところで何度も無限に繰り返し処理がされてしまいます

[jimbe]

sort_tree の 第二引数は NULL もありだったのですね, 失礼しました.
append 関数の 3 行目で node->next = NULL としているため, 恐らく落ちていると思います.
sort_tree 関数の 4 行目
append(&top, next);
を
if(next != NULL) append(&top, next);
としてはどうでしょうか.

[Kassy11]

すみません、大丈夫でした。
何度も質問に答えていただきありがとうございます。助かります（汗）