3

現在、F＃でバイナリツリーを構築していますが、ほぼ完成しています。私はこのタスクの最後の割り当てにいます。ここでは、バイナリツリーの文字列表現を作成することになっています。ツリーは次のように表示される必要があることを意味します。

例：("node" "value" ("node" "value" "Empty" "Empty") Empty)<-2つの空のサブツリーと空の右サブツリーを持つノードを持つ左側のサブツリーを持つルートノードを持つツリー。

私の木は次のようになります。

 type Btree<'a when 'a: comparison> = 
 |Node of  'a * Btree<'a> *Btree<'a> 
 |Leaf of 'a 
 |EmptyTree

これは私がどこまで得たかです： 

let rec treeToString bintree = 
    match bintree with
    |EmptyTree -> "Empty" //Check if the tree is empty
    |Node(inner, left, right) when inner = 0 -> "Empty"
    |Leaf x-> "Node"+x.ToString() //Returns "Node" and its value
    |Node(inner, left, right) when inner <> 0-> treeToString left //Need some kind of output here, but what?
    |Node(inner, left, right) when inner <> 0->treeToString right

私のメソッドは1つの値しか返さないので、私のソリューションの実際の問題は再帰部分を正しく取得することです。

だから私の質問は：私はここで何が間違っているのですか？

4

2 に答える 2

3

でモデル化できるため、ユニオンケースLeaf of 'aは冗長です。型宣言は次のように簡略化できます。Leaf(a)Node(a, Empty, Empty)

type BinTree<'a when 'a: comparison> = 
    | Empty 
    | Node of 'a * BinTree<'a> * BinTree<'a>

出力サンプルから、("node" "value" ("node" "value" "Empty" "Empty") Empty)最初にノード要素の値を表示してから、左ブランチと右ブランチを再帰的に表示する必要があります。

let rec treeToString bintree = 
    match bintree with
    | Empty -> "Empty"
    | Node(value, left, right) -> 
      sprintf "(Node %O %s %s)" value (treeToString left) (treeToString right)

ToString()メソッドをオーバーライドすることで、これをさらに進めることができます

type BinTree<'a> with
override x.ToString() = treeToString x

タイプが動作するsprintf "%O" bintreeようになど。

于 2012-11-25T14:54:39.037 に答える
0

で関数を宣言すると、関数recはそれ自体を呼び出すことしかできません。実際には、トラバーサル戦略（この場合、バイナリツリーのトラバーサル）は実装されません。

次のように、ツリーの順序どおりのトラバーサルを実装する必要があります。

let rec treeToString bintree = 
    match bintree with
    | EmptyTree -> "Empty" //Check if the tree is empty
    | Leaf x -> "Node" + x.ToString() //Returns "Node" and its value
    | Node(inner, left, right) when inner = 0 -> "Empty"
    | Node(inner, left, right) when inner <> 0 ->
        // Traverse the tree recursively
        treeToString left
        treeToString inner
        treeToString right
于 2012-11-25T14:49:23.483 に答える