Зеркальное изображение двоичного дерева OCaml

Question

Я изучаю OCaml для класса, и мне дали задание вычислить зеркальное отображение двоичного дерева. Я застрял и не уверен, как начать...

type btree = Empty | Node of int * btree * btree
;;

let mirror : btree -> btree
  = fun t -> (* Code *)

Пример ввода:

let tree1 = Node(1, Node(2, Node(3, Empty, Empty), Empty), Node(4, Empty, Empty))
;;

Образец вывода:

mirror tree1 = Node(1, Node(4, Empty, Empty), Node(2, Empty, Node(3, Empty, Empty)))
;;

Answer 1

Использовать match особенность.

Вы можете match на структуре значения, как это определено его типом. В вашем примере значение btree тип создается либо с Empty конструктор или конструктор кортежей Node of int * btree * btree, Вы должны получить что-то вроде этого:

...
match t with
| Node (num, lt, rt) -> (* do something to switch the subtrees, and mirror the subtrees themselves *)
| Empty -> (* do nothing *)
...

и так как mirror функция имеет тип btree -> btreeкаждый из ваших совпадений должен возвращать правильное значение типа btree,

Смотрите: http://ocaml.org/learn/tutorials/data_types_and_matching.html