OCaml 将函数数组作为二叉树转换为列表

Question

我必须将函数数组转换为 OCaml 上的列表，这是我到目前为止所拥有的，但它没有通过测试，任何人都可以帮助解决我的代码有什么问题以及我应该使用什么方法吗？

我首先编写了一个函数来返回除第一个值之外的树，然后取出头并将其连接到其余部分的头以创建一个列表。我是不是搞错了？

exception Subscript

let top = function
  | Lf -> raise Subscript
  | Br (v,_,_) -> v

let rec pop = function
  | Lf -> raise Subscript
  | Br (_, Lf, Lf) -> Lf
  | Br (_, lt, rt) -> Br (top lt, rt, pop lt)

let rec listofarray = function
  | Br (v, t1, t2) -> v :: (listofarray (pop (Br(v, t1, t2))))
  | Lf -> []

Answer 1

正如 Jeffrey Scofield 所建议的，您可能希望修改

pop

的实现，以处理左树或右树是

Lf

但不是 两者都的情况。

let rec pop = function
  | Lf -> raise Subscript
  | Br (_, Lf, Lf) -> Lf
  | Br (_, Lf, rt) -> ...
  | Br (_, lt, Lf) -> ...
  | Br (_, lt, rt) -> Br (top lt, rt, pop lt)

现在的问题是

pop

在每种情况下应该做什么。考虑第一个场景。

   0
  / \
 /   \
Lf    1
     / \
    /   \
   Lf   Lf

看起来相当明显，在

pop

之后我们应该：

   1
  / \
 /   \
Lf   Lf

我们可以通过简单地返回正确的树来得到这个。

let rec pop = function
  | Lf -> raise Subscript
  | Br (_, Lf, Lf) -> Lf
  | Br (_, Lf, rt) -> rt
  | Br (_, lt, Lf) -> ...
  | Br (_, lt, rt) -> Br (top lt, rt, pop lt)

同样，如果我们考虑其他场景，我们可以看到解决方案也同样简单。

         0              1
        / \            / \ 
       /   \          /   \
      1    Lf   ->   Lf   Lf
     / \
    /   \
   Lf   Lf

我们可以通过返回左树来实现这一点。

let rec pop = function
  | Lf -> raise Subscript
  | Br (_, Lf, Lf) -> Lf
  | Br (_, Lf, rt) -> rt
  | Br (_, lt, Lf) -> lt
  | Br (_, lt, rt) -> Br (top lt, rt, pop lt)

现在，在不改变

listofarray

的情况下，我们在评估 Jeffrey Scofield 提供的示例时确实得到了正确的结果。

utop # listofarray (Br (0, Lf, Br (1, Lf, Lf)));;
- : int list = [0; 1]
utop # listofarray (Br (0, Br (1, Lf, Lf), Lf));;
- : int list = [0; 1]

Answer 2

你没有说树是否有额外的不变量。除非对可能的树有限制，否则您的

pop

函数并不适用于所有树：

# pop (Br (0, Br (1, Lf, Lf), Lf));;
- : tree = Br (1, Lf, Lf)
# pop (Br (0, Lf, Br (1, Lf, Lf)));;
Exception: Subscript.