I am trying to learn Haskell. As an exercise, I wrote a
function to create a binary tree in level-order. I am attaching
the code. I am sure there are a number of places where
the code could be improved. Could you please point these out?
Thanks,
Philip
------------------------------------------------------------------------------
BinTree.lhs : Implementation of a binary tree. createTree
accepts a sequence and builds a binary tree in level-order.
------------------------------------------------------------------------------
>module BinTree where
------------------------------------------------------------------------------
A binary tree either
1. is empty, or
2. consists of three distinct binary trees : a root node, a left
subtree, and a right subtree.
------------------------------------------------------------------------------
>data Tree a = Empty | Tree {rootNode::a, left::(Tree a),
right::(Tree a)} deriving (Eq, Show)
------------------------------------------------------------------------------
Count the number of nodes in a binary tree, using the simple
recursive definition of the count.
------------------------------------------------------------------------------
>countNodes :: Tree a -> Integer
>countNodes Empty = 0
>countNodes (Tree rootNode left right) = 1 + countNodes left
+ countNodes right
------------------------------------------------------------------------------
Insert a single element into the proper place in the tree, as
per level-order.
------------------------------------------------------------------------------
>insert :: Eq a => Tree a -> a -> Tree a
>insert tree x = if tree == Empty
> then Tree x Empty Empty
> else if (left tree) == Empty
> then Tree (rootNode tree) (Tree x Empty Empty) (right tree)
> else if (right tree) == Empty
> then Tree (rootNode tree) (left tree) (Tree x Empty Empty)
> else if countNodes (left tree) <= countNodes (right tree)
> then Tree (rootNode tree) (insert (left tree) x) (right tree)
> else Tree (rootNode tree) (left tree) (insert (right tree) x)
------------------------------------------------------------------------------
Use insert to create a tree from a sequence.
------------------------------------------------------------------------------
>createTree :: Eq a => [a] -> Tree a
>createTree [] = Empty
>createTree (x:xs) = foldl insert (insert Empty x) xs
