練習問題 6.5

深さ n ですべてのノードのラベルが x であるような完全二分木を生成する関数 comptree x n を定義しなさい。次に、ノードのラベルとして、根が 1 で、次の子は右から 2、3、次の深さには 4、5、6、7 と、各深さに連続した数字が並んでいるような完全二分木を生成する関数 comptree’ n を定義しなさい。

解答

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

let rec comptree x n =
  if n = 0 then Lf
  else Br (x, (comptree x (n-1)), (comptree x (n-1)));;

実行例

# 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 comptree_in x n =
    if n = 0 then Lf
    else Br (x, (comptree_in (x * 2 + 1) (n-1)), (comptree_in (x * 2) (n-1)))
  in 
  comptree_in 1 n;;

実行例

# comptree' 1;;
- : int tree = Br(1, Lf, Lf)
# comptree' 2;;
- : int tree = Br(1, Br(3, Lf, Lf), Br(2, Lf, Lf))
# comptree' 3;;
- : int tree = Br(1, Br(3, Br(7, Lf, Lf), Br(6, Lf, Lf)),
             Br(2, Br(5, Lf,Lf), Br(4, Lf, Lf)))

Tweet