Haskell traverse tree inorder preorder postorder
I have the following Haskell data definition:
data Tree = Leaf Int | Node Int Tree Tree deriving Show
and I wrote the following programs to traverse trees preorder, inorder and postorder:
preorder(Leaf n) = n
preorder(Node n t0 t1) = [n] ++ preorder t0 ++ preorder t1
inorder(Leaf n) = n
inorder(Node n t0 t1) = inorder t0 ++ [n] ++ inorder t1
postorder(Leaf n) = n
po开发者_如何转开发storder(Node n t0 t1) = postorder t0 ++ postorder t1 ++ [n]
The error that I get is:
- Type error in application
*** Expression : preorder t0 ++ preorder t1
*** Term : preorder t1
*** Type : Int
*** Does not match : [a]
I need to return a list that contains all tree integers in appropriate order. Any help is highly appreciated as I am new to Haskell.
You're returning Int
from the base case but [Int]
from the constructive case. The leaves should be lists too.
The error is:
preorder(Leaf n) = n
Should be:
preorder(Leaf n) = [n]
And same for inorder and postorder.
Changing the functions fixes the error, but you can only insert elements in pairs into your Tree
.
Better change it to:
data Tree = Leaf | Branch Int Tree Tree deriving Show
inorder Leaf = []
inorder (Branch n left right) = inorder left ++ [n] ++ inorder right
-- etc.
Nice page to check out algorithm implementations in different languages is Rosetta Code which has a page on Tree traversals including in Haskell.
精彩评论