如何在列表中添加树的节点？

Question

我想将树的节点按预序添加到列表中，而不连接列表。

type 'a bintree = Nil | BT of 'a bintree * 'a * 'a bintree
let preorder t = 
  let rec addpre t list = 
    match t with
    | Nil -> list
    | BT (left, v, right) -> addpre left (v :: list)
  in 
  addpre t [];;

let ab = BT (BT(Nil, 2, Nil),
             7,
             BT(BT(Nil, 5, Nil), 6, BT(Nil, 11, Nil)))
let r = preorder ab;;

如您所见，我知道如何从分支（左或右）添加节点，但我不知道如何从两个分支添加节点。你能帮我吗？

更新

我想我成功了

let preorder t = 
  let rec addpre t list = 
    match t with
    | Nil -> list
    | BT (left, v, right) -> v :: addpre left (addpre right list)
  in 
  addpre t [];;

是吗？

Answer 1

您可能想在计算完

countpree

后，再计算

right

到

left

。 将计算本地绑定到左侧部分可能会有所帮助。 类似于

| BT (left, v, right) -> 
      let leftpreoder = countpre left (v :: list) 
      in ...