fork download
copy 
  1. import Data.List
  2. import Control.Monad
  3.  
  4. -- Implementations for exercises 2.1, 2.4 and 2.5
  5.  
  6. data Tree a = Empty | Node a (Tree a) (Tree a) deriving (Show)
  7.  
  8. -- Ex 2.1
  9. recreateTree :: (Ord a, Eq a) =>  [a] -> [a] -> Tree a
  10. recreateTree []    []      = Empty
  11. recreateTree inord postord = Node root left right
  12.   where root  = last postord
  13.         left  = recreateTree leftInord leftPostord
  14.         right = recreateTree rightInord rightPostord  
  15.  
  16.         Just rootInd = elemIndex root inord
  17.         leftInord    = take rootInd inord
  18.         rightInord   = drop (rootInd+1) inord
  19.  
  20.         leftPostord  = take rootInd postord
  21.         rightPostord = init $ drop rootInd postord
  22.  
  23.  
  24. -- Ex 2.4
  25. buildBST :: (Ord a, Eq a) => [a] -> Tree a
  26. buildBST [] = Empty
  27. buildBST xs = Node root left right
  28.   where (root,len) = middle xs
  29.         left       = buildBST $ take len xs
  30.         right      = buildBST $ drop (len+1) xs
  31.  
  32. middle :: [a] -> (a,Int)
  33. middle [] = error "D:"
  34. middle xs = (xs !! half, half)
  35.   where half = (length xs) `div` 2
  36.  
  37.  
  38. -- Ex 2.5
  39. printLevelK :: (Show a) => Tree a -> Integer -> String
  40. printLevelK tree k = go tree k
  41.   where go Empty        _ = "Nil"
  42.         go (Node a l r) 0 = show a
  43.         go (Node a l r) k = go l (k-1) ++ "  " ++ go r (k-1)
  44.  
  45.  
  46. -- Tests
  47.  
  48. ino = [4,2,5,1,3,6]
  49. posto = [4,5,2,6,3,1]
  50.  
  51. bst20 = buildBST [1..20]
  52.  
  53. main = do putStrLn "Tree tests!"
  54.           putStrLn "-----------"
  55.           putStrLn "\nRecreating tree from inorder and postorder:"
  56.           putStrLn $ "inorder:   " ++ show ino
  57.           putStrLn $ "postorder: " ++ show posto
  58.           putStrLn $ "tree:      " ++ show (recreateTree ino posto)
  59.  
  60.           putStrLn "\nPrint each level of bst20:"
  61.           putStrLn "-----------"
  62.           mapM_ (putStrLn . printLevelK bst20) [0..height bst20]
  63.  
  64.  
  65.           --we can use printLevelK as a crappy prettyprinter :-D
  66.           --test with the previous tree:
  67.           putStrLn "\nPrint recreated tree level by level:"
  68.           putStrLn "-----------"
  69.           let tree = recreateTree ino posto
  70.           mapM_ (putStrLn . printLevelK tree) [0..height tree]
  71.  
  72. height :: Tree a -> Integer
  73. height Empty        = -1
  74. height (Node _ l r) = 1 + max (height l) (height r)
Success #stdin #stdout 0s 6288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Tree tests!
-----------

Recreating tree from inorder and postorder:
inorder:   [4,2,5,1,3,6]
postorder: [4,5,2,6,3,1]
tree:      Node 1 (Node 2 (Node 4 Empty Empty) (Node 5 Empty Empty)) (Node 3 Empty (Node 6 Empty Empty))

Print each level of bst20:
-----------
11
6  16
3  9  14  19
2  5  8  10  13  15  18  20
1  Nil  4  Nil  7  Nil  Nil  Nil  12  Nil  Nil  Nil  17  Nil  Nil  Nil

Print recreated tree level by level:
-----------
1
2  3
4  5  Nil  6
https://ideone.com/4nSGrk
language:
Haskell (ghc 8.4.4)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!