Objective Caml 入門 手習い（6章）その2

バリアント型の肩慣らしに入りました。

• Objective Caml 入門

Exercise 4

問題

Exercise4 深さ n で全てのノードのラベルが x であるような 完全二分木を生成する関数comptree x n を定義せよ．

自分の答え

type 'a tree = Lf | Br of 'a * 'a tree * 'a tree;;

let rec comptree x n =
  match n with
  | n when n < 0 -> Br (x, Lf, Lf)
  | 0 -> Br (x, Lf, Lf)
  | _ -> Br (x, comptree x (n-1), comptree x (n-1))
;;

Exercise 5

問題

Exercise5 preord と同様な方法で，通りがけ順，帰りがけ順に列挙する関数 inord, postord を定義せよ．

自分の答え

let comptree = 
  Br(1, Br(2, Br(4, Lf, Lf),
              Br(5, Lf, Lf)),
        Br(3, Br(6, Lf, Lf),
              Br(7, Lf, Lf)));;  

let rec preorder = function
  | Lf -> []
  | Br (x, left, right) -> x :: (preorder left) @ (preorder right)
;;

let rec inorder = function
  | Lf -> []
  | Br (x, left, right) -> (inorder left) @ (x :: inorder right)
;;

let rec postorder = function
  | Lf -> []
  | Br (x, left, right) -> (postorder left) @ (postorder right) @ [x]
;;

let rec preord t l =
  match t with
  | Lf -> l
  | Br (x, left, right) -> x :: (preord left (preord right l))
;;

let rec inord t l =
  match t with
  | Lf -> l
  | Br (x, left, right) -> inord left (x :: inord right l)
;;

let rec postord t l =
  match t with
  | Lf -> l
  | Br (x, left, right) -> postord left (postord right (x::l))
;;

Exercise 6

問題

Exercise6 二分木の左右を反転させた木を返す関数 reflect を定義せよ．

自分の答え

let rec reflect = function
  | Lf -> Lf
  | Br (x, left, right) -> Br (x, reflect right, reflect left)
;;