6

私はOCamlを使用しています。タイプがあります： 

type 'a bt = Empty | Node of 'a * 'a bt * 'a bt;;

また、BSTの例があります：

let tree = Node(1,Node(2,Node(4,Empty,Empty),Empty),Node(3,Node(5,Empty,Node(6,Empty,Empty)),Empty));

function: を記述する必要があります。breadthBT : 'a bt -> 'a listこれは、幅優先検索トラバーサルになります。上記の例のツリーでは、返されるはずです[1; 2; 3; 4; 5; 6]

その関数をどのように書くのですか？DSTを使用する次の関数のみを記述できます。

let rec breadthBT tree =
if tree=Empty then []
else let Node(w,l,r)=tree in (w::breadthBT l)@breadthBT r;;

上記の関数は (たとえば、ツリー) [1; を返します。2; 4; 3; 5; 6]。しかし、私はBFSを使用する関数を書くことができません。私たちを手伝ってくれますか？

4

2 に答える 2

5

これはコンパイル可能なソリューションではありません。ただのヒント。最上位のルート ノードから深いレベルのノードまで反復する必要があります。私たちの関数は、答えのアキュムレータとノードのリスト ('a bt 値) を 2 番目のパラメータとして受け取ります。トリプルの最初の要素を取得し、回答の次の部分を受け取ることで、このリストをマップできます。また、ツリーの次のレベルを評価する必要があります。各ノードには、最大で 2 つの子孫があります。リストをマッピングして_a_function_、子孫のリストを受け取るように申請できます。それはあなたのツリーの次のレベルになります。そして --- 再帰よりも。

A はこれを指定しません_a_function_。グーグルでconcatMapとは何かを調べてみてください。

ハッピーハッキング！

于 2012-10-19T22:27:08.390 に答える
1

木に鼻をくっつけたと想像してください。メモ帳で位置をブックマークせずに、幅優先の方法でツリーをトラバースすることは可能ですか? いいえ、順序によって、あるブランチから別の無関係なブランチにジャンプする可能性があるためです。したがって、「訪問する残りの位置」が記載されたメモ帳が必要です。メモ帳から次の残りの位置を選択し、盲目的にそこにジャンプします。訪問した位置をメモ帳から消去したので、まだ訪問していないノードにいます。そして、中間のノードにアクセスしないとツリーをたどることができないため、現在上の 2 つのノードにはアクセスしていません。しかし、あなたは枝を直接登る本能に抵抗します - 一体、これは幅です最初の注文。これら 2 つの未訪問ノードを忘れたくないので、それらをノートブックに入れます。ノートの前か後ろか、どこに置きますか？もちろん、そうでなければすぐにそれらの 1 つを選ぶことになりますが、それは避けたいことです。出来上がり: メモ帳はノードの FIFO キューであり、アキュムレータとして保持 (つまり、渡す) しますが、アクセスするサブツリーを選択するために消費します。

于 2012-10-20T09:56:07.563 に答える