Created
January 18, 2011 05:43
-
-
Save wavebeem/784028 to your computer and use it in GitHub Desktop.
BST
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 Main 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 right (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