1

2つの二分木（t1とt2）を取り、t1の右下にt2を配置する新しいツリーを生成する関数を書いています。t2は、ノードがリーフでなくても、右の子が空である最初のノードに接続されます。

let rec adjoin_right (t1: 'a tree) (t2: 'a tree) : 'a tree

テストケース：

let test () : bool =
adjoin_right (Node (Empty, 1, Empty)) (Node (Empty, 2, Empty)) = 
Node(Empty, 1, Node (Empty, 2, Empty))
;; run_test "adjoin_right leaf" test

誰かがこの問題に対して正しい方向に私を導くことができますか？私はおそらくヘルパー関数を書かなければならないことを知っています。

4

1 に答える 1

2

再帰を機能させるには、次の2つの質問について考える必要があります。

  • t1の場合、結果はどうなるはずEmptyですか？

  • t1が空ではないが、のサブツリーに適用されたときに正しく機能する関数がある場合、このt1関数をどのように使用して結果を取得しますか？

これらを理解できれば、サブツリーに対して適切に機能する関数があります。

編集

再帰的な場合を考えてみましょう。l（左側のサブツリー）、r（右側のサブツリー）、およびv（ノードの値）があります。FPでは、これらの値を変更することはありません。あなたがしたいのは、正しい内容で新しいツリーを構築することです。では、これらの3つの材料から新しいツリーを作成するために、関数をどのように再帰的に使用しますか？難しいことではありません。実際には、1行のコードだけです。

于 2013-02-02T04:39:38.750 に答える