配列による二分木

数値表現で書かれているString(infix)を受け取ってlevel-order-traversalの配列に変換するプログラムを作りたいのですが。どうやって書いたらいいかさえもわかりません。さらに、Level-orderからPostfixとlevel-orderからprefixに画面に出力する方法も知りたいのですが、アドバイスをもしよかったらお願いします。

質問の補足として、
2*X/5+3*Y-4*Z-1　　　(infix)
をStringで受けたファンクションから
-/-*+*12X5*4Z 3Y (level order)
(空のノードと一番初めはスペースにしてます）
っという風に変えたいということです。

二分木は

....................-
.......... /....................-
.....*........+..........*..........1...
2..X.....5...*......4...Z................
................3..Y.........................

のようになっています。（ちょと解りづらくて申し訳ないですが.を抜かした部分が木になっています）
どなたかわかる方よろしくお願いします。

No.2 ベストアンサー 回答者： ChateauAres 回答日時： 2005/08/01 11:09

大学レベルの課題だと思いますが、作成者のレベルが推し量れる良い課題だと思います。

で、アドバイスだけですが
１．ノードのクラスを設計する
　（符号をどのように扱うか、レベル自体をノードの情報として保持するか）
２．Treeのクラスを設計する
　（追加・削除・表示の機能を実装）
３．infixの内容を解析するプログラムの検討
　（スタックを利用して、逆ポーランド表記に変換するのが楽かな）
４．スタックしたデータでノードのインスタンスを作成してTreeに追加
５．Treeの内容を表示
　（ついでにPreorderやInorderなど別の巡回法も実装すれば＋αの評価がもらえるかも）

二分木も逆ポーランドのプログラムもネットで多数Hitするので参考にすればよいでしょう。

この回答へのお礼

返事が遅くなって申し訳ないです。
なんとか、先生の助けを借りて、終わらせる事ができました。

ChateauAresもとても参考になりました。
ありがとうございました。

お礼日時：2005/08/16 14:03

No.1 回答者： hrm_mmm 回答日時： 2005/08/01 01:04

＞2*X/5+3*Y-4*Z-1　　　(infix)

＞-/-*+*12X5*4Z 3Y (level order)
こうはならないと思うのだけど？？
演算子の優先順位とかは通常の*/は+-より先に計算というものではないのでしょうか？
全部の演算子が等価だとすれば、手前から順になるべきだと思うし。
私の理解が間違っているのでしょうか？
どうしてこうなるのかアルゴリズムを補足して下さい。
でないとプログラムは書けません。

この回答への補足

すいません、間違えてました。。

問題は（2*X)/(5+3*Y)-(4*Z-1)
というのを前提としてました。
でもちょっとわかりづらいので、例を変えようと思います。

56+34*2-36*12/3+5*13-5*4+6 (infix)
の場合
+ - 6 + * - * 5 4 + * 5 13 56 * 36 / 34 2 12 3
(level order)

となると思いますが、また間違ってたらすいません。

＞演算子の優先順位とかは通常の*/は+-より先に計算＞というものではないのでしょうか？
はい、普通の計算の優先順位であっています。

そして、質問は、infixをStringで受け取り、level order の配列で返すという質問でした。
方法としては、演算子の優先順位順に演算子を前に持っていってその後に近くの数字を次に持ってくる！？のような方法で配列を並び替えればいいのでしょうか？

どういう方法で並び替えてよいのかわからなくて困っています。もし、わかるようでしたらアドバイスお願いします。

質問の内容がわからないようであったら、まだ補足します。間違いを指摘していただいてありがとうございました。

補足日時：2005/08/01 03:50