以特殊方式遍历树

Question

我们有一个二叉树

type 'a tree = Node of 'a * 'a tree * 'a tree | Null ;;

我们想要return一个'a list包含特定顺序的所有顶点，即列表中两个相邻顶点之间的距离不能超过3。每个顶点只能出现一次。

例子。对于树

一个可能的答案是 [1; 3; 4; 5; 2; 6]

暂时我有以下代码：

let walk t =
    let rec pom_walk t acc end_root = (* it's symmetric, so it could be start_root and the result would be correct too *)
        match t with
        | Null -> acc
        | Node (nr, l, r) ->
            if end_root then
                nr::(pom_walk r (pom_walk l acc false) false)
            else
                (pom_walk r (pom_walk l acc true) true) @ [nr]
     in
        pom_walk t [] true

但是由于使用了本身是线性的 @ 运算符，此代码具有平方复杂度。

如何在线性时间内解决这个问题？

Answer 1

因为您将元素推到列表的前面和后面，所以能够轻松地执行这两个操作会很好。正如@david-eisenstat 所建议的，您可以使用 difference lists.

我在这里提出一个不同的解决方案。我们将用两个列表表示我们的列表：一个初始段和一个（反向）结束段。

type 'a init_last = 'a list * 'a list

我们可以通过给出一个函数 to_list 将这样的 'a init_last 转换为它表示的 'a list 来使这种直觉更正式：

let to_list (xs : 'a init_last) : 'a list =
  let (init, last) = xs in init @ rev last

现在很容易定义辅助函数，定义空 'a init_last 的样子，并在恒定时间内将项目推到我们的 'a init_last 表示的列表的顶部/末尾：

let empty : 'a init_last = ([], [])

let push_top (a : 'a) (xs : 'a init_last) : 'a init_last =
  let (init, last) = xs in (a :: init, last)

let push_end (xs : 'a init_last) (a : 'a) : 'a init_last =
  let (init, last) = xs in (init, a :: last)

然后我们可以在您定义的 walk 和 return 中使用这些组合子，通过 post 处理更常规的 'a list - 处理 pom_walk 的结果使用 to_list:

let walk t =
    let rec pom_walk t acc end_root =
        match t with
        | Null -> acc
        | Node (nr, l, r) ->
            if end_root then
                push_top nr (pom_walk r (pom_walk l acc false) false)
            else
                push_end (pom_walk r (pom_walk l acc true) true) nr
     in
        to_list (pom_walk t empty true)

Answer 2

@gallais 展示了一个很好的解决方案，我想分享我想出的那个。请仔细检查，直到没有剩下;)

let walk t =
    let rec pom_walk t cont end_root =
        match t with
        | Null -> cont
        | Node (nr, l, r) ->
            let resL = pom_walk l cont (not end_root) in
            let resR = pom_walk r resL (not end_root) in
                if end_root then
                    function res -> nr::(resR res)
                else
                    function res -> resR (nr::res)
     in
        pom_walk t (fun x -> x) true []

以特殊方式遍历树

Traversing a tree in a special way

algorithm

ocaml