Binary Search Tree in Haskell
二叉搜索树是一种递归数据结构，其基本概念不再赘述，在Haskell中用代数数据类型，先声明树类型：一个二叉搜索树Tree要么是空树，要么是包含一个值且有左右子树
data Tree a = EmptyTree | Node a (Tree a) (Tree a) deriving (Show)
这里Tree就是BinSearchTree，在建树的时候我们通过取一个值和一棵树并将这个值加入到这棵树当中来做。过程中会将此值与树的结点进行数值比较，若小于根则向左，若大于则向右，重复这个过程，直到达到空树。在C语言中我们会通过修改指针并调整树的数据来进行，但Haskell作为纯函数式，不能对树作修改，只能在修改后，返回一棵全新的树。我们的函数签名大概是 (Ord a)=>a -> Tree a->Tree a类型的，取一个可比较的a类型与一棵树作为参数，返回一棵插入过相应元素的新树。这样虽然看起来有点低效，但是Haskell对此类操作进行了专门优化，允许新树与旧树共享大部分子树。
有了Tree a的类，首先编写插入函数：
singleton :: a -> Tree a
singleton x = Node x EmptyTree EmptyTree
treeInsert :: (Ord a) => a -> Tree a -> Tree a
treeInsert x EmptyTree = singleton x
treeInsert x (Node a left right)
| x==a = Node a left right
| x<a = Node a (treeInsert x left) right
| x>a = Node a left (treeInsert x right)singleton是辅助函数，它表示一个单结点树。根据搜索树的定义，向空树中插入值时就将当前值插入当前结点，如果插入值小于根结点，就继续向左子树中插入，大于则向右子树中插入。如果相等则将树原样返回。
检查元素的存在性，同样利用树的定义，如果是空树则元素不存在树中，若等于根结点则说明存在于树中，小于则继续在左子树中找，大于则在右子树中找。
treeElem :: (Ord a) => a -> Tree a -> Bool
treeElem x EmptyTree = False
treeElem x (Node a left right)
| x==a = True
| x<a = treeElem x left
| x>a = treeElem x right编写一个main测试一下这个二叉搜索树：
main = do
let t = foldr treeInsert EmptyTree [1,5,3,11,6,7,4,2]
print t
print $ treeElem 3 t
print $ treeElem 13 t输出
Node 2 (Node 1 EmptyTree EmptyTree) (Node 4 (Node 3 EmptyTree EmptyTree) (Node 7 (Node 6 (Node 5 EmptyTree EmptyTree) EmptyTree) (Node 11 EmptyTree EmptyTree))) True False
将第1行树的输出格式化一下：
Node 2 (Node 1 EmptyTree EmptyTree ) (Node 4 (Node 3 EmptyTree EmptyTree ) (Node 7 (Node 6 (Node 5 EmptyTree EmptyTree ) EmptyTree ) (Node 11 EmptyTree EmptyTree ) ) )
根据二叉搜索树的知识，这个构建是正确的，2是首个元素，比2小的元素（仅有1）是其左子树，比2大的都在右子树。可以编写一个中序遍历这个树，二叉搜索树的中序遍历是有序（去重）的，可以再次验证二叉搜索树构造的正确性：
postOrder :: Tree a -> [a] postOrder EmptyTree = [] postOrder (Node a left right) = postOrder left ++ [a] ++ postOrder right
将[1,5,3,11,6,7,4,2]为序列foldr插入建树，树的中序遍历为[1,2,3,4,5,6,7,11]，确实是有序的序列。