再帰的データ型(二分木)

さっそくデータ型を定義。大きさと深さを求める関数も定義。

# type 'a tree = Lf | Br of 'a * 'a tree * 'a tree;;
type 'a tree = Lf | Br of 'a * 'a tree * 'a tree
# let rec size = function
    Lf -> 0
  | Br (_, left, right) -> 1 + size left + size right;;
val size : 'a tree -> int = <fun>
# let rec depth = function
    Lf -> 0
  | Br (_, left, right) -> 1 + max (depth left) (depth right);;
val depth : 'a tree -> int = <fun>
# let tree = Br (1, Br (2, Br (4, Lf, Lf),
                           Br (5, Lf, Lf)),
                    Br (3, Br (6, Lf, Lf),
                           Br (7, Lf, Lf)));;
val tree : int tree =
  Br (1, Br (2, Br (4, Lf, Lf), Br (5, Lf, Lf)),
   Br (3, Br (6, Lf, Lf), Br (7, Lf, Lf)))
# size tree;;
- : int = 7
# depth tree;;
- : int = 3

このような木を生成する関数を書いてみる。

# let rec comptree x = function
    0 -> Lf
  | n -> Br (x, comptree x (n-1), comptree x (n-1));;
val comptree : 'a -> int -> 'a tree = <fun>
# comptree 'a' 3;;
- : char tree =
Br ('a', Br ('a', Br ('a', Lf, Lf), Br ('a', Lf, Lf)),
 Br ('a', Br ('a', Lf, Lf), Br ('a', Lf, Lf)))
# let comptree' n =
    let rec get_tree x = function
      0 -> Lf
    | n -> Br (x, get_tree (2*x) (n-1), get_tree (2*x+1) (n-1))
    in
    get_tree 1 n;;
val comptree' : int -> int tree = <fun>
# comptree' 3;;
- : int tree =
Br (1, Br (2, Br (4, Lf, Lf), Br (5, Lf, Lf)),
 Br (3, Br (6, Lf, Lf), Br (7, Lf, Lf)))

二分木の要素を列挙する関数

# let tree = comptree' 3;;
val tree : int tree =
  Br (1, Br (2, Br (4, Lf, Lf), Br (5, Lf, Lf)),
   Br (3, Br (6, Lf, Lf), Br (7, Lf, Lf)))
# let preorder tree = 
    let rec preord t l =
      match t with
        Lf -> l
      | Br (x, left, right) -> x :: (preord left (preord right l))
    in
    preord tree [];;
val preorder : 'a tree -> 'a list = <fun>
# preorder tree;;
- : int list = [1; 2; 4; 5; 3; 6; 7]
# let inorder tree = 
    let rec inord t l =
      match t with
        Lf -> l
      | Br (x, left, right) -> inord left (x :: inord right l)
    in
    inord tree [];;
val inorder : 'a tree -> 'a list = <fun>
# inorder tree;;
- : int list = [4; 2; 5; 1; 6; 3; 7]
# let postorder tree =
    let rec postord t l =
      match t with
        Lf -> l
      | Br (x, left, right) -> postord left (postord right (x :: l))
    in postord tree [];;
val postorder : 'a tree -> 'a list = <fun>
# postorder tree;;
- : int list = [4; 5; 2; 6; 7; 3; 1]

二分木を左右反転させる関数

# let rec reflect = function
      Lf -> Lf
    | Br (x, left, right) -> Br (x, reflect right, reflect left);;
val reflect : 'a tree -> 'a tree = <fun>
# reflect tree;;
- : int tree =
Br (1, Br (3, Br (7, Lf, Lf), Br (6, Lf, Lf)),
 Br (2, Br (5, Lf, Lf), Br (4, Lf, Lf)))
# preorder (reflect tree);;
- : int list = [1; 3; 7; 6; 2; 5; 4]
# inorder (reflect tree);;
- : int list = [7; 3; 6; 1; 5; 2; 4]
# postorder (reflect tree);;
- : int list = [7; 6; 3; 5; 4; 2; 1]

これらより、以下が導かれる。

• preorder (reflect tree) = reverse (postorder tree)
• inorder (reflect tree) = reverse (inorder tree)
• postorder (reflect tree) = reverse (preorder tree)