CODEWITHSUNDEEP
haskellbinary-tree
aanrv
aanrv

Reputation: 2241

Displaying binary tree in Haskell

data BinTree a = Empty | Node a (BinTree a) (BinTree a)
    deriving (Show)

I'm trying to figure out a way to display a binary tree in a manner such that for each level I go down in the tree, I want to add an additional * next to the name of the node and have them all separated by \n.

For example:

let x = Node "Parent" (Node "childLeft" (Node "grandChildLeftLeft" Emp Emp) Emp) (Node "childRight" Emp Emp)
putStrLn $ displayTree x

should return:

"Parent"
*"childLeft"
**"grandChildLeftLeft"
*"childRight"

My function (only prints up to one *):

displayTree :: Show a => BinTree a -> String
displayTree Emp = ""
displayTree (Node head Emp Emp) = (show head)
displayTree (Node head left Emp) = (show head) ++ "\n*" ++ displayTree left
displayTree (Node head Emp right) = (show head) ++ "\n*" ++ displayTree right
displayTree (Node head left right) = (show head) ++ "\n*" ++ displayTree left ++ "\n*" ++ displayTree right

My displayTree function would print: 

"Parent"
*"childLeft"
*"grandChildLeftLeft"
*"childRight"

I want "grandChildLeftLeft" to have ** next to it instead of just *.

Any suggestions?

NOTE: I don't want to change the parameters that are passed into the function, so it should stay as displayTree :: Show a => BinTree a -> String

Upvotes: 1

Views: 1337

Answers (2)

kvanbere
kvanbere

Reputation: 3352

I think this is what you want:

module Main (main) where

data BinTree a = Empty | Node a (BinTree a) (BinTree a)
    deriving (Show)

showTree :: Show a => BinTree a -> Int -> String
showTree (Empty) _ = []
showTree (Node t l r) n = replicate n '*' ++ show t ++ "\n" ++ showTree l (n+1) ++ showTree r (n+1)

main :: IO ()
main = do
    let x = Node "Parent" (Node "childLeft" (Node "grandChildLeftLeft" Empty Empty) Empty) (Node "childRight" Empty Empty)
    putStrLn $ showTree x 0

Note the accumulator n which changes the indent level with each recursive call.

http://ideone.com/lphCoV

"Parent"
*"childLeft"
**"grandChildLeftLeft"
*"childRight"

Upvotes: 3

cactus1
cactus1

Reputation: 629

Why not pass in the depth to the displayTree function?

displayTree :: Show a => BinTree a -> String 
displayTree = displayTree' ""

displayTree' str Emp = ""
displayTree' str (Node head Emp Emp) = str ++ (show head)
displayTree' str (Node head left Emp) = str ++ (show head) ++ "\n" ++ displayTree' (str ++ "*") left
displayTree' str (Node head Emp right) = str ++ (show head) ++ "\n" ++ displayTree' (str ++ "*") right
displayTree' str (Node head left right) = str ++ (show head) ++ "\n" ++ displayTree' (str ++ "*") left ++ "\n" ++ displayTree (str ++ "*") right

Also, here's it refactored to be kinda more readable: 

displayTree :: Show a => BinTree a -> String 
displayTree = displayTree' ""

displayTree' str Empty = ""
displayTree' str (Node h l r) = hstr ++ lstr ++ rstr
    where
        hstr = str ++ (show head) ++ "\n"
        lstr = makeTreeStr l
        rstr = makeTreeStr r
        makeTreeStr Empty = ""
        makeTreeStr tree = displayTree' (str ++ "*") tree ++ "\n"

Upvotes: 0

Related Questions