3

我目前正在 F# 中构建我的二叉树，我快完成了。我正在完成这项任务的最后一项任务，我应该在其中制作二叉树的字符串表示形式。这意味着树应该像这样呈现：

示例：("node" "value" ("node" "value" "Empty" "Empty") Empty)<- 具有根节点的树，该树具有一个左子树，一个节点具有两个空子树和一个空右子树。

我的树看起来像这样：

 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

我的方法只返回一个值，所以我的解决方案的实际问题是让递归部分正确。

所以我的问题是：我在这里做错了什么？

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 回答