StandardMLで二分木を左右反転する関数reflect:'a tree->'a treeを作成したい。
実行例;reflect(tree)

二分木を表すデータ型
datatype 'a tree=Empty | Node of 'a *'a tree * 'a tree;

A 回答 (2件)

reflect の引数は 'a tree なんだけど, それは Empty か Node かのいずれかです. で, Empty のときには単純に Empty を返せばいいので


reflect(Empty) = Empty
と書けます. 一方, Node のときは
reflect(Node(root, left, right))
とマッチングさせればよく, これにより Node の対応する要素が root, left, right に束縛されます. これらの変数を使って「どのような二分木を作るのか」を書いてやる. 単にこのノードで左右を入れ替えるだけなら
reflect(Node(root, left, right)) = Node(root, right, left)
だけど, 左右の部分木でも入れ替える必要があります. そしてそれは left および right のそれぞれに対して reflect を再帰的に適用すればできるはず, ですね.

この回答への補足

度々ありがとうございます。教えて頂いた文章を読みながらプログラムを作ってみました。

- fun reflect(Empty)=Empty
= | reflect(Node(root,left,right))=
= Node(root,reflect(right),reflect(left));

上記のプログラムでコンパイルおよび実行できましたが、正しく動作するものになっているでしょうか?教えてください。よろしくお願いします。

補足日時:2009/02/13 21:30
    • good
    • 0
この回答へのお礼

いろいろと教えて頂きありがとうございました。
本当に助かりました。

お礼日時:2009/02/14 15:36

困ってるのはわかるけど, 自分で解こうという気はちょっとでもありましたか? もし解こうという気があったのなら, 何かは考えたはずです. それを書いてください.


もし自分で解こうという気がないなら, ここで質問する資格はありません. 諦めてください.

この回答への補足

申し訳ありませんでした。実際にプログラムを書くことはできませんでしたが、アルゴリズムは考えることができてます。

二分木の右部分木と左部分木をそれぞれの節点で入れ替える作業を行えばよいということは分かりますが、実際にどのように右部分木を指定して入れ替えれば良いかが分かりません。

教えてください。よろしくお願いします。

補足日時:2009/02/13 13:01
    • good
    • 0

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!

今、見られている記事はコレ!

おしトピ編集部からのゆる~い質問を出題中

お題をもっとみる

このQ&Aを見た人が検索しているワード


このカテゴリの人気Q&Aランキング

おすすめ情報

カテゴリ