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

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

```# 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)