Created
January 20, 2011 02:58
-
-
Save wavebeem/787316 to your computer and use it in GitHub Desktop.
Haskell binary search tree
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
module BST where | |
-- Define the BST data type | |
data BST a | |
= Node (BST a) (BST a) a | |
| Tip | |
deriving (Show, Eq) | |
-- Make a leaf node | |
leaf y = Node Tip Tip y | |
-- Adding a node to a BST | |
add Tip y = leaf y | |
add (Node left right x) y = | |
if y < x | |
then Node (add left y) right x | |
else Node left (add right y) x | |
-- Build a tree from a list | |
build xs = build' Tip xs | |
where | |
build' tree [] = tree | |
build' tree (x:xs) = build' (add tree x) xs | |
preOrd Tip = "" | |
preOrd (Node left right x) = | |
show x ++ " => " ++ preOrd left ++ preOrd right | |
inOrd Tip = "" | |
inOrd (Node left right x) = | |
inOrd left ++ show x ++ " => " ++ inOrd right | |
postOrd Tip = "" | |
postOrd (Node left right x) = | |
postOrd left ++ postOrd right ++ show x ++ " => " |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment