Haskell : Btree operations

data BT a = Leaf a
|Node (BT a) (BT a)
|Empty
deriving (Show,Eq)

— creating unbalanced tree from List
mkTree (x:y:xs) = Node (Node (Leaf x ) (Leaf y ) ) (mkTree xs)
mkTree [] = Empty
mkTree [x] = Node (Leaf x) Empty

split xs = go xs xs

go (x:xs) (_:_:ys) = (x:us,vs)
where (us,vs) = go xs ys

go xs _ = ([],xs)
–creating a balanced tree from list
mkBalancedTree xs = mkTree1 x y
where (x,y) = split xs

mkTree1 [] [] = Empty
mkTree1 [] [x] = Node Empty (Leaf x)
mkTree1 [x] [y] = Node (Leaf x) (Leaf y)

mkTree1 xs ys = Node (mkTree1 xs1 xs2) (mkTree1 ys1 ys2)
where ((xs1,xs2),(ys1,ys2)) = (split xs,split ys)

–mirror it
mirror (Node x y) = Node (mirror y) (mirror x)
mirror (Leaf a) = Leaf a

Advertisements
This entry was posted in Haskell and tagged , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s