module BinTree

where

inTree :: (Ord a,Show a) => a -> BinTree a -> Bool

addTree :: (Ord a,Show a) => a -> BinTree a -> BinTree a

delTree :: (Ord a,Show a) => a -> BinTree a -> BinTree a

buildTree :: (Ord a,Show a) => [a] -> BinTree a

inorder :: (Ord a,Show a) => BinTree a -> [a]

data (Ord a) => BinTree a = EmptyBT

| NodeBT a (BinTree a) (BinTree a)

deriving Show

emptyTree = EmptyBT

inTree v' EmptyBT = False

inTree v' (NodeBT v lf rt) | v==v' = True

| v'<v = inTree v' lf

| v'>v = inTree v' rt

addTree v' EmptyBT = NodeBT v' EmptyBT EmptyBT

addTree v' (NodeBT v lf rt) | v'==v = NodeBT v lf rt

| v' < v = NodeBT v (addTree v' lf) rt

| otherwise = NodeBT v lf (addTree v' rt)

buildTree lf = foldr addTree EmptyBT lf

-- value not found

delTree v' EmptyBT = EmptyBT

-- one descendant

delTree v' (NodeBT v lf EmptyBT) | v'==v = lf

delTree v' (NodeBT v EmptyBT rt) | v'==v = rt

-- two descendants

delTree v' (NodeBT v lf rt)

| v'<v = NodeBT v (delTree v' lf) rt

| v'>v = NodeBT v lf (delTree v' rt)

| v'==v = let k = minTree rt

in NodeBT k lf (delTree k rt)

minTree (NodeBT v EmptyBT _) = v

minTree (NodeBT _ lf _) = minTree lf

inorder EmptyBT = []

inorder (NodeBT v lf rt) = inorder lf ++ [v] ++ inorder rt