问题描述
类型定义为
data BST = MakeNode BST String BST
| Empty
我正在尝试向树中添加新的叶子，但我真的不知道如何使用递归来做到这一点。
函数设置如下
add :: String -> BST -> BST
推荐答案
使用二叉树的优势在于，您只需查看树的"当前部分"即可知道在何处插入节点。
那么，让我们定义add函数：
add :: String -> BST -> BST
如果您将某些内容插入到空树中(案例1)，则只需直接创建一片叶子：
add s Empty = MakeNode Empty s Empty
如果您想要将某些内容插入到一个节点中(案例2)，您必须决定要在哪个子节点中插入值。使用比较来执行此测试：
add s t@(MakeNode l p r) -- left, pivot, right
| s > p = Node l p (add s r) -- Insert into right subtree
| s < p = Node (add s l) p r -- Insert into left subtree
| otherwise = t -- The tree already contains the value, so just return it
["a", "b", "c", "d"])，它将变得非常不平衡，但这种情况在实践中非常罕见。