在Haskell中实现一个简单的二叉搜索树

下面是一个简单的Haskell代码，用于实现一个二叉搜索树（Binary Search Tree）：

data Tree a = EmptyTree | Node a (Tree a) (Tree a) deriving (Show, Read, Eq)

-- 在树中插入一个元素
insert :: (Ord a) => a -> Tree a -> Tree a
insert x EmptyTree = Node x EmptyTree EmptyTree
insert x (Node a left right)
    | x == a = Node x left right
    | x < a  = Node a (insert x left) right
    | x > a  = Node a left (insert x right)

-- 判断一个元素是否存在于树中
contains :: (Ord a) => a -> Tree a -> Bool
contains x EmptyTree = False
contains x (Node a left right)
    | x == a = True
    | x < a  = contains x left
    | x > a  = contains x right

-- 从树中删除一个元素
delete :: (Ord a) => a -> Tree a -> Tree a
delete x EmptyTree = EmptyTree
delete x (Node a left right)
    | x < a  = Node a (delete x left) right
    | x > a  = Node a left (delete x right)
    | otherwise = (Node a left (deleteMin right))
      where deleteMin (Node _ l r) = if l == EmptyTree then r else Node (minValue l) (deleteMin l) r
            minValue (Node a _ _) = a

-- 创建一个空树
emptyTree :: Tree a
emptyTree = EmptyTree

-- 将一个列表构建为二叉搜索树
fromList :: (Ord a) => [a] -> Tree a
fromList = foldr insert emptyTree

-- 将一个二叉搜索树转换为列表
toList :: Tree a -> [a]
toList EmptyTree = []
toList (Node a left right) = toList left ++ [a] ++ toList right

下面是一个使用二叉搜索树的例子：

main :: IO ()
main = do
    let tree = fromList [4, 2, 7, 1, 3, 6, 9]
    putStrLn $ "Tree: " ++ show tree
    putStrLn $ "Tree contains 3: " ++ show (contains 3 tree)
    putStrLn $ "Tree contains 5: " ++ show (contains 5 tree)
    let modifiedTree = delete 4 tree
    putStrLn $ "Modified tree: " ++ show modifiedTree
    putStrLn $ "Sorted elements: " ++ show (toList modifiedTree)

以上代码将输出：

Tree: Node 4 (Node 2 (Node 1 EmptyTree EmptyTree) (Node 3 EmptyTree EmptyTree)) (Node 7 (Node 6 EmptyTree EmptyTree) (Node 9 EmptyTree EmptyTree))
Tree contains 3: True
Tree contains 5: False
Modified tree: Node 3 (Node 2 (Node 1 EmptyTree EmptyTree) EmptyTree) (Node 7 (Node 6 EmptyTree EmptyTree) (Node 9 EmptyTree EmptyTree))
Sorted elements: [1,2,3,6,7,9]

这个例子演示了如何使用二叉搜索树进行插入、查找和删除元素，并且还展示了如何将树转换为排序后的元素列表。