如何在F＃中实现二叉搜索树的添加操作？

Question

我正在尝试实现来自《算法 第四版》的以下代码：

private Node put(Node x, Key key, Value val)
{
    if (x == null) return new Node(key, val, 1);
    int cmp = key.compareTo(x.key);
    if (cmp < 0) x.left = put(x.left, key, val);
    else if (cmp > 0) x.right = put(x.right, key, val);
    else x.val = val;
    x.N = size(x.left) + size(x.right) + 1;
    return x;
}

我已经想出了以下的F#实现：

我已经想出了以下的F#实现：

type Node = {
                mutable Left : Node option
                mutable Right : Node option
                mutable Value : int
                mutable Count : int
            }

type BST() =
    let root : Node option = None

    member x.Put (value : int) =
        let rec Add (node:Node option) value =
            match node with 
            | None -> Some { Left = None; Right = None; Value = value; Count = 1 }
            | Some t -> 
                match t with
                | _ when t.Value < value ->  t.Right <- Add t.Right value
                | _ when t.Value > value -> t.Left <- Add t.Left value
                | _ -> 
                        t.Value <- value
                        t.Count <- (x.Size t.Left) + (x.Size t.Right) + 1
                        Some t
        ()

我遇到了错误：在以下行中，预期类型为Node option，但此处为unit：

| _ when t.Value < value ->  t.Right <- Add t.Right value
| _ when t.Value > value -> t.Left <- Add t.Left value

有没有更好的方法来实现上面的代码？如果直接将过程式风格的代码复制到函数式代码中，会犯错吗？

- Pawan Mishra

---

使用一个带有区分联合类型可能比使用记录类型更简单；请参考一些初步的草图。 - Sehnsucht

Answer 1

你之所以会出现这个错误，是因为 None 匹配返回了 Some Node，所以你必须在所有其他分支中匹配该返回类型。

你可以通过在匹配节点后返回节点来解决这个问题：

let rec Add (node:Node option) value =
    match node with 
    | None -> Some { Left = None; Right = None; Value = value; Count = 1 }
    | Some t -> 
        match t with
        | _ when t.Value < value ->
            t.Right <- Add t.Right value
            Some t
        | _ when t.Value > value ->
            t.Left <- Add t.Left value
            Some t
        | _ ->
            t.Value <- value
            //t.Count <- (x.Size t.Left) + (x.Size t.Right) + 1
            Some t

你可能注意到我注释掉了倒数第二行，因为x没有Size成员。

引用： 我把过程式风格的代码无脑复制到函数式代码里是否有错呢？ 答案是：很可能有。这取决于你的目标是什么。如果你想学习F#的语法，那么它可能是一个不错的练习。不过如果你想学习函数式编程，这样做就没有意义了。

- Mark Seemann