F# 为二叉搜索树制作 ToString 方法

Question

我目前正在用 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

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

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

Answer 1

并集 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 等一起工作。