2分木と双方向線形リストを同時に実現する方法

質問

ファイルに書かれている文字列を読み込み，

(1)ソートしてファイル出力
(2)読み込んだ順と逆順にファイル出力

というプログラムを作成する場合，
(1)は２分木のデータ構造を用いて実現したのですが，２分木のデータ構造をそのまま利用することで逆順に出力させることは可能でしょうか？

私は無理だと思うので，２分木に加えて双方向の線形リストになるようにポインタを設定する必要があると考えているのですが，もっと上手く実現するアルゴリズムはあるでしょうか？

アドバイスを頂けるとありがたいです．

回答No.6

chie65536（@chie65535） · ベストアンサー

＞(1)は２分木のデータ構造を用いて実現したのですが

「２分木」って、もしかして「Binary Tree」かな？

Binary Tree ソートについて
http://www13.plala.or.jp/kmaeda/cs/treesort.htm

だったとしたら、上記ページで説明されてる構造になってる筈だから、構造体に「１つ前に追加したノードへのポインタ」っていうメンバーを増やして、以下のようにすれば良い。

１．グローバル変数に「最も最近に追加したノードへのポインタ」を増やし、NULLで初期化する。

２．１行読み込んで、新しいノードを作成したら「１つ前に追加したノードへのポインタ」のメンバーに「最も最近に追加したノードへのポインタ」を代入する。

３．代入したら「最も最近に追加したノードへのポインタ」に「たった今作成したノードのポインタ」を代入する。

・ソートしてファイル出力する場合

http://www13.plala.or.jp/kmaeda/cs/treesort.htm
の「Print関数」を参照。

・逆順にファイル出力する場合

すべてをツリーに挿入し終わったら「最も最近に追加したノードへのポインタ」から出力を始めて「１つ前に追加したノードへのポインタ」を辿って行き、NULLになったらやめる。

お礼

詳細な回答ありがとうございます．ポインタをグローバル変数を用いるのには気づきませんでした．これだと比較的プログラムが複雑にならなそうですね．

回答No.5

επιστημη（@episteme）

A) 行番号 と
B) その一行 とを組にして保持します。

Bをキーにソートすれば(1)が、
Aをキーにソートすれば(2)が得られます。

お礼

簡潔なアルゴリズムですね．全然思いつきませんでした．こちらでも実装してみたいと思います．

回答No.4

asuncion

念のため、逆順に出力するだけなら、単方向のリスト構造でじゅうぶんです。
双方向を使う必要性はありません。

お礼

将来拡張することを考えて，双方向で作ろうと思いました．逆方向へのポインタだけでもいいですが，逆方向をつけるのに比べて順方向をつけるのは容易なので．

回答No.3

sakusaker7

データ構造を生かして、とはあるけど、木のノードの構成をいじったらだめなんでしょうか?

木の本来のポインタとは別に線形リスト用のポインタを持たせておいて
ノードの生成のときにつないでいきゃあいいと思うのですが。

お礼

そう思い実装してみたのですが，複雑なアルゴリズムになってしまったので．もっと簡潔にする方法があればと思ったのですが，地道にやるのがいいみたいですね．

回答No.2

Tacosan

そもそも「読み込んだ順と逆順に出力する」のは「読み込んだ順」が分からないと不可能だ. そのことに気づいているんだろうか.
「２分木のデータ構造を用いて実現した」っていうのも「どのようなデータを保持してどのように用いたのか」が書かれていないので, 「そのまま利用して逆順に出力する」ことは「不可能だと思うけどひょっとしたらできるかもしれない」としか言えない. 「２分木のデータ構造」と書いてるけど, 「読み込んですぐに二分探索木に挿入した」んではないかと推測してみる＞#1.
(1) と (2) を逆の順序でやると小賢しいといわれて幸せかも.

お礼

やはり無理ですよね．線形リストを使いたいと思います．

回答No.1

SilverThaw

>もっと上手く実現するアルゴリズムはあるでしょうか？
ソートに対して2分木を採用した理由は何でしょうか？
2分木は親から複数の子に対してのノードをぶら下げていく方法ですから、ソートはかえって難しかったのでは？
（私個人にはツリー構造での実現方法というものは思いつきませんが……中点を最上位のノードとしても、その子のノードはどの位置を示すのかとか考えたくないですし）
双方向リストを使用した方が簡単ですよ。

お礼

２分木の既存のプログラムがあったので，それを応用して作ろうと思ったのと，探索などの機能を拡張する場合，２分木のほうが優れているという判断です．

純粋に双方向のポインタを付け加えようと思います．