在 F# 中查找树中最左边的节点

Question

该函数的目标是找到并return树中最左边节点的值：

type btree = Empty | Node of btree * int * btree

type finding = NotFound | Found of int

let s = Node (Node(Empty, 5, Empty), 3, Node (Empty, 6, Empty))
(*
     (3)
    /   \
  (5)    (6)
  / \    / \
 () () ()  ()

                *)

let rec leftmost t =
    match t with
    Node (t, _, _) -> leftmost t
    | _ -> failwith "Empty"


let n = leftmost s
printfn "Found %i" n

这就是我目前的代码。它每次都会运行进入空树错误。我是 F# 的新手，当我找到最左边的节点时，我很难弄清楚如何实现这种情况。我最初的想法是

   | (Empty, t, _) -> t

但我没有找到任何成功，我们将不胜感激。谢谢

Answer 1

你快到了。 | (Empty, ) 后卫的想法很好。如果应用在正确的位置，它会起作用：

let rec leftmost t =
    match t with
    Node(Empty, n, _) -> n
    | Node (t, _, _) -> leftmost t
    | _ -> failwith "Empty"

重要的是，一旦下一个左子节点是 Empty，我们需要在当前节点 t 和 return 其有效载荷 n 处停止。

为了完整性：我建议将左子树命名为与当前根不同的名称并对齐大小写：

let rec leftmost t =
    match t with
    | Node(Empty, n, _) -> n
    | Node (l, _, _) -> leftmost l
    | _ -> failwith "Empty"

此外，let f x = match x with | P 有一个快捷方式：let f = function | P，这样就无需为参数命名：

let rec leftmost = function
    | Node(Empty, n, _) -> n
    | Node (l, _, _) -> leftmost l
    | _ -> failwith "Empty"

在 F# 中查找树中最左边的节点

Finding the leftmost node in a tree in F#

f#

binary-tree