Магический код для обхода двоичного дерева уровня - что происходит?

Question

У нас есть определение бинарного дерева:

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

а также полезную функцию для обхода дерева»

let rec fold_tree f a t = 
    match t with 
    | Null -> a 
    | Node (l, x, r) -> f x (fold_tree f a l) (fold_tree f a r);; 

А вот„функция магии“, который, когда дано бинарное дерево, возвращает список, в котором у нас есть списки элементов на определенных уровнях, например, когда дано дерево:

tree http://lcm.csa.iisc.ernet.in/dsa/img151.gif

функция возвращает [[1]; [2; 3]; [4; 5; 6; 7]; [8; 9]].

let levels tree = 
    let aux x fl fp = 
    fun l -> 
    match l with 
    | [] -> [x] :: (fl (fp [])) 
    | h :: t -> (x :: h) :: (fl (fp t)) 
    in fold_tree aux (fun x -> x) tree [];; 

И, по-видимому, это работает, но я не могу обдумать его. Может ли кто-нибудь просто объяснить, что происходит? Почему эта функция работает?

Answer 1

Как вы совмещаете два списка слоев из двух поддеревьев и получаете список слоев дерева педерастов? Предположим, что у вас есть это дерево

a 
/\ 
x y 

где x и y произвольные деревья, и у них есть свои списки слоев, как [[x00,x01,...],[x10,x11,...],...] и [[y00,y01,...],[y10,y11,...],...] соответственно.

Список слоев нового дерева будет [[a],[x00,x01,...]++[y00,y01,...],[x10,x11,...]++[y10,y11,...],...]. Как эта функция создает его?

Давайте посмотрим на это определение

let rec fold_tree f a t = ... 

и посмотреть, какие аргументы мы переходим к fold_tree в нашем определении levels.

... in fold_tree aux (fun x -> x) tree [] 

Итак, первый аргумент, aux, является своего рода длинной и сложной функции. Мы вернемся к нему позже.

Второй аргумент также является функцией - функцией тождества. Это означает, что fold_tree также вернет функцию, потому что fold_tree всегда возвращает тот же тип значения, что и его второй аргумент. Мы будем утверждать, что функция fold_tree, примененная к этому набору аргументов, принимает список слоев и добавляет к ней слои данного дерева.

Третий аргумент - наше дерево.

Подождите, что является четвертым аргументом? fold_tree только должно получить дерево? Да, но поскольку он возвращает функцию (см. Выше), эта функция применяется к этому четвертому аргументу, пустой список.

Итак, давайте вернемся к aux. Эта функция aux принимает три аргумента. Один из них - это элемент дерева, а два других - это результаты складки поддеревьев, то есть то, что возвращается fold_tree. В нашем случае эти две вещи являются функциями снова.

So aux получает элемент дерева и две функции и возвращает еще одну функцию. Какая функция такова?Он берет список слоев и добавляет к нему слои данного дерева. Как это происходит? Он добавляет корень дерева к первому элементу (который является верхним слоем) списка, а затем добавляет слои правого поддерева к хвосту списка (который является всеми слоями под вершиной), вызывая правая функция на нем, а затем добавляет слои левого поддерева к результату, вызывая левую функцию. Или, если входящий список пуст, это просто список слоев заново, применяя вышеуказанный шаг к пустым спискам.