以特殊的方式遍歷樹

Question

我們有一個二叉樹

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

我們要返回包含特定的順序所有頂點的'a list，即在列表中的兩個相鄰頂點之間的距離不得超過3每個頂點只能出現一次。

例子。對於樹

 1 
    /\ 
    2 6 
/
    3 
/\ 
4 5 

一個可能的答案是[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定義中使用這些組合程序和後處理的pom_walk結果使用to_list返回一個更傳統的'a 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 []