2

如何删除 BST 中的最小值？我似乎找不到保留树的方法

data BST = EmptyT
         | Node Float BST BST
           deriving (Eq, Show, Read)

deleteMin :: BST -> Maybe BST
deleteMin EmptyT  = Nothing
deleteMin (Node x left right)
    |left == EmptyT = ? 
    |otherwise = ?

我需要吸气剂和二传手吗？

4

1 回答 1

5

Haskell 没有 OOP 意义上的“getter and setter”，尽管您可以提出类似的概念。如果要删除二叉树中的值，则必须构造一个缺少该值的新树。这就是你如何“保护树”。

假设您使用的是标准 BST，那么树中最左边的节点将包含最小元素。所以，通过向左遍历你的树，你最终应该会遇到这样的情况Node x EmptyT r。任何其他节点，您只需递归调用deleteMin左分支。

这给出了一个看起来像的函数

deleteMin :: BST -> Maybe BST
deleteMin EmptyT                = Nothing
deleteMin (Node x EmptyT right) = Just right
deleteMin (Node x left right)   =
    case deleteMin left of
         Nothing -> Nothing
         Just nl -> Just $ Node x nl right

您必须检查每次调用的结果deleteMin以检查 Nothing. 我不认为你真的需要返回 a Maybe BST，除非你真的需要表明没有要删除的元素。如果没有要删除的内容，则返回一棵空树更有意义（至少对我而言）。

我认为大多数人也会考虑使用模式匹配，而不是使用带有相等检查的守卫。

于 2013-01-27T04:27:35.863 回答