gpt4 book ai didi

.net - F#中如何实现二叉搜索树的add操作?

转载 作者:塔克拉玛干 更新时间:2023-11-03 03:13:53 26 4
gpt4 key购买 nike

我正在尝试实现来自 Algorithms 4th Edition 的以下代码

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# 中提出了以下实现:

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
()

我收到错误:预期有 type Node 选项,但这里作为单元,在以下几行中:

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

有没有更好的方法来实现上面的代码?复制函数式方法中的程序样式代码是否犯了错误?

最佳答案

您收到错误是因为 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 成员。)

Am I making a mistake by copying a procedural style code as it is in functional approach?

可能吧。这取决于你的目标是什么。如果您想学习 F# 的语法,这可能是一个很好的练习。如果你想学习函数式编程,那么这样做是没有意义的。

关于.net - F#中如何实现二叉搜索树的add操作?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/32800544/

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com