二分木を作ってみる

そういえば、二分木を探索するコードは書いたことがあったけど、二分木を作るコードは書いた記憶がなかったなぁ、と思いやってみることにしました。

いつもはWebの情報とかを参考にしがちなんだけど、脳に汗を書かせたい気分なので自力で頑張るぞ、と。

type 'a t = Lf | Br of 'a * 'a t * 'a t

let rec set v = function
  | Lf -> Br(v, Lf, Lf)
  | Br(orig, left, right) ->
      if v < orig
        then Br(orig, (set v left), right)
        else Br(orig, left, (set v right))

let _ =
  let sample = [5; 2; 7; 1; 8; 3; 6; 4] in
  List.fold_left (fun t i -> set i t) Lf sample

お、なんかすっきりかけた。二分木をダンプするコード書くのめんどいので…

mitsu@garlic$ ocaml
        Objective Caml version 3.10.2

# #use "tree.ml";;
type 'a t = Lf | Br of 'a * 'a t * 'a t
val set : 'a -> 'a t -> 'a t = <fun>
- : int t =
Br (5, Br (2, Br (1, Lf, Lf), Br (3, Lf, Br (4, Lf, Lf))),
 Br (7, Br (6, Lf, Lf), Br (8, Lf, Lf)))
#

それらしく出来てる！やったぁ。