バリアント型の肩慣らしに入りました。
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) ;;