1

これは宿題の質問です。

私の質問は簡単です: ツリーの最も深い要素のリストを返す 'a btree -> 'a リスト型の関数 btree_deepest を書きます。ツリーが空の場合、最深部は [] を返す必要があります。入力ツリーの複数の要素が同じ最大深さにある場合、最深部は、それらの最深部の要素を含むリストを返す必要があり、事前順序トラバーサルに従って順序付けされます。関数は提供された btree_reduce 関数を使用する必要があり、再帰的であってはなりません。

これが私のコードです：

(* Binary tree datatype. *)
datatype 'a btree = Leaf | Node of 'a btree * 'a * 'a btree

(* A reduction function. *)
(* btree_reduce : ('b * 'a * 'b -> 'b) -> 'b -> 'a tree -> 'b) *)
fun btree_reduce f b bt =
   case bt of
   Leaf => b
   | Node (l, x, r) => f (btree_reduce f b l, x, btree_reduce f b r)

(* btree_size : 'a btree -> int *)
fun btree_size bt =
    btree_reduce (fn(x,a,y) => x+a+y) 1 bt

(* btree_height : 'a btree -> int *)
fun btree_height bt =
    btree_reduce (fn(l,n,r) => Int.max(l, r)+1) 0 bt

最も深い要素のリストを作成するには、btree_reduce に渡す関数を作成する必要があることを知っています。

再帰の使用が許可されている場合は、左右のノードの高さを比較し、どちらか高い方のブランチで再帰します (または、同じ高さの場合は両方で再帰します)。次に、高さがゼロのときに現在の要素を返し、これらの要素をリストにスローします。

始めるには正しい方向へのプッシュが必要だと思います...

ありがとう！

アップデート：

コンパイルされないソリューションの試みを次に示します。

fun btree_deepest bt =
let
val (returnMe, height) = btree_reduce (fn((left_ele, left_dep),n,(right_ele, right_dep)) => 
    if left_dep = right_dep 
        then 
            if left_dep = 0 
                then ([n], 1) 
                else ([left_ele::right_ele], left_dep + 1)
        else 
            if left_dep > right_dep
                then (left_ele, left_dep+1) 
                else (right_ele, right_dep+1)
    ) 
    ([], 0) bt
in  
    returnMe
end
4

2 に答える 2

3

最大深度の要素を取得するには、 がアクセスするすべてのサブツリーについて、2 つのことを同時に追跡する必要がありますbtree_reduce。そのサブツリーの最大深度と、その深度で見つかった要素です。この情報を何らかのデータ構造にまとめると、 (の署名'bによると) タイプが得られます。btree_reduce

に提供する関数で 2 つのサブツリーの結果を結合する必要がある場合、次のbtree_reduce3 つのケースが考えられます。サブ結果。サブ結果は、各サブツリーの最も深いノードの深さとノード値を表すことを思い出してください。それらを組み合わせて、現在のツリーの深さと最も深いノードの値を取得する方法を考えてください。

さらにポインタが必要な場合は、btree_deepestready の実装があります。これを共有したいと思っています。あなたが解決策ではなくヒントを具体的に（そして名誉に）求めたので、まだ投稿していません。

于 2012-11-09T08:42:52.380 に答える
1

あなたのコードを見てください。X_ele が単一の要素であるかリストであるかに基づいて混乱が生じているようで、型エラーが発生します。上記の最初の「else」ブランチで「@」演算子を使用してみてください。

        if left_dep = 0 
            then ([n], 1) 
            else (left_ele @ right_ele, left_dep + 1)
于 2012-11-10T22:37:47.140 に答える