32 lines
1,009 B
Haskell
32 lines
1,009 B
Haskell
data Tree a = Empty | Branch a (Tree a) (Tree a)
|
|
deriving (Show, Eq)
|
|
|
|
completeBinaryTreeNumbered :: Int -> Int -> Tree Int
|
|
completeBinaryTreeNumbered m n =
|
|
Branch m branch1 branch2
|
|
where
|
|
branch1 =
|
|
if 2 * m <= n
|
|
then completeBinaryTreeNumbered (2 * m) n
|
|
else Empty
|
|
branch2 =
|
|
if 2 * m + 1 <= n
|
|
then completeBinaryTreeNumbered (2 * m + 1) n
|
|
else Empty
|
|
|
|
useSameCharLabel :: Char -> Tree a -> Tree Char
|
|
useSameCharLabel _ Empty = Empty
|
|
useSameCharLabel c (Branch _ branch1 branch2) =
|
|
Branch c branch1' branch2'
|
|
where
|
|
branch1' = useSameCharLabel c branch1
|
|
branch2' = useSameCharLabel c branch2
|
|
|
|
completeBinaryTree :: Int -> Tree Char
|
|
completeBinaryTree n = useSameCharLabel 'x' $ completeBinaryTreeNumbered 1 n
|
|
|
|
isCompleteBinaryTree :: Tree a -> Bool
|
|
isCompleteBinaryTree Empty = True
|
|
isCompleteBinaryTree (Branch _ _ Empty) = True
|
|
isCompleteBinaryTree (Branch _ branch1 branch2) =
|
|
isCompleteBinaryTree branch1 && isCompleteBinaryTree branch2
|