OCaml中将二叉树实现的函数式数组转换为列表的代码问题排查

现有代码的问题 #

你的实现思路大方向没有问题，核心错误出在pop函数的逻辑不符合Braun树（你所用的函数式数组底层的完全二叉树结构）的性质，导致元素顺序错乱：

• 你当前的pop函数没有判断左右子树的大小，强行将左子树的顶点作为新根、交换左右子树位置，会打乱Braun树「左子树大小等于右子树或比右子树大1」的规则，最终生成的列表元素顺序不符合预期。
• 额外的性能问题：每次pop复杂度为O(log n)，循环调用n次的总复杂度为O(n log n)，存在优化空间。

正确实现方案 #

方案1：保留原有思路，修正pop实现 #

首先补充Braun树的size函数，再修正pop逻辑即可：

exception Subscript

type 'a tree = Lf | Br of 'a * 'a tree * 'a tree

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

let rec size = function
  | Lf -> 0
  | Br (_, lt, rt) -> 1 + size lt + size rt

let rec pop = function
  | Lf -> raise Subscript
  | Br (_, Lf, Lf) -> Lf
  | Br (_, lt, rt) when size lt > size rt ->
      (* 左子树更大，取左子树顶点为新根，pop左子树 *)
      Br (top lt, pop lt, rt)
  | Br (_, lt, rt) ->
      (* 左右子树大小相等，取右子树顶点为新根，pop右子树 *)
      Br (top rt, lt, pop rt)

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

方案2：层序遍历直接生成列表（更优，O(n)复杂度） #

不需要依赖pop操作，直接对树做层序遍历，得到的结果就是函数式数组的顺序列表，实现简单且效率更高：

exception Subscript

type 'a tree = Lf | Br of 'a * 'a tree * 'a tree

let listofarray t =
  let rec aux queue = match queue with
    | [] -> []
    | Lf :: rest -> aux rest
    | Br(v, lt, rt) :: rest -> v :: aux (rest @ [lt; rt])
  in aux [t]

内容的提问来源于stack exchange，提问作者mimi