H60.hs


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

import Tree
import H59

import Data.Maybe
import Data.List

hbalTreeNodes :: Int -> [Tree Char]
hbalTreeNodes 0 = [Empty]
hbalTreeNodes n = concatMap (filter ((==n).countNodes).hbalTree') [minH..maxH]
    where 
        -- Shenle
        minNodesSeq = 0:1:zipWith ((+).(1+)) minNodesSeq (tail minNodesSeq)
        
        minH = ceiling $ logBase 2 $ fromIntegral (n+1)
        maxH = (fromJust $ findIndex (>n) minNodesSeq) - 1
        countNodes Empty = 0
        countNodes (Branch _ t1 t2) = 1 + (countNodes t1) + (countNodes t2)