обходе дерева специальным образом

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 и возвращаем более обычные '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 []