P57 - 二叉搜索树
Binary search trees
官方模块：
Problems.P57核心函数：construct,addedTo
题目描述
按输入顺序把元素插入二叉搜索树。小于当前节点的值进入左子树，其余值进入右子树，因此重复值也会保留。
函数签名
1addedTo :: Ord a => a -> Tree a -> Tree a
2construct :: Ord a => [a] -> Tree a
实现
方法一：递归插入 + foldl
1addedTo :: Ord a => a -> Tree a -> Tree a
2addedTo x Empty = leaf x
3addedTo x (Branch y left right)
4 | x < y = Branch y (addedTo x left) right
5 | otherwise = Branch y left (addedTo x right)
6
7construct :: Ord a => [a] -> Tree a
8construct = foldl (flip addedTo) Empty
标准 BST 插入：比较、递归、重建。construct 用 foldl 逐个插入。
方法二：按根值稳定分区
1construct :: Ord a => [a] -> Tree a
2construct [] = Empty
3construct (root:values) = Branch root
4 (construct [value | value <- values, value < root])
5 (construct [value | value <- values, value >= root])
第一个元素仍是根；剩余元素按原顺序稳定分成“小于根”和“不小于根”两组，再递归构造左右子树。这与逐个插入得到相同形状，但直接从输入序列推导子树。
方法对比
| 方法 | 构造过程 |
|---|---|
| 逐个插入 | 状态是一棵不断增长的 BST |
| 稳定分区 | 递归地把后续输入分给左右子树 |
测试
1>>> construct [3,2,5]
2Branch 3 (Branch 2 Empty Empty) (Branch 5 Empty Empty)
3>>> symmetric (construct "abccba")
4True